Математикадан республикалық олимпиада, 1999-2000 оқу жылы, 9 сынып

«Жетпіс жеті күн» бағдарламасының мәліметі бойынша Қызықстан елінде 14 облыстық орталық және 79 ұшақ бар. Авиакеросинді үнемдеу мақсатымен әрбәр үшақ тек екі қаланың арасында ғана үша алады және кез-келген екі қала көп дегенде бір үшақпен байланысады. Осы жағдайда жолаушы кез келген облыс орталығынан басқа бір облыс орталығына көп дегенде бір-ақ рет үшақ ауыстырып жете алатынын дәлелдеңіздер.

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

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

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

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