Разделы 
Дополнительно
Задача по математике - 3396
2019-06-03 
В стране несколько городов, соединенных дорогами с односторонним и двусторонним движением. Известно, что из каждого города в любой другой можно проехать ровно одним путем, не проходящим два раза через один и тот же город. Докажите, что страну можно разделить на три губернии так, чтобы ни одна дорога не соединяла два города из одной губернии.
Решение:
Покажем, как разделить страну на губернии так, чтобы выполнялось условие задачи. Если в стране всего один город, то задача тривиальна: можно взять две губернии пустыми.
Назовем несколько городов страны автономной областью, если из каждого города этой автономной области можно проехать в любой другой город этой автономной области, не выезжая за ее пределы. (Легко видеть, что тогда для этой автономной области будет выполнятся условие задачи, т. е. такой путь, не проходящий два раза через один город, будет единственным.)
Возьмем произвольный город. Очевидно, он образует автономную область, и эту автономную область можно поделить на три губернии, как требуется в задаче. Будем последовательно увеличивать автономную область, добавляя к ней на каждом шаге несколько городов так, чтобы опять получалась автономная область, и деля полученную область на губернии, как требуется в задаче.
Предположим, что автономная область содержит не все города страны. Тогда найдется дорога, ведущая из города
области (обозначим его через $X$) в город, еще не принадлежащий этой области (назовем его $Y$). Действительно, если все дороги, выходя¬щие из городов автономной области, ведут в города этой области, то из городов области можно проехать только в города этой области. Рассмотрим несамопересекающийся путь (последовательность дорог, не проходящих два раза через один город), ведущий из $Y$ в $X$. Вообще говоря, он может до города $X$ проходить и через другие города области. Покажем, что это невозможно, т. е. на этом пути не могут встретиться другие города автономной области, кроме последнего города $X$.
Пусть $Z$ - первый город автономной области на пути из $Y$ в $X$. Предположим, что $Z$ и $X$ - разные города этой области. Так как для области выполнялось условие задачи, найдется несамопересекающийся путь из $X$ в $Z$, идущий только по городам области (рис.).
Но тогда из $X$ можно добраться до $Z$ двумя несамопересекающимися путями: не выезжая из области и через $Y$. Но по условию такое невозможно.
Следовательно, путь из $Y$ в $X$ не содержит других городов области, кроме $X$. Теперь присоединим все города на этом пути (включая $Y$) к автономной области и отнесем их поочередно в те две губернии, в которые $X$ не входит.
Заметим, что можно проехать из любого добавленного города в любой другой добавленный или в любой город области и наоборот, т. е. получилась опять автономная область. Докажем, что она правиль-но разделена на губернии. Так как из каждого города в любой другой можно проехать ровно одним путем, не проходящим два раза через один и тот же город, то все дороги, соединяющие присоединенные города, - это дороги на пути $Y \rightarrow X$. Аналогично, есть только две дороги, соединяющие какой-либо присоединенный город с городом, уже имевшимся в области - это дорога из $X$ в $Y$ и последняя дорога на пути $Y \rightarrow X$ (рис.). Поэтому нет дорог, соединяющих города из одной губернии. Следовательно, полученная область будет правильно разделена на губернии.
Действуя таким образом, пока есть хотя бы один город, не лежащий в автономной области, мы получим автономную область, совпадающую со всей страной, при этом она будет правильно разделена на губернии. Утверждение задачи доказано.
В стране несколько городов, соединенных дорогами с односторонним и двусторонним движением. Известно, что из каждого города в любой другой можно проехать ровно одним путем, не проходящим два раза через один и тот же город. Докажите, что страну можно разделить на три губернии так, чтобы ни одна дорога не соединяла два города из одной губернии.
Решение:
Покажем, как разделить страну на губернии так, чтобы выполнялось условие задачи. Если в стране всего один город, то задача тривиальна: можно взять две губернии пустыми.
Назовем несколько городов страны автономной областью, если из каждого города этой автономной области можно проехать в любой другой город этой автономной области, не выезжая за ее пределы. (Легко видеть, что тогда для этой автономной области будет выполнятся условие задачи, т. е. такой путь, не проходящий два раза через один город, будет единственным.)
Возьмем произвольный город. Очевидно, он образует автономную область, и эту автономную область можно поделить на три губернии, как требуется в задаче. Будем последовательно увеличивать автономную область, добавляя к ней на каждом шаге несколько городов так, чтобы опять получалась автономная область, и деля полученную область на губернии, как требуется в задаче.
Предположим, что автономная область содержит не все города страны. Тогда найдется дорога, ведущая из города
области (обозначим его через $X$) в город, еще не принадлежащий этой области (назовем его $Y$). Действительно, если все дороги, выходя¬щие из городов автономной области, ведут в города этой области, то из городов области можно проехать только в города этой области. Рассмотрим несамопересекающийся путь (последовательность дорог, не проходящих два раза через один город), ведущий из $Y$ в $X$. Вообще говоря, он может до города $X$ проходить и через другие города области. Покажем, что это невозможно, т. е. на этом пути не могут встретиться другие города автономной области, кроме последнего города $X$.
Пусть $Z$ - первый город автономной области на пути из $Y$ в $X$. Предположим, что $Z$ и $X$ - разные города этой области. Так как для области выполнялось условие задачи, найдется несамопересекающийся путь из $X$ в $Z$, идущий только по городам области (рис.).
Но тогда из $X$ можно добраться до $Z$ двумя несамопересекающимися путями: не выезжая из области и через $Y$. Но по условию такое невозможно.
Следовательно, путь из $Y$ в $X$ не содержит других городов области, кроме $X$. Теперь присоединим все города на этом пути (включая $Y$) к автономной области и отнесем их поочередно в те две губернии, в которые $X$ не входит.
Заметим, что можно проехать из любого добавленного города в любой другой добавленный или в любой город области и наоборот, т. е. получилась опять автономная область. Докажем, что она правиль-но разделена на губернии. Так как из каждого города в любой другой можно проехать ровно одним путем, не проходящим два раза через один и тот же город, то все дороги, соединяющие присоединенные города, - это дороги на пути $Y \rightarrow X$. Аналогично, есть только две дороги, соединяющие какой-либо присоединенный город с городом, уже имевшимся в области - это дорога из $X$ в $Y$ и последняя дорога на пути $Y \rightarrow X$ (рис.). Поэтому нет дорог, соединяющих города из одной губернии. Следовательно, полученная область будет правильно разделена на губернии.
Действуя таким образом, пока есть хотя бы один город, не лежащий в автономной области, мы получим автономную область, совпадающую со всей страной, при этом она будет правильно разделена на губернии. Утверждение задачи доказано.
