Олимпиада имени Леонарда Эйлера 2016-2017 учебный год, I тур регионального этапа

Между городами страны организованы двусторонние беспосадочные авиарейсы таким образом, что от каждого города до каждого другого можно добраться (возможно, с пересадками). Более того, для каждого города $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$ требуемое утверждение доказано.