В стране есть несколько городов и несколько дорог с односторонним движением Каждая дорога соединяет два города и не проходит через остальные . При,этом какие бы два города не взять, хотя бы из одного из них можно проехать в другой, не нарушая правил движения.Докажите,что найдется город ,из которого можно проехать в любой другой, не нарушая правил движения
Пусть в стране есть n городов. Также пусть каждый город соединен односторонними дорогами с другими городами, формируя n (n-1) пар дорог.
Рассмотрим для каждого города величину, равную количеству городов, в которые можно попасть из данного города, не нарушая правил движения.
Если ни в одном городе невозможно попасть во все остальные, то для каждого города эта величина будет строго меньше n-1. Таким образом, мы получим n чисел, каждое из которых меньше n-1.
Однако по принципу Дирихле, если есть n+1 элементов, и ни один из них не превышает n-1, то как минимум 2 из этих чисел должны совпадать.
Рассмотрим два города, количество городов, в которые можно попасть из каждого из них, совпадают. Пусть это города А и В.
Мы знаем, что из города А можно попасть в любой другой город, не нарушая правил движения.
Теперь рассмотрим город С, из которого нельзя попасть в город В без нарушения правил. Так как мы знаем, что из города А можно попасть в любой другой город, не нарушая правил, то существует дорога из города А в город С, не нарушающая правила движения.
Таким образом, из города С можно попасть как минимум в два города: в город В и в город С, что противоречит условию задачи.
Следовательно, найдется город, из которого можно проехать в любой другой город, не нарушая правила движения.