Разделы 
Дополнительно
Задача по математике - 1902
2019-01-21 
В стране несколько городов, некоторые пары городов соединены беспосадочными рейсами одной из $N$ авиакомпаний, причем из каждого города есть ровно по одному рейсу каждой из авиакомпаний. Известно, что из любого города можно долететь до любого другого (возможно, с пересадками). Из-за финансового кризиса был закрыт $N - 1$ рейс, но ни в одной из авиакомпаний не закрыли более одного рейса. Докажите, что по- прежнему из любого города можно долететь до любого другого.
Решение:
Рассмотрим некоторый путь, соединяющий некоторые два города, возможно включающий в себя некоторые закрытые после кризиса рейсы. Покажем, что в этом пути любой закрытый рейс можно заменить последовательностью незакрытых. Пронумеруем авиакомпании числами от $1$ до $N$. В одной из авиакомпаний сохранились все рейсы: предположим, что в первой. Тогда в любой другой авиакомпании закрыли по одному рейсу. Рассмотрим только рейсы первой и второй авиакомпаний: из каждого города выходит по одному рейсу этих авиакомпаний. Следовательно, все города разбиваются на циклы. В одном из этих циклов закрыли один рейс. Очевидно, можно пролететь остальными рейсами этого цикла, следовательно, мы можем «обойти» любой закрытый рейс. Отметим, что мы при этом не используем рейсы других авиакомпаний, следовательно, аналогично можно обойтись без остальных закрытых рейсов.
В стране несколько городов, некоторые пары городов соединены беспосадочными рейсами одной из $N$ авиакомпаний, причем из каждого города есть ровно по одному рейсу каждой из авиакомпаний. Известно, что из любого города можно долететь до любого другого (возможно, с пересадками). Из-за финансового кризиса был закрыт $N - 1$ рейс, но ни в одной из авиакомпаний не закрыли более одного рейса. Докажите, что по- прежнему из любого города можно долететь до любого другого.
Решение:
Рассмотрим некоторый путь, соединяющий некоторые два города, возможно включающий в себя некоторые закрытые после кризиса рейсы. Покажем, что в этом пути любой закрытый рейс можно заменить последовательностью незакрытых. Пронумеруем авиакомпании числами от $1$ до $N$. В одной из авиакомпаний сохранились все рейсы: предположим, что в первой. Тогда в любой другой авиакомпании закрыли по одному рейсу. Рассмотрим только рейсы первой и второй авиакомпаний: из каждого города выходит по одному рейсу этих авиакомпаний. Следовательно, все города разбиваются на циклы. В одном из этих циклов закрыли один рейс. Очевидно, можно пролететь остальными рейсами этого цикла, следовательно, мы можем «обойти» любой закрытый рейс. Отметим, что мы при этом не используем рейсы других авиакомпаний, следовательно, аналогично можно обойтись без остальных закрытых рейсов.
