Упр.1150 ГДЗ Мерзляк Полонский 6 класс (Математика)
Решение #1
Решение #2
Рассмотрим вариант решения задания из учебника Мерзляк, Полонский, Якир 6 класс, Вентана-Граф:
1150. В стране Севентаун семь городов, каждый из которых соединён дорогами более чем с двумя городами. Докажите, что из любого города можно доехать до любого другого (возможно, проезжая через другие города).
Докажем, что, если каждый из семи городов соединён дорогами более, чем с двумя городами, всегда из любого города можно доехать до любого другого.
Используем для этого метод от противного. Предположим, что при таких условиях существуют два таких города А и В, что добраться из города А в город В нельзя.
По условию задачи, каждый из этих городов имеет минимум по три дороги, идущие в другие города. Чтобы было невозможно добраться из А в В, нам нужно, чтобы «соседи» города А были не соединены с «соседями» города В.
Кроме того, из каждого города выходит минимум по три дороги, поэтому карта страны Севентаун будет выглядеть так.
Теперь выполнены все условия, кроме самого главного: в городе не семь, а восемь городов.
Наличие восьмого города позволяет получить противоречие условию задачи. Значит, наше предположение, что существуют два города А и В, между которыми нет дорожного сообщения, - неверно. Получаем, что таких городов не существует. Следовательно, из любого города можно доехать до любого другого.
Для карты Севентауна это будет означать, что один город должен совпасть, например, так.
*размещая тексты в комментариях ниже, вы автоматически соглашаетесь с пользовательским соглашением
