M2098

Задача М2098

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

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

Решение

М2098Докажем индукцией по 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 из решения задачи далеко не просто (хотя интуитивно все очевидно), оно следует из известной топологической теоремы Жордана.

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

Е.Гик, П.Кожевников

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *