2019-04-29
На всех улицах города Зурбагана существовало двустороннее движение. Когда, однако, городским властям потребовалось произвести ремонт всех дорог, они вынуждены были временно ввести на части улиц одностороннее движение, оставив движение на остальных улицах двусторонним; после этого, напротив, односторонним было сделано движение по тем улицам, которые ранее не ремонтировались, а по улицам, где движение ранее было односторонним, снова было разрешено ехать в обоих направлениях. При этом в период ремонта дорог в обоих случаях можно было проехать из любого пункта Зурбаганэ в любой другой. Доказать, что в Зурбагане можно ввести одностороннее движение по всем улицамч так, чтобы проезд из любого пункта города в любой другой оставался возможным.
Решение:
Будем доказывать утверждение задачи методом математической индукции по числу городских перекрестков (из которых исходят более двух дорог). Если в Зурбагане имеются всего два перекрестка $A$ и $B$, то утверждение задачи очевидно: из $A$ в $B$ ведут не менее двух дорог (если бы такая дорога была одна, то при введении по ней одностороннего движения - скажем, в направлении от $A$ к $B$ - мы не смогли бы проехать из $B$ в $A$); поэтому установив по одной из этих дорог движение от $A$ к $B$, а по второй - от $B$ к $A$, мы сможем проехать от любого перекрестка до любого, отличного от него. Это простое рассуждение неожиданно «работает» и в общей ситуации. Предположим, что для всех городов, число перекрестков в которых не превосходит n, утверждение задача уже доказано; рассмотрим теперь новый город (пусть это и будет Зурбаган), имеющий $n+1$ перекресток. Рассмотрим два соседних из этих-перекрестков - перекрестки $A$ и $B$, соединенные улицей АВ. Ясно, что поскольку после введения на улице $AB$ (при ее ремонте) одностороннего движения - скажем, от $A$ к $B$ - проехать от $B$ к $A$ было возможно, то из перекрестка $B$ в перекресток $A$ ведет некоторая не включающая улицы $AB$ «цепочка» улиц. (Разумеется, эту «цепочку» можно считать не имеющей самопересечений - ведь если бы она дважды проходила через один и тот же перекресток $С$, то «цикл» между первым вхождением в С и последующим вхождением в ту же точку мы могли бы просто отбросить.) Таким образом, мы приходим к существованию в Зурбагане «кольца» s - замкнутой сети улиц, ведущей из $A$ в $B$, а затем (через ряд «промежуточных» перекрестков) - снова в $A$. Рассмотрим теперь условный город, план которого получается из плана Зурбагана «склеиванием» всех перекрестков нашего кольца $s$ в один перекресток $S$, из которого исходят все улицы, реально «упирающиеся» в кольцо $s$. Число перекрестков такого условного города меньше $n + 1$; поэтому, по предположению индукции, в нем можно ввести по всем улицам одностороннее движение с соблюдением требований задачи. Если мы затем оставим движение по всем не входящим в кольцо $s$ улицам таким же, каким оно было в этом условном «городе», а по кольцу s пустим движение в одном (безразлично каком!) направлении, то на всех улицах Зурбагана будет установлено одностороннее движение - и притом с любого перекрестка можно будет проехать в любой другой.