В стране несколько городов, некоторые пары городов соединены беспосадочными рейсами одной из N авиакомпаний, причём из каждого города есть ровно по одному рейсу каждой из авиакомпаний. Известно, что из каждого города можно долететь до любого другого (возможно, с пересадками). Из-за финансового кризиса был закрыт N–1 рейс, но ни в одной из авиакомпаний не закрыли более одного рейса. Докажите, что по-прежнему из каждого города можно долететь до любого другого.
Это задача 9.2 Всероссийской олимпиады по математике 1999 года.
Автор задачи - Д.В. Карпов.
Рассмотрим два каких-нибудь города и произвольный путь, который соединял их до закрытия рейсов.
Докажем, что все закрытые рейсы можно заменить последовательностью рейсов, которых ещё не закрыли.
Пронумеруем авиакомпании числами от 1 до N. В одной из авиакомпаний (пусть в первой) сохранились все рейсы. Тогда в каждой из остальных закрыли по одному рейсу.
Рассмотрим только рейсы первой и второй авиакомпаний: из каждого города выходит по одному рейсу этих авиакомпаний. Следовательно, все города разбиваются на циклы (это утверждение часто называют леммой о хороводах).
В одном из этих циклов закрыли один рейс. Очевидно, можно пролететь остальными рейсами этого цикла. Значит, мы можем обойти любой закрытый рейс.
Заметим, что при этом мы никак не используем рейсы других авиакомпаний. Следовательно, аналогично можно обойтись без остальных закрытых рейсов.