Разделы 
Дополнительно
Задача по математике - 1984
2019-01-22 
В городе несколько площадей. Некоторые пары площадей соединены улицами с односторонним движением так, что с каждой площади можно выехать ровно по двум улицам. Докажите, что город можно разделить на 1014 районов так, чтобы улицами соединялись только площади из разных районов, и для любых двух районов все соединяющие их улицы были направлены одинаково (либо все из первого района во второй, либо наоборот).
Решение:
Сначала докажем, что если с любой площади выходит не более двух улиц, то площади можно покрасить в 13 цветов так, чтобы ни с какой площади нельзя было попасть на площадь того же цвета, проехав менее трех улиц. Для этого рассмотрим следующий вспомогательный ориентированный граф: его вершинами будут площади, а ориентированными ребрами будут соединены пары площадей, между которыми в нашем городе есть путь, проходящий не более, чем по двум улицам. Легко видеть, что в этом графе из каждой вершины выходит не более 6 ребер. Нужно доказать, что вершины этого графа можно раскрасить в 13 цветов правильным образом.
Это утверждение легко доказывается индукцией по числу вершин. Действительно, в случае, если вершин не больше 13, утверждение очевидно. Далее, легко видеть, что если в ориентированном графе из каждой вершины выходит не более 6 ребер, то существует вершина, в которую входит не более 6 ребер. Удалив из графа эту вершину, мы получим граф, удовлетворяющий нашему условию и содержащий меньшее число вершин. По индуктивному предположению, мы можем раскрасить вершины этого графа в 13 цветов, после чего удаленную вершину мы также можем покрасить в один из цветов, так как она соединена не более, чем с 12 вершинами.
Теперь для каждого цвета разделим все площади данного цвета на 78 типов, в зависимости от того, на площади каких цветов ведут улицы, выходящие с данной площади. Поскольку других цветов 12, для каждого цвета есть 12 вариантов, в которых обе улицы ведут на площади одного цвета, и $\frac{12 \cdot 11}{2} = 66$ вариантов, в которых они ведут на площади разных цветов. Итого, 78 вариантов. Таким образом, мы можем разбить все площади на $78 \cdot 13 = 1014$ районов.
Докажем, что полученное разбиение подходит. Пусть в районе $A$ есть площади $a_1$ и $a_2$, а в районе $B$ - площади $b_1$ и $b_2$ такие, что из $a_1$ выходит улица, ведущая на $b_1$), а из $b_2$ - на $a_2$. Тогда, поскольку площади $b_1$ и $b_2$ принадлежат одному району, из них выходят улицы, ведущие на площади одних и тех же цветов. Это означает, что из $b_1$ выходит улица, ведущая на площадь того же цвета, что и $a_2$, а следовательно, того же цвета, что и $a_1$. Таким образом, мы получили путь длины 2 между площадями одного цвета, что невозможно. Полученное противоречие завершает решение задачи.
В городе несколько площадей. Некоторые пары площадей соединены улицами с односторонним движением так, что с каждой площади можно выехать ровно по двум улицам. Докажите, что город можно разделить на 1014 районов так, чтобы улицами соединялись только площади из разных районов, и для любых двух районов все соединяющие их улицы были направлены одинаково (либо все из первого района во второй, либо наоборот).
Решение:
Сначала докажем, что если с любой площади выходит не более двух улиц, то площади можно покрасить в 13 цветов так, чтобы ни с какой площади нельзя было попасть на площадь того же цвета, проехав менее трех улиц. Для этого рассмотрим следующий вспомогательный ориентированный граф: его вершинами будут площади, а ориентированными ребрами будут соединены пары площадей, между которыми в нашем городе есть путь, проходящий не более, чем по двум улицам. Легко видеть, что в этом графе из каждой вершины выходит не более 6 ребер. Нужно доказать, что вершины этого графа можно раскрасить в 13 цветов правильным образом.
Это утверждение легко доказывается индукцией по числу вершин. Действительно, в случае, если вершин не больше 13, утверждение очевидно. Далее, легко видеть, что если в ориентированном графе из каждой вершины выходит не более 6 ребер, то существует вершина, в которую входит не более 6 ребер. Удалив из графа эту вершину, мы получим граф, удовлетворяющий нашему условию и содержащий меньшее число вершин. По индуктивному предположению, мы можем раскрасить вершины этого графа в 13 цветов, после чего удаленную вершину мы также можем покрасить в один из цветов, так как она соединена не более, чем с 12 вершинами.
Теперь для каждого цвета разделим все площади данного цвета на 78 типов, в зависимости от того, на площади каких цветов ведут улицы, выходящие с данной площади. Поскольку других цветов 12, для каждого цвета есть 12 вариантов, в которых обе улицы ведут на площади одного цвета, и $\frac{12 \cdot 11}{2} = 66$ вариантов, в которых они ведут на площади разных цветов. Итого, 78 вариантов. Таким образом, мы можем разбить все площади на $78 \cdot 13 = 1014$ районов.
Докажем, что полученное разбиение подходит. Пусть в районе $A$ есть площади $a_1$ и $a_2$, а в районе $B$ - площади $b_1$ и $b_2$ такие, что из $a_1$ выходит улица, ведущая на $b_1$), а из $b_2$ - на $a_2$. Тогда, поскольку площади $b_1$ и $b_2$ принадлежат одному району, из них выходят улицы, ведущие на площади одних и тех же цветов. Это означает, что из $b_1$ выходит улица, ведущая на площадь того же цвета, что и $a_2$, а следовательно, того же цвета, что и $a_1$. Таким образом, мы получили путь длины 2 между площадями одного цвета, что невозможно. Полученное противоречие завершает решение задачи.
