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

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

Условие

В стране несколько городов, некоторые пары городов соединены беспосадочными рейсами одной из N авиакомпаний, причём из каждого города есть ровно по одному рейсу каждой из авиакомпаний. Известно, что из каждого города можно долететь до любого другого (возможно, с пересадками). Из-за финансового кризиса был закрыт  N – 1  рейс, но ни в одной из авиакомпаний не закрыли более одного рейса. Докажите, что по-прежнему из каждого города можно долететь до любого другого.


Решение

  Рассмотрим некоторый путь, соединяющий некоторые два города, возможно включающий в себя некоторые закрытые после кризиса рейсы. Покажем, что в этом пути любой закрытый рейс можно заменить последовательностью незакрытых.
  Пронумеруем авиакомпании числами от 1 до N. В одной из авиакомпаний (пусть в первой) сохранились все рейсы. Тогда в каждой из остальных закрыли по одному рейсу.
  Рассмотрим только рейсы первой и второй авиакомпаний: из каждого города выходит по одному рейсу этих авиакомпаний. Следовательно, все города разбиваются на циклы.
  В одном из этих циклов закрыли один рейс. Очевидно, можно пролететь остальными рейсами этого цикла, следовательно, мы можем обойти любой закрытый рейс.
  Отметим, что мы при этом не используем рейсы других авиакомпаний, следовательно, аналогично можно обойтись без остальных закрытых рейсов.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 1999
Этап
Вариант 5
Класс
Класс 9
задача
Номер 99.5.9.2

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

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