Задача 5.
В городе Октопусе построили метро из 8 станций. При этом из них выходит 4, 3, 3, 3, 2, 2, 2, 1 линий метро соответственно (одна линия соединяет ровно две станции). Одну линию закрыли на ремонт. Могло ли оказаться, что теперь карта метро состоит из двух одинаковых независимых кусков?
Ответ на Задачу 5.
Ответ: Не могло.
Решение 1:
Предположим, что такое получиться могло. Тогда карта разбилась на два одинаковых куска по 4 станции, из которых выходит соответственно равное количество линий. Значит, после удаления одной линии станций с 4 исходящими линиями больше нет (иначе она попала бы в какой-то только один кусок, и в другом куске такой станции не было бы). Также, чтобы такое разделение имело место, нужно, чтобы после закрытия одной линий, число станций с двумя исходящими линиями должно быть чётно (чтобы поделилось пополам на 2 куска). Следовательно, необходимо, чтобы была закрыта линия, соединяющая станцию с 4 исходящими линиями и станцию с 2 исходящими линиями. Тогда получим, что в каждом куске должны быть такие станции с таким числом исходящих линий: 3, 3, 2, 1, что невозможно. Докажем это. Сосчитаем количество всех линий в этом куске — (3+3+2+1):2 — каждую линию мы сосчитали дважды и должно было получиться чётное число, но оно нечётное. Следовательно, такой вариант невозможен.
Решение 2:
Предположим, что такое получиться могло. Тогда карта разбилась на два одинаковых куска по 4 станции, из которых выходит соответственно равное количество линий. Значит, после удаления одной линии количество линий должно стать чётным. Но изначально их уже было (4+3+3+3+3+2+2+2+1):2=10 — чётно. Соответственно будет нечётно и поделить на две части будет нельзя.
