ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 97779
Темы:    [ Связность и разложение на связные компоненты ]
[ Степень вершины ]
[ Обход графов ]
Сложность: 4+
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

Автор: Фольклор

В стране больше 101 города. Столица соединена авиалиниями со 100 городами, а каждый город, кроме столицы, соединён авиалиниями ровно с десятью городами (если A соединён с B, то B соединён с A). Известно, что из каждого города можно попасть в любой другой (может быть, с пересадками). Доказать, что можно закрыть половину авиалиний, идущих из столицы, так, что возможность попасть из каждого города в любой другой сохранится.


Решение 1

Рассмотрим граф, вершины которого соответствуют городам, а рёбра – авиалиниям. Мысленно закроем все линии, ведущие из столицы. Оставшаяся часть графа распадается на компоненты связности. Достаточно доказать, что каждая из этих компонент в исходном графе соединялась со столицей по крайней мере двумя рёбрами-линиями (тогда все, кроме одной, можно закрыть). Допустим противное: компонента М соединена со столицей только одним ребром. Тогда в графе, состоящем из этой компоненты, степень одной вершины – 9, а всех остальных – 10, что невозможно (см. задачу 87972). Противоречие.


Решение 2

Пусть авиапассажир вылетит из столицы в произвольном направлении и далее будет путешествовать, каждый раз используя новую авиалинию, пока это возможно. Поскольку линий конечное число, в какой-то момент он застрянет в одном из городов, использовав все идущие из него авиалинии. Однако в городе, отличном от столицы, он застрять не мог: при каждом посещении он использует две линии (прилетел – улетел), а всего линий чётное число – 10. Следовательно, он застрянет в столице. Но перед этим он должен предварительно 50 раз вылететь из столицы и снова вернуться туда. Таким образом, его маршрут состоит из 50 петель. Можно на каждой из этих петель закрыть ту авиалинию, по которой пассажир возвращался в столицу. Очевидно при этом возможность попасть из каждого города в любой другой сохранится.

Замечания

баллы: 8

Источники и прецеденты использования

журнал
Название "Квант"
год
Год 1982
выпуск
Номер 8
Задача
Номер М756
олимпиада
Название Турнир городов
Турнир
Дата 1981/1982
Номер 3
вариант
Вариант 7-8 класс
Задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .