Задача: В клетчатом прямоугольнике 2 × 100 каждую клетку красят в белый или чёрный цвет. Доминошкой будем называть клетчатый прямоугольник 1 × 2 или 2 × 1. Оказалось, что существует единственный способ разбить данный прямоугольник 2 × 100 на доминошки так, чтобы каждая доминошка покрывала хотя бы 1 чёрную клетку. Какое наибольшее количество клеток могло быть покрашено в чёрный цвет?
Решение: Пусть прямоугольник \(2 \times 100\) разбит на доминошки. Двигаясь слева направо, понимаем, что горизонтальные доминошки объединяются в блоки \(2 \times 2\). Далее под блоком понимаем такой блок \(2 \times 2\) из двух горизонтальных доминошек. Назовём хорошим разбиение на доминошки, в котором в каждой доминошке хотя бы одна клетка чёрная. Назовём раскраску хорошей, если при ней существует ровно одно хорошее разбиение. 1) Приведём пример хорошей раскраски, в которой 120 чёрных клеток. Красим первый столбец белым, следующие 3 столбца — чёрным, пятый столбец — белым, и далее продолжаем с периодом 5. Тогда разобьём наш прямоугольник на прямоугольники \(2 \times 5\) и в каждом из них пусть слева и справа находятся блоки, а посередине — вертикальная доминошка. Видим, что получено хорошее разбиение. Покажем, что оно единственно. Посмотрим на границу между 5-м и 6-м столбцами. Эта граница не может находиться внутри блока, значит, эта граница обязательно должна присутствовать в разбиении и отрезать прямоугольник \(2 \times 5\). Далее продолжим аналогичные рассуждения с отрезанием прямоугольников \(2 \times 5\). Остаётся разобраться, как может быть устроено хорошее разбиение для прямоугольника \(2 \times 5\). В первом столбце не может быть вертикальная доминошка, поэтому в 1-м и 2-м столбцах точно находится блок. Аналогично в 4-м и 5-м столбцах находится вертикальный блок. Тем самым хорошее разбиение однозначно восстановлено. Обоснование того, что наша раскраска хорошая, завершено. 2) Оценка. Рассмотрим хорошее разбиение прямоугольника \(2 \times 100\). В каждом блоке не более двух чёрных клеток, иначе мы можем заменить две горизонтальные доминошки этого блока на вертикальные, и разбиение останется хорошим. В вертикальной доминошке может быть одна чёрная клетка или две чёрных клетки. В первом случае вертикальную доминошку назовём светлой, а во втором — тёмной. Если у нас \(k\) тёмных доминошек, то в них \(2k\) чёрных клеток, а остальная площадь \((200 - 2k)\) разбита на блоки и светлые доминошки, т.е. в ней не более половины площади занимают чёрные клетки. Итого чёрных клеток не более \(2k + (100 - k) = 100 + k\). Остаётся понять, что тёмных доминошек не более 20. Вертикальная доминошка не может граничить с тёмной доминошкой, иначе эту пару можно заменить на блок (из двух горизонтальных доминошек), и разбиение останется хорошим. Значит, граничить с тёмной доминошкой может только блок. К одному и тому же блоку слева и справа не могут примыкать две тёмные доминошки, иначе в образованном ими прямоугольнике \(2 \times 4\) можно заменить все доминошки на горизонтальные, и разбиение останется хорошим. Рассмотрим две ближайшие друг к другу тёмные доминошки. Промежуток (по горизонтали) между ними не может составлять 0, 1, 2 или 3 клетки (в последнем случае два блока, соседних с этими тёмными доминошками, должны пересекаться, что невозможно). Суммируя длины промежутков для \(k - 1\) пар ближайших тёмных доминошек, получаем, что количество вертикалей не менее \(k + 4(k - 1) = 5k - 4\). Но оно равно 100. Отсюда \(5k - 4 \leq 100\) и \(5k \leq 104\), что невозможно при \(k \geq 21\). Неравенство \(k \leq 20\) установлено. Доказательство оценки завершено.
Ответ: 120