Задача М264‍‍

Прежде чем приступать к решению, отметим, что в условии задачи ссылка на рисунок 10 существенна — он является частью условия; так, например, для города, изображённого на рисунке 11 (с одной синей и $n$‍‍ зелёными площадями), все условия задачи выполнены, а утверждение — неверно: из части I нельзя проехать в часть II.

Перейдём теперь к решению нашей задачи. Разобьём доказательство на две части: докажем, что

а) от любой зелёной площади можно доехать до синей;

б) от синей площади можно доехать до любой зелёной.

Условимся обозначать направление движения на улицах стрелочками.

а) Предположим, что от зелёной площади $A_1$‍‍ нельзя доехать до синей площади. Поскольку уехать с площади $A_1$‍‍ можно, то от неё, проехав по одной улице, мы доедем до зелёной площади $A_2$‍.‍ От площади $A_2$‍‍ тоже нельзя доехать до синей площади. Выехав с неё, мы доедем до площади $A_3$‍;‍ потом $A_4$‍‍ и т. д. Поскольку всего зелёных площадей $n$‍,‍ проехав по $n$‍‍ улицам, мы вернёмся на площадь $A_1$‍‍ и убедимся, что стрелки в городе расставлены так, как на рисунке 12. Но тогда на синюю площадь нельзя приехать, что противоречит условиям задачи.

б) Изменим направления всех стрелок. Полученная схема движения удовлетворяет условиям задачи. Поэтому, как показано в пункте а), при этой расстановке стрелок от любой зелёной площади можно доехать до синей. Но это и означает, что при старой расстановке стрелок от синей площади можно доехать до любой зелёной.

Обобщить задачу Б. Розенштейна о городе с односторонним движением можно так. Пусть в городе нет «тупиков» (в таком случае можно расставить направления на улицах так, что на каждую площадь можно приехать и с каждой уехать). Необходимое и достаточное условие того, что при любой такой расстановке стрелок от каждой площади можно доехать до любой другой, можно сформулировать так: любые два кольцевых маршрута (по городу, на улицах которого ещё не расставлены стрелки) должны проходить через одну площадь. Докажите это.