В стране 101 город , причем некоторые города соединены дорогами с односторонним движением так, что, во-первых, нет двух дорог с одинаковым направлением, а, во-вторых, из каждого города выходит и в каждый город входит хотя бы по 50 дорог (дорога не идет из города в этот же город). Докажите, что от любого города до любого другого можно добраться, проехав не более чем по двум дорогам.

Предыдущий
вопрос Следующий
вопрос

Возьмем произвольные два города A и B. Поскольку из каждого города выходит и входит хотя бы по 50 дорог, то существует по крайней мере одна дорога, ведущая из города A в другой город C, и одна дорога, ведущая из города D в город B.

Теперь рассмотрим все возможные случаи:

1) Если города C и D совпадают, то мы можем доехать от города A до города B, проезжая всего одну дорогу (напрямую через город C или D).

2) Если города C и D различны, то существуют две возможности:
2.1) Существует дорога напрямую из города C в город D. В этом случае мы можем доехать от города A до города B, проезжая всего две дороги (по дороге из A в C, затем из C в D, затем из D в B).
2.2) Не существует прямой дороги из города C в город D. В таком случае существует город E, из которого есть дороги как в город C, так и в город D (поскольку из каждого города выходит и входит хотя бы по 50 дорог). Мы можем доехать от города A до города B, проезжая всего две дороги (по дороге из A в C через город E, затем из E в D, затем из D в B).

Таким образом, в любом случае мы можем добраться от любого города до любого другого, проезжая не более чем по двум дорогам.