Докажем сначала для $n=7$ городов утверждение а). Будем говорить, что два города эквивалентны, если из каждого из них можно проехать в другой. Тогда все 7 городов разобьются на группы эквивалентных между собой городов, причём из каждых двух групп одна «мажорирует» другую, в том смысле, что все дороги из одной группы ведут в другую. Рассмотрим случай, когда таких групп больше двух. Пусть $y$ — предпоследняя группа (рис. 1). Выбрав в группе $y$ любой город $Y$ и изменив направления всех дорог, соединяющих его с другими городами, мы получим искомое: из $Y$ можно теперь попасть в группу $a$, а из неё — в любой другой город; и наоборот, в $Y$ можно попасть из последней группы $z$, а в неё — из любого другого города. Осталось рассмотреть случай, когда групп всего две (рис. 2). Пусть в группе $a$ всего $x$ городов, в группе $b$ — $(7-x)$. Можно считать, что $x$ не меньше 4 (иначе заменим все стрелки на противоположные). Разберём три случая: 1) $x=4$; 2) $x=5$; 3) $x=6$. Впрочем, сразу заметим, что случай $x=5$ невозможен, поскольку группа не может состоять из двух эквивалентных городов.
Для дальнейшего удобно использовать такую лемму:
В группе из любого числа $k\gt 3$ эквивалентных городов всегда существует замкнутый путь, проходящий (по направлению стрелок) через все города по разу («гамильтонов цикл»).
Доказательство леммы приведено в конце решения.
Рассмотрим оставшиеся случаи. 1) При $x=4$ группа выглядит так, как показано на рисунке 3 (направление шестой, непоказанной дороги несущественно). В качестве нужного города надо выбрать $C$. 3) При $x=6$ группа $a$ выглядит так, как показано на рисунке 4 (направление других дорог пока не существенно). Предполагая, что не существует города, при изменении направлений всех дорог в котором можно будет доехать из него до любого города из группы $a$, можно заключить, что дороги направлены так, как показано на рисунке 5. Но тогда в качестве нужного города можно выбрать любой из шести городов.
Итак, для $n=7$ утверждение задачи а) доказано.
При $n\gt 7$ его можно доказать методом индукции. Прежде всего, выберем из городов такой, в который входит не менее двух дорог и из которого выходит не менее двух дорог. (Если такого города нет, то имеется 4 города, в каждый из которых входит не более одной дороги, или 4 города, из которых выходит не более одной дороги. Но это невозможно, поскольку у шести дорог между четырьмя городами 6 «начал» и 6 «концов».) Среди оставшихся $(n-1)$ городов по предположению индукции есть такой, «обращением» всех дорог в котором можно добиться желаемого эффекта. Он же, очевидно, годится и для всех $n$ городов.
Рисунок 6 показывает, что для $n=6$ городов утверждение неверно, т. е. ответ на вопрос б) отрицателен. (Интересно, что этот пример единственный, как говорят, с точностью до изоморфизма.)
В заключение докажем лемму о гамильтоновом цикле (для $k=3$ городов она очевидна). Будем рассуждать по индукции. Удалим любой из $k\gt 3$ городов — город $X$. Если оставшиеся $(k-1)$ городов после этого образуют несколько групп эквивалентности (как на рисунке 1, причём некоторые стрелки из группы $z$ идут в $X$, а из $X$ — в группу $a$), то поскольку в каждой из групп $a$, $b$, $\ldots$, $y$, $z$ по предположению индукции есть гамильтонов цикл, на них очевидно составляется гамильтонов цикл, проходящий через все $k$ городов. Если же оставшиеся $(k-1)$ городов образуют одну группу эквивалентности, то в ней есть гамильтонов цикл, причём среди дорог, соединяющих эти города с $X$, есть как входящие в $X$, так и выходящие из него. Проходя по этому циклу, мы можем найти два соседних города таких, что из первого идёт дорога в $X$, а во второй — приходит дорога из $X$ (рис. 7). Таким образом, мы можем включить $X$ в этот цикл.
Заметим, что с помощью этой леммы можно доказать утверждение а) сразу для любого $n$, большего 7, — примерно так, как это сделано выше для $n=7$ городов.
Рисунок номер 1
Рисунок номер 2
Рисунок номер 3
Рисунок номер 4
Рисунок номер 5
Рисунок номер 6
Рисунок номер 7
