Задача 133: В стране N 13 городов, каждый из которых соединён авиасообщением с 6 другими. Докажите, что из любого города можно добраться в любой другой (возможно, с пересадками).

Здравствуйте, ребята! Давайте разберем эту интересную задачу. **Доказательство:** Предположим, что из некоторого города А нельзя добраться до некоторого города Б. Давайте посмотрим, что из этого следует. 1. **Города, достижимые из А:** Город А соединен с 6 другими городами. Назовем эти города 'группой 1'. Таким образом, мы можем достичь 7 городов (сам город А и 6 городов из 'группы 1') напрямую. 2. **Города, недостижимые из А:** Остается 13 - 7 = 6 городов, недостижимых из города А. Назовем эти города 'группой 2'. 3. **Соединения городов из группы 2:** Каждый город из 'группы 2' соединен с 6 другими городами. Но он не может быть соединен ни с городом А, ни с городами из 'группы 1', так как в таком случае он был бы достижим из города А. Следовательно, каждый город из 'группы 2' должен быть соединен с остальными 5 городами из 'группы 2', а также с одним городом из группы А или группы 1. 4. **Противоречие**: Всего у каждого города должно быть 6 связей. В группе 2 у каждого города есть 5 связей внутри группы. Остается только одна связь, которая должна идти в группу городов, достижимых из города A. Это значит, что 6 городов в группе 2 должны быть соединены с группой из 7 городов. Однако общее количество связей из группы 2 составляет 6 городов * 6 связей /2 = 18 связей. Эти связи должны соединять группу 2 с группой 1. Это означает, что группе 1 необходимо иметь минимум 18 связей. Но так как в группе 1 (включая город А) всего 7 городов, а у каждого из них только 6 связей, то получается максимум 7 * 6 = 42 связи. Это значит, что минимум 18 связей должны быть у группы 2. Однако у группы 2 всего 6 городов, и у каждого есть 6 связей (по условию), но 5 из них внутри группы 2. Значит, от каждого города в группе 2 идет только 1 связь к городам из группы, достижимой из города A. Тогда максимум 6 связей может быть между группами. Получаем противоречие. **Вывод:** Предположение, что из какого-то города нельзя добраться в какой-то другой, приводит к противоречию. Следовательно, из любого города можно добраться в любой другой город (возможно, с пересадками). Надеюсь, это объяснение вам понятно. Если есть вопросы, не стесняйтесь задавать!