Задача М2098

Двое играют в игру, делая ходы по очереди: первый рисует на плоскости многоугольник, не налегающий на уже нарисованные, а второй ответным ходом раскрашивает его в один из 2008 цветов. Второй игрок хочет, чтобы любые два многоугольника, граничащие по отрезку сторны, имели разные цвета. Сможет ли первый игрок помешать ему?

Ответ: сможет

Решение

Докажем индукцией по $n$, что первый может играть так, что нарисованные им многоугольники будут давать в объединении некоторый многоугольник $P_{n}$, на границу которого выходят многоугольники не менее $n$ цветов. Отсюда будет следовать, что никакого конечного числа цветов недостаточно.

База индукции очевидна. Пусть утверждение верно для $n=k$, докажем его для $n=k+1$. Из предположения индукции следует, что первый игрок может играть так, чтобы нарисованные многоугольники давали в объединении $k$ многоугольников $P_{k}^{(1)},P_{k}^{(2)},’cdots,P_{k}^{(k)}$, на границу каждого из которых выходят многоугольники не менее $k$ цветов. На границе многоугольника $P_{k}^{(1)}$ выделим отрезок $Delta_{1}$ некоторго цвета 1, на границе многоугольника $P_{k}^{(2)}$ выделим отрезок $Delta_{2}$ некоторго цвета 2, отличного от 1, и т.д., на границе многоугольника $P_{k}^{(k)}$ выделим отрезок $Delta_{k}$ некоторго цвета k, отличного от уже определенных цветов $1,2,cdots,k-1$. Пусть теперь первый нарисует многоугольник $P$, пересекающийся с многоугольником $P_{k}^{(i)}$ по части отрезка $Delta_{i}$ для всех $i=1,2,cdots,k$ (рис.). Второй игрок должен раскрасить многоугольник $P$ в цвет, отличный от цветов $1,2,cdots,k$. Тогда на границу многоугольника, являющего объединением многоугольников $P,P_{k}^{(1)},P_{k}^{(2)},cdots,P_{k}^{(k)}$, выходят не менее $k+1$ цветов. Переход индукции доказан.

Замечания

Строгое доказательство существования многоугольника $P$ из решения задачи далеко не просто (хотя интуитивно все очевидно), оно следует из известной топологической теоремы Жордана.

Отметим, что вопрос, поставленный в задаче, уже рассматривался в «Задачнике «Кванта»» для случая, когда первому игроку позволяется рисовать многоугольники лишь специального вида. Результат этой задачи интресно сопоставить также со знаменитой теоремой о четырех красках, согласно которой для раскрашивания правильным образом любой карты на плоскости достаточно лишь четырех цветов.