Решение задачи 445

Условие:

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

Решение:

Рассмотрим город А, из которого выходит наибольшее число дорог (если таких несколько, выберем любой). Рассмотрим произвольный другой город В. Если из А в В ведет дорога, то добираемся до В за один ход.

Пусть из А в В не ведет дорога, то есть она ведет из В в А. Рассмотрим все города (пусть их n), до которых можно добраться за один ход из города А. Если из всех из них не ведет дорога в В, (то есть из В в них ведут дороги), то из В ведет хотя бы n+1 дорог, а из А всего n, противоречие. Значит, среди рассмотренных городов найдется тот, из которого можно одним ходом попасть в В. Значит, из А в В можно добраться по двум дорогам.