|
|
 |
Условие
В городе Никитовка двустороннее движение. В течение двух лет в городе проходил ремонт всех дорог. Вследствие этого в первый год на некоторых дорогах было введено одностороннее движение. На следующий год на этих дорогах было восстановлено двустороннее движение, а на остальных дорогах введено одностороннее движение. Известно, что в каждый момент ремонта можно было проехать из любой точки города в любую другую. Доказать, что в Никитовке можно ввести одностороннее движение так, что из каждой точки города удастся проехать в любую другую точку.
Решение
Индукция по числу городских перекрёстков (из которых исходят более двух дорог).
База. Если в Никитовке имеются всего два перекрёстка A и B, то утверждение очевидно: по условию из A в B ведут не менее двух дорог; поэтому достаточно установить по одной из этих дорог движение от A к B, а по второй – от B к A, мы сможем проехать от каждого перекрёстка до любого, отличного от него.
Шаг индукции. Рассмотрим город Никитовку, имеющий n + 1 перекрёсток и два соседних из этих перекрёстков – перекрёстки A и B, соединённые улицей AB. Поскольку после введения на улице AB (при её ремонте) одностороннего движения – скажем, от A к B – проехать от B к A было возможно, то из B в A ведёт некоторая не включающая улицы AB "цепочка" улиц (эту "цепочку" можно считать не имеющей самопересечений). Таким образом, мы приходим к существованию в Никитовке "кольца" s – замкнутой сети улиц, ведущей из A в B, а затем (через ряд "промежуточных" перекрёстков) – снова в A.
Рассмотрим теперь новый город, план которого получается из плана Никитовки "склеиванием" всех перекрёстков нашего кольца s в один перекрёсток S, из которого исходят все улицы, реально "упирающиеся" в кольцо s. Число перекрёстков такого условного города меньше n + 1; поэтому по предположению индукции в нём можно ввести по всем улицам одностороннее движение с соблюдением требований задачи. Если мы затем оставим движение по всем не входящим в кольцо s улицам таким же, каким оно было в этом новом городе, а по кольцу s пустим движение в одном (безразлично каком!) направлении, то на всех улицах Никитовки будет установлено одностороннее движение – и притом с каждого перекрёстка можно будет проехать в любой другой.
