2014-06-08
Некоторые из городов $P_{1}, \cdots, P_{1983}$ соединены попарно некоторыми авиалиниями, принадлежащими компаниям $A_{1}, \cdots, A_{10}$. Известно только, что из любого города можно перелететь в любой другой без пересадок и что каждая авиалиния действует в обоих направлениях. Доказать, что (как бы ни были города соединены авиалиниями) существует хотя бы одна компания, которая может обеспечить путешествие с началом и концом в одном и том же городе и с нечетным числом используемых авиалиний.
Решение:
Докажем индукцией пo $n \in \mathbf{N}$, что если есть $n$ компаний $A_{1}, \cdots, A_{n}$ и $N$ городов $P_{1}, \cdots, P_{N}$, причем $N > 2^{n}$ и любые два города соединены авиалиниями, то хотя бы одна компания сможет обеспечить круговое путешествие с нечетным числом авиалиний. Поскольку $1983 > 1024 = 2^{10}$, то требуемое в задаче утверждение будет доказано. Если $n = 1$, то $N \geq 3$ и $P_{1}P_{2}P_{3}P_{1}$ - искомое путешествие. Пусть утверждение доказано для числа $n – 1$. Докажем его для числа $n$. Пусть все круговые путешествия компании $A_{n}$ состоят из четного числа авиалиний (иначе утверждение можно считать доказанным). Тогда разобьем города на две группы
$R = \{R_{1}; \cdots; R_{k} \}$ и $Q = \{Q_{1}; \cdots; Q_{m} \}$ следующим образом. Положим $P_{1} \in R$. Далее, все города, в которые можно прилететь на самолетах компании $A_{n}$ без пересадок из $P_{1}$, включим в группу $Q$. Все города, в которые можно прилететь на самолетах компании $A_{n}$ из городов, лежащих в $Q$, без пересадок, включим в $R$, и т. д. При этом никогда не случится так, что два города из одной группы ($R$ или $Q$) связаны авиалинией компании $A_{n}$ (иначе появится круговое путешествие с нечетным числом авиалиний). Если мы исчерпали все города, в которые можно прилететь из $P_{1}$ на самолетах компании $A_{n}$, то включим в $R$ любой из оставшихся городов и продолжим описанные действия (до тех пор, пока все города не будут распределены по группам). Хотя бы в одной из групп $R$ или $Q$ находится более чем $2^{n-1}$ городов (ибо $k + m = N > 2^{n}$), а внутри каждой из этих групп все перелеты обеспечивают компании $A_{1}, A_{2}, \cdots, A_{n-1}$ (так как компания $A_{n}$ соединяет только города из $R$ с городами из $Q$). Остается применить предположение индукции.