Номер 1269 — ГДЗ математика 6 класс Мерзляк
№ 1269.
В стране Севентаун семь городов, каждый из которых соединен дорогами более чем с двумя городами.
Докажите, что из любого города можно доехать до любого другого (возможно, проезжая через другие города).
💡 Подсказка (без ответа)
Используй метод доказательства от противного. Предположи, что города разделены на несвязные группы, и найди противоречие с условием, что каждый город соединён более чем с двумя другими городами.
Решение по шагам · ✓ ответ сверен
Предположим противное: пусть города разбиты на несколько отдельных групп, которые между собой не соединены дорогами.
Рассмотрим одну группу, в которой находится наименьшее количество городов. Пусть в этой группе k городов (k ≤ 3, так как всего 7 городов, и если групп больше одной, то в какой-то группе не более 3 городов).
Возьмём любой город из этой группы. По условию задачи, он соединён более чем с двумя городами, то есть минимум с 3 городами. Но в его группе всего k ≤ 3 городов (включая сам этот город), значит максимум он может быть соединён с (k − 1) городами внутри группы.
Получаем противоречие:
- Город должен быть соединён с более чем 2 городами (то есть минимум с 3)
- Но в группе он может быть соединён максимум с (k − 1) ≤ 2 городами
Таким образом, наше предположение неверно. Города не могут быть разбиты на отдельные несвязные группы.
Значит, все города образуют одну связную сеть, и из любого города можно доехать до любого другого (проезжая через другие города при необходимости).