Задача 67462
|
|
 |
Условие
Петя красит каждую клетку доски $22 \times 22$ в чёрный или белый цвет так, чтобы клетки каждого цвета образовывали многоугольник. Затем Вася разрезает доску на двухклеточные доминошки. Петя стремится к тому, чтобы в итоге получилось как можно больше разноцветных доминошек, а Вася – к тому, чтобы их получилось как можно меньше. Наличие какого наибольшего числа разноцветных доминошек может гарантировать Петя, как бы ни действовал Вася? (Напомним, что граница многоугольника – замкнутая ломаная без самопересечений.)Решение
Решим задачу для прямоугольника $2m \times 2n,$ где $m,n$ – произвольные натуральные числа (в нашем случае $m=n=11$). Мы докажем, что ответом является число $1+(m-1)(n-1)$.Сначала покажем, что Петя может раскрасить доску так, чтобы при любом разрезании Васи получилось не менее чем $1+(m-1)(n-1)$ разноцветных доминошек. Покрасим прямоугольник шахматным образом в синий и красный цвета так, чтобы левая нижняя клетка была красной. Пете достаточно добиться того, чтобы в чёрном многоугольнике было на $1+(m-1)(n-1)$ больше синих клеток, чем красных. Действительно, тогда при любом разрезании на доминошки будет хотя бы $1+(m-1)(n-1)$ доминошек, в которых есть синяя клетка чёрного многоугольника, но нет красной (так как в каждой доминошке ровно одна синяя и ровно одна красная клетка), все такие доминошки будут чёрно-белыми. Занумеруем строки снизу вверх, а столбцы слева направо. Добиться такого перевеса синих клеток в чёрном многоугольнике Петя может, например, покрасив в точности следующие клетки в чёрный цвет: все клетки первого столбца, в остальных столбцах с номерами, дающими остаток $1$ от деления на $4$, – все клетки, кроме самой верхней, во всех столбцах с чётными номерами, кроме самого правого, – все синие клетки, во всех остальных столбцах – только самую нижнюю клетку (см. рис. ниже).
Теперь докажем, что как бы Петя ни раскрасил клетки, Вася сможет добиться того, чтобы разноцветных доминошек было не более чем $1+(m-1)(n-1)$. Назовём каёмкой множество всех клеток прямоугольника, прилегающих к границе. Достаточно доказать, что Вася всегда сможет разбить все клетки, отличные от клеток каёмки, на доминошки так, чтобы среди них было не более $(m-1)(n-1)$ разноцветных, и что он всегда сможет разрезать каёмку на доминошки так, чтобы среди них было не более одной разноцветной.
Сначала докажем первое из этих утверждений. Пусть Вася разрежет образуемый не каёмочными клетками прямоугольник $(2m-2)\times (2n-2)$ на квадраты $2\times 2,$ а затем каждый квадрат порежет на доминошки так, чтобы среди них была хотя бы одна одноцветная. Он действительно сможет так сделать, так как иначе какой-то квадрат $2\times 2$ покрашен шахматным образом, но тогда все четыре ребра клетчатой плоскости, проходящие через его центр, являются граничными для белого многоугольника, что невозможно. Таким образом, из этой части прямоугольника Вася получит не более $(m-1)(n-1)$ разноцветных доминошек.
Теперь докажем второе утверждение. Для этого достаточно доказать, что белые клетки каёмки образуют связное по сторонам множество клеток. Действительно, тогда в каёмке белые клетки представляют собой несколько последовательных клеток, и Вася может порезать всю каёмку на доминошки, порезав при этом всю белую часть на доминошки, за исключением, возможно, одной клетки (если в каёмке белых клеток нечётное количество). Таким образом, разрезав каёмку, Вася получит не более одной разноцветной доминошки.
Итак, докажем связность множества белых клеток каёмки. Клетки белого многоугольника образуют связное по сторонам множество клеток, поэтому достаточно доказать, что если между некоторыми двумя различными не соседними белыми клетками в каёмке есть путь $\gamma$ по белым клеткам, не содержащий других клеток каёмки, то между ними есть и путь по белым клеткам каёмки. Докажем это. Клетки пути $\gamma$ разбивают прямоугольник на две (необязательно связные по сторонам) части, между которыми нет путей по клеткам, не содержащих клеток пути $\gamma$. Значит, $\gamma$ разбивает каёмку на две связные части, только в одной из которых могут быть чёрные клетки (так как чёрные клетки сами образуют связное по сторонам множество клеток, не содержащее клеток пути $\gamma$). Следовательно, одна из частей каёмки полностью белая, и поэтому между рассмотренными белыми клетками каёмки есть путь по белым клеткам каёмки.
