|
|
 |
Условие
В городе одна синяя площадь и n зелёных, причём каждая зелёная площадь соединена улицами с синей и с двумя зелёными, как показано на рисунке. На каждой из 2n улиц ввели одностороннее движение так, что на каждую площадь можно проехать и с каждой – уехать. Докажите, что с каждой площади этого города можно, не нарушая правил, доехать до любой из остальных.
Решение
Докажем, что
а) от каждой зелёной площади можно доехать до синей;
б) от синей площади можно доехать до любой зелёной.
Условимся обозначать направление движения на улицах стрелками.
а) Предположим, что от зелёной площади A1 нельзя доехать до синей площади. Поскольку уехать с площади A1 можно, то от неё, проехав по одной улице, мы доедем до зелёной площади A2. От площади A2 тоже нельзя доехать до синей площади. Выехав с неё, мы доедем до площади A3, потом до A4 и т.д. Проехав по n улицам, мы вернёмся на площадь A1 и убедимся, что стрелки в городе расставлены так, как на рисунке. Но тогда на синюю площадь нельзя приехать, что противоречит условию.
б) Изменим направления всех стрелок. Полученная схема движения тоже удовлетворяет условию. Поэтому, как показано в а), при этой расстановке стрелок от каждой зелёной площади можно доехать до синей. Но это означает, что при старой расстановке стрелок от синей площади можно было доехать до любой зелёной.
