12-я Международная Жаутыковская олимпиада, 2016 год

В Графландии 60 городов, каждые два из которых соединены дорогой с односторонним движением. Докажите, что можно покрасить четыре города в красный цвет, а другие четыре — в зелёный так, чтобы каждая дорога, соединяющая красный город с зелёным, была направлена от красного к зелёному. ( А. Голованов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Скажем, что город $A$ обслуживает четвёрку городов $B_1$, $B_2$, $B_3$, $B_4$, если из него ведут дороги во все эти четыре города. Если всего из города выходит $k$ дорог, то он обслуживает $C_k^4$ четвёрок (мы считаем $C_k^4=0$ при $k < 4$). Пусть количества дорог, выходящих из всех городов — $k_1$, $k_2$, $\ldots$, $k_{60}$. Сумма этих количеств равна числу всех дорог $C_{60}^2= 30 \cdot 59$. Сумма количеств четвёрок, обслуживаемых всеми городами, равна $S = C_{{k_1}}^4 + C_{{k_2}}^4 + \ldots C_{{k_{60}}}^4$. Докажем, что наименьшее значение этой суммы при условии ${k_1} + {k_2} + \ldots + {k_{60}} = 30 \cdot 59$ равно $30 \cdot C_{30}^4 + 30 \cdot C_{29}^4$. Действительно, множество наборов целых неотрицательных $k_i$ c суммой $30\cdot 59$ конечно, поэтому один из них доставляет наименьшее значение этой суммы. Предположим, что в этом наборе есть два числа $m \ge 4$ и $n$, для которых $m-n \ge 2$. Тогда замена $m$ и $n$ на $m-1$ и $n+1$ уменьшит нашу сумму (так как $C_m^4 + C_n^4 - C_{m - 1}^4 - C_{n + 1}^4 = C_{m - 1}^4 - C_n^3 > 0$). Таким образом, наименьшее значение суммы $S$ достигается для набора $k_i$, никакие два из которых не отличаются более, чем на $1$. Такой набор, очевидно, только один, и состоит из $30$ чисел, равных $30$ и $30$ чисел, равных $29$.
Итак, все $60$ городов вместе обслуживают не менее $30 \cdot C_{30}^4 + 30 \cdot C_{29}^4$ четвёрок. Но это число, как легко проверить, больше, чем $3 \cdot C_{60}^4$, то есть утроенное количество всех четвёрок. Поэтому есть четвёрка, которую обслуживают хотя бы четыре города, что и требовалось доказать.

Пусть $G$ -- это граф, состоящий из 60 городов, связанных дорогами с односторонним движением. Тогда каждое ребро $(u,v)$ в $G$ направлено от $u$ к $v$. Построим новый граф $G'$, в котором ребра направлены в обратном направлении. Тогда в $G'$ каждое ребро $(u,v)$ направлено от $v$ к $u$.

Теперь разобьем города $G$ на две части: $S$ и $T$, где $S$ состоит из 4 городов, а $T$ -- из остальных 56. Тогда в графе $G'$ каждое ребро $(u,v)$ из $S$ в $T$ указывает от $v$ к $u$.

Таким образом, мы покрасим 4 города в красный цвет, а остальные 56 -- в зеленый, так что каждая дорога, соединяющая красный город с зеленым, будет направлена от красного к зеленому. Это доказано.

Поздравляю с первым комментарием!