ВСОШ 2025, 10 класс, задача 8
( баллов) В клетчатом прямоугольнике каждую клетку красят в белый или чёрный цвет. Доминошкой будем называть клетчатый прямоугольник или . Оказалось, что существует единственный способ разбить данный прямоугольник на доминошки так, чтобы каждая доминошка покрывала хотя бы чёрную клетку. Какое наибольшее количество клеток могло быть покрашено в чёрный цвет?
(И. Лобацкий)
Ответ
Ответ. .
Решение. Пусть прямоугольник разбит на доминошки. Двигаясь слева направо, понимаем, что горизонтальные доминошки объединяются в блоки . Далее под блоком понимаем такой блок из двух горизонтальных доминошек.
Назовём хорошим разбиение на доминошки, в котором в каждой доминошке хотя бы одна клетка чёрная. Назовём раскраску хорошей, если при ней существует ровно одно хорошее разбиение.
1) Приведём пример хорошей раскраски, в которой чёрных клеток. Красим первый столбец белым, следующие столбца — чёрным, пятый столбец — белым, и далее продолжаем с периодом (см. рис. ).
Тогда разобьём наш прямоугольник на прямоугольники и в каждом из них пусть слева и справа находятся блоки, а посередине — вертикальная доминошка. Видим, что получено хорошее разбиение.
Покажем, что оно единственно. Посмотрим на границу между -м и -м столбцами. Эта граница не может находиться внутри блока, значит, эта граница обязательно должна присутствовать в разбиении и отрезать прямоугольник . Далее продолжим аналогичные рассуждения с отрезанием прямоугольников . Остаётся разобраться, как может быть устроено хорошее разбиение для прямоугольника . В первом столбце не может быть вертикальная доминошка, поэтому в -м и -м столбцах точно находится блок. Аналогично в -м и -м столбцах находится вертикальный блок. Тем самым хорошее разбиение однозначно восстановлено. Обоснование того, что наша раскраска хорошая, завершено.
2) Оценка.
Рассмотрим хорошее разбиение прямоугольника . В каждом блоке не более двух чёрных клеток, иначе мы можем заменить две горизонтальные доминошки этого блока на вертикальные, и разбиение останется хорошим.
В вертикальной доминошке может быть одна чёрная клетка или две чёрных клетки. В первом случае вертикальную доминошку назовём светлой, а во втором — тёмной. Если у нас тёмных доминошек, то в них чёрных клеток, а остальная площадь разбита на блоки и светлые доминошки, т. е. в ней не более половины площади занимают чёрные клетки. Итого чёрных клеток не более . Остаётся понять, что тёмных доминошек не более .
Вертикальная доминошка не может граничить с тёмной доминошкой, иначе эту пару можно заменить на блок (из двух горизонтальных доминошек), и разбиение останется хорошим. Значит, граничить с тёмной доминошкой может только блок. К одному и тому же блоку слева и справа не могут примыкать две тёмные доминошки, иначе в образованном ими прямоугольнике можно заменить все доминошки на горизонтальные, и разбиение останется хорошим (см. рис. ).
Рассмотрим две ближайшие друг к другу тёмные доминошки. Промежуток (по горизонтали) между ними не может составлять , , или клетки (в последнем случае два блока, соседних с этими тёмными доминошками, должны пересекаться, что невозможно). Суммируя длины промежутков для пар ближайших тёмных доминошек, получаем, что количество вертикалей не менее . Но оно равно . Отсюда и , что невозможно при . Неравенство установлено. Доказательство оценки завершено.
Только верный ответ.
Приведён верный пример раскраски с обоснованием существования и единственности хорошей раскраски.
В верном примере не доказана единственность хорошей раскраски.
Предъявлена только раскраска без хорошего разбиения.
Полностью доказана оценка .
Баллы за продвижения в оценке и примере суммируются.
Отсутствует доказательство того, что в разбиении на доминошки горизонтальные доминошки встречаются блоками «одна над другой».