|
|
 |
Условие
В городе несколько площадей. Некоторые пары площадей соединены улицами с односторонним движением так, что с каждой площади можно выехать ровно по двум улицам. Докажите, что город можно разделить на 1014 районов так, чтобы улицами соединялись только площади из разных районов, и для каждых двух районов все соединяющие их улицы были направлены одинаково (либо все из первого района во второй, либо наоборот).
Решение
Сначала докажем, что площади можно покрасить в 13 цветов так, чтобы ни с какой площади нельзя было попасть на площадь того же цвета, проехав менее трёх улиц. Для этого рассмотрим вспомогательный ориентированный граф: его вершинами будут площади, а ориентированными рёбрами будут соединены пары площадей, между которыми в нашем городе есть путь, проходящий не более чем по двум улицам. Легко видеть, что в этом графе из каждой вершины выходит не более 6 рёбер. Нужно доказать, что вершины этого графа можно раскрасить в 13 цветов правильным образом.
Проведём индукцию по числу вершин. База: в случае, если вершин не больше 13, утверждение очевидно.
Шаг индукции. Так как из каждой вершины выходит не более 6 рёбер, то существует вершина, в которую входит не более 6 рёбер. Удалив из графа эту вершину, мы получим граф, удовлетворяющий нашему условию и содержащий меньшее число вершин. По индуктивному предположению, мы можем раскрасить вершины этого графа в 13 цветов, после чего удалённую вершину мы также можем покрасить в один из цветов, так как она соединена не более чем с 12 вершинами.
Теперь для каждого цвета разделим все площади данного цвета на 78 типов, в зависимости от того, на площади каких цветов ведут улицы, выходящие с данной площади. Поскольку других цветов 12, для каждого цвета есть 12 вариантов, в которых обе улицы ведут на площади одного цвета, и 12·11 : 2 = 66 вариантов, в которых они ведут на площади разных цветов. Итого 78 вариантов. Таким образом, мы можем разбить все площади на 78·13 = 1014 районов.
Докажем, что полученное разбиение подходит. Пусть в районе A есть
такие площади a1 и a2, а в районе B – такие площади b1 и b2, что из a1 выходит улица, ведущая на b1, а из b2 – на a2. Тогда, поскольку площади b1 и b2 принадлежат одному району, из них выходят улицы, ведущие на площади одних и тех же цветов. Это означает, что из b1 выходит улица, ведущая на площадь того же цвета, что и a2, а следовательно, того же цвета, что и a1. Таким образом, мы получили путь длины 2 между площадями одного цвета, что невозможно.
