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