2019-04-29
В стране Дельфинии имеется $n$ городов, каждые два из которых соединены шоссе, причем движение по всем шоссе является односторонним. Доказать, - что если $n \neq 2$ или 4, го направления движения по шоссе можно выбрать так, чтобы из каждого города в любой другой можно было попасть с заездом не более чем еще в один город; если же $n = 2$ или 4, то так движение организовать нельзя.
Решение:
Ясно, что если в стране имеются 2 города, соединенные одним шоссе с односторонним движением по нему, то из одного города вообще не удастся попасть во второй. Если городов 4, то мы можем считать их вершинами четырехугольника $A_1A_2A_3A_4$; при этом либо движение по контуру четырехугольника является «циклическим» (рис. а), либо хоть одна из вершин - например, вершина $A_1$ - такова, что две проходящие через нее стороны четырехугольника изображают ведущие из города шоссе рис. б). Но в первом случае вершины четырехугольника равноправны и любой выбор направлений по диагоналям четырехугольника по существу не отличается от любого другого, а меж тем, на рис., а мы не можем с заездом в один лишь город проехать из $A_3$ в $A_2$. Если же шоссе $A_1A_2$ и $A_1A_4$ ведут из $A_1$ и то для того, чтобы мы могли с соблюдением требований задачи проехать из $A_2$ и из $A_4$ в $A_1$ направления движения на шоссе $A_2A_3$, $A_4A_3$ и $A_3A_1$, надо выбрать такими, как указано стрелками на рис. б; но при этом мы снова приходим к «симметричной» ситуации, позволяющей ограничиться рассмотрением варианта, отвечающего какому-то выбору направления движения по шоссе $A_2A_4$ - а в случае рис. б из $A_4$ в $A_2$ нельзя проехать с заездом в один лишь город. При $n = 3$ или 6 выбор направлений движения с соблюдением всех поставленных требований возможен (см. рис. а и б; на рис. б мы даже ограничились изображением не всех шоссе).
Далее воспользуемся методом математической индукции. А именно, пусть для некоторого числа $n$ городов утверждение задачи уже доказано; покажем, что тогда оно будет справедливо и для на 2 большего числа городов $n + 2$. Для этого направления движения на всех шоссе, соединяющих любые два из первых n городов $A_1, A_2, \cdots, A_n$, мы установим такими, чтобы из любого из этих городов в любой другой можно было проехать с заездом не более чем в один «промежуточный» город (это возможно в силу предположения индукции). Далее, по вcем шоссе, ведущим из $(n+1)$-го города $A_{n+1}$ в один из городов $A_1, A_2, \cdots, A_n$, направим движение в сторону городов $A_1, A_2, \cdots, A_n$, а из каждого из этих городов направим движение в сторону $(n + 2)$-го города $A_{n + 2}$ (рис.); тогда из $A_{n+1}$ в каждый из городов $A_1, A_2, \cdots, A_n$ и из каждого из этих городов в $A_{n+2}$ можно будет попасть без заездов в какой-либо другой город. Наконец, направим движение по соединяющему $A_{n+1}$ и $A_{n+2}$ шоссе от $A_{n+2}$ к $A_{n+1}$ - тогда из $A_{n+2}$ в $A_{n+1}$ мы попадем «за один шаг», а из $A_{n+2}$ в любой из городов $A_1, A_2, \cdots, A_n$ и из любого из этих городов в $A_{n+1}$ - за два «шага» (с заездом, соответственно, в $A_{n+1}$ или в $A_{n+2}$).
Так как утверждение задачи справедливо для $n = 3$ и для $n = 6$, то из доказанного следует, что оно также справедливо для всех нечетных $n \geq 3$ и для всех чётных $n \geq 6$.