Республиканская олимпиада по математике, 2000 год, 9 класс

В стране имеется 14 областных центров и 79 самолетов. Ввиду экономии авиакеросина каждый самолет может летать только между двумя городами, и между любыми двумя городами летает не более одного самолета. Доказать, что пассажир может попасть из любого областного центра в любой другой не более чем с одной пересадкой.

Комментарий/решение

Общее количество рейсов у нас 14×13/2=91. Докажем от противного.Пусть все же нашлись два таких областных центров где пассажир не сможет попасть из одного центра в другую не более чем с 1 пересадкой.Обозначим эти "города" как точки $A$ и $B$. Пусть в город $B$ ведет $k$ авиадорог.Тогда в город $A$ ведет не больше 13-$k$ дорог.Тогда всего мы имеем $n$ пустых авиарейсов, где $n$>12.

Следовательно 91-$n$<79.Противоречие.

$"Пустые" авиарейсы(дороги)$ - авиарейс между какими то двумя городами где не летает ни один самолет.