МОШ 2025, 11 класс, задача 6

Ответ: .

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

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

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

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

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

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

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

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