Упр.1150 ГДЗ Мерзляк Полонский 6 класс (Математика)

Задача

Докажем, что, если каждый из семи городов соединён дорогами более, чем с двумя городами, всегда из любого города можно доехать до любого другого.
Используем для этого метод от противного. Предположим, что при таких условиях существуют два таких города А и В, что добраться из города А в город В нельзя.
По условию задачи, каждый из этих городов имеет минимум по три дороги, идущие в другие города. Чтобы было невозможно добраться из А в В, нам нужно, чтобы «соседи» города А были не соединены с «соседями» города В.
Кроме того, из каждого города выходит минимум по три дороги, поэтому карта страны Севентаун будет выглядеть так.
Теперь выполнены все условия, кроме самого главного: в городе не семь, а восемь городов.
Наличие восьмого города позволяет получить противоречие условию задачи. Значит, наше предположение, что существуют два города А и В, между которыми нет дорожного сообщения, — неверно. Получаем, что таких городов не существует. Следовательно, из любого города можно доехать до любого другого.
Для карты Севентауна это будет означать, что один город должен совпасть, например, так.

Подробный ответ

Рассмотрим решение от противного. Предположим, что существуют два города А и В, из которых нельзя доехать один до другого.

Тогда все дороги, выходящие из города А, должны вести только в города, из которых нельзя попасть в В. По условию из каждого города выходит более двух дорог, значит, из А выходит как минимум 3 дороги, и из В тоже как минимум 3 дороги.

Если из А нельзя добраться до В, то «соседи» города А не могут совпадать с «соседями» города В. Получаются две отдельные группы городов: вместе с городом А не меньше 4 городов и вместе с городом В не меньше 4 городов.

Тогда всего городов должно быть не меньше

$$4+4=8.$$

Но по условию в стране всего 7 городов. Получили противоречие.

Значит, предположение неверно, и из любого города можно доехать до любого другого, возможно, проезжая через другие города.