Раскраски

Решим задачу для прямоугольника , где — произвольные натуральные числа. Мы докажем, что ответом является число

Сначала покажем, что Петя может раскрасить доску так, чтобы при любом разрезании Васи получилось не менее, чем разноцветных доминошек. Покрасим прямоугольник шахматным образом в синий и красный цвета так, чтобы левая нижняя клетка была красной. Пете достаточно добиться того, чтобы в чёрном многоугольнике было на больше синих клеток, чем красных. Действительно, тогда при любом разрезании на доминошки будет хотя бы доминошек, в которых есть синяя клетка чёрного многоугольника, но нет красной (так как в каждой доминошке ровно одна синяя и ровно одна красная клетка), все такие доминошки будут чёрно-белыми.

Занумеруем строки снизу-вверх, а столбцы слева-направо. Добиться такого перевеса синих клеток в чёрном многоугольнике Петя может, например, покрасив в точности следующие клетки в чёрный цвет: все клетки первого столбца, в остальных столбцах с номерами дающими остаток от деления на — все клетки, кроме самой верхней, во всех столбцах с чётными номерами, кроме самого правого, — все синие клетки, во всех остальных столбцах — только самую нижнюю клетку (см рисунок). Действительно, тогда в первом столбце синих и красных клеток одинаковое количество, в остальных столбцах с нечётными номерами красных клеток на одну больше, чем синих, а в каждом чётном столбце, кроме последнего, синих клеток на больше, чем красных, в последнем столбце синих на одну больше, чем красных, итого суммарно синих больше, чем красных, на клеток. При такой покраске как чёрные, так и белые клетки образуют многоугольник.

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

Теперь докажем второе утверждение. Для этого достаточно доказать, что белые клетки каёмки образуют связное по сторонам множество клеток. Действительно, тогда в каёмке белые клетки представляют собой несколько последовательных клеток, и Вася может порезать всю каёмку на доминошки, порезав при этом всю белую часть на доминошки, за исключением, возможно, одной клетки (если в каёмке белых клеток нечётное количество). Таким образом, разрезав каёмку, Вася получит не более одной разноцветной доминошки.

Итак, докажем связность множества белых клеток каёмки. Клетки белого многоугольника образуют связное по сторонам множество клеток, поэтому достаточно доказать, что если между некоторыми двумя различными не соседними белыми клетками в каёмке есть путь по белым клеткам, не содержащий других клеток каёмки, то между ними есть и путь по белым клеткам каёмки, далее это и докажем. Клетки пути разбивают прямоугольник на две (необязательно связные по сторонам) части, между которыми нет путей по клеткам, не содержащих клеток пути . Значит, разбивает каёмку на две связные части, только в одной из которых могут быть чёрные клетки (так как чёрные клетки сами образуют связное по сторонам множество клеток, не содержащее клеток пути ). Следовательно, одна из частей каёмки полностью белая, и поэтому между рассмотренными белыми клетками каёмки есть путь по белым клеткам каёмки.