Эйлер атындағы олимпиада, 2016-2017 оқу жылы, аймақтық кезеңнің 1 туры

Бір елдің қалаларының арасында кез келген қаладан кез келген басқа қалаға (мүмкін, басқа қала арқылы) жетуге болатындай екі бағытты тұра авиарейстер ұйымдастырылған. Сонымен қатар кез келген $A$ қаласы үшін, келесі шарттар орындалатындай $B$ қаласы бар: осы екі қаладан басқа қаладардың әрқайсысы $A$ қаласымен, немесе $B$ қаласымен тұра қосылған. Кез келген қаладан кез келген басқа қалаға ең көп дегенде екі орын ауыстыру арқылы жетуге болатынын дәлелдеңіздер. ( И. Богданов )

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

Комментарии от администратора Комментарии от администратора №1.     Решение. Пусть $X$ и $Y$ — произвольные два города, а $X$, $Z_1$, $\ldots$, $Z_k$, $Y$ — маршрут между ними с наименьшим числом пересадок. Предположим, что $k \ge 3$. Тогда $Z_2$ не соединён рейсом ни с $X$, ни с $Y$, иначе наш маршрут можно бы было бы сократить, воспользовавшись этим рейсом. По условию, существует город $B$ такой, что каждый город, отличный от $Z_2$ и $B$, соединён рейсом хотя бы с одним из них. Значит, каждый из городов $X$ и $Y$ либо соединён с $B$, либо сам является городом $B$. Но, если $X \ne B \ne Y$, то существует маршрут $X$, $B$, $Y$ с одной пересадкой, в противном случае существует даже рейс между $X$ и $Y$. В любом случае мы получили противоречие с выбором $k$. Значит, предположение неверно, и $k \le 2$. В силу произвольности выбора $X$ и $Y$ требуемое утверждение доказано.