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

Для доказательства данного факта воспользуемся принципом Дирихле.

Пусть в стране есть n городов. Также пусть каждый город соединен односторонними дорогами с другими городами, формируя n (n-1) пар дорог.

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

Если ни в одном городе невозможно попасть во все остальные, то для каждого города эта величина будет строго меньше n-1. Таким образом, мы получим n чисел, каждое из которых меньше n-1.

Однако по принципу Дирихле, если есть n+1 элементов, и ни один из них не превышает n-1, то как минимум 2 из этих чисел должны совпадать.

Рассмотрим два города, количество городов, в которые можно попасть из каждого из них, совпадают. Пусть это города А и В.

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

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

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

Следовательно, найдется город, из которого можно проехать в любой другой город, не нарушая правила движения.