|
|
 |
Условие
В стране больше 101 города. Столица соединена авиалиниями со 100 городами, а каждый город, кроме столицы, соединён авиалиниями ровно с десятью городами (если A соединён с B, то B соединён с A). Известно, что из каждого города можно попасть в любой другой (может быть, с пересадками). Доказать, что можно закрыть половину авиалиний, идущих из столицы, так, что возможность попасть из каждого города в любой другой сохранится.
Решение 1
Рассмотрим граф, вершины которого соответствуют городам, а рёбра – авиалиниям. Мысленно закроем все линии, ведущие из столицы. Оставшаяся часть графа распадается на компоненты связности. Достаточно доказать, что каждая из этих компонент в исходном графе соединялась со столицей по крайней мере двумя рёбрами-линиями (тогда все, кроме одной, можно закрыть). Допустим противное: компонента М соединена со столицей только одним ребром. Тогда в графе, состоящем из этой компоненты, степень одной вершины – 9, а всех остальных – 10, что невозможно (см. задачу 87972). Противоречие.
Решение 2
Пусть авиапассажир вылетит из столицы в произвольном направлении и далее будет путешествовать, каждый раз используя новую авиалинию, пока это возможно. Поскольку линий конечное число, в какой-то момент он застрянет в одном из городов, использовав все идущие из него авиалинии. Однако в городе, отличном от столицы, он застрять не мог: при каждом посещении он использует две линии (прилетел – улетел), а всего линий чётное число – 10. Следовательно, он застрянет в столице. Но перед этим он должен предварительно 50 раз вылететь из столицы и снова вернуться туда. Таким образом, его маршрут состоит из 50 петель. Можно на каждой из этих петель закрыть ту авиалинию, по которой пассажир возвращался в столицу. Очевидно при этом возможность попасть из каждого города в любой другой сохранится.
Замечания
баллы: 8
