Есть клетчатая доска размером 14×14 клеток, изначально белая. Назовём стикером квадрат размером 2×2 клетки, две противоположные угловые клетки которого чёрные, а две другие — белые. На доску наклеивают несколько стикеров (по линиям клеток) — стикеры могут перекрываться, при этом клетки, накрытые другим стикером, оказываются не видны. Какое наибольшее количество чёрных клеток может оказаться на доске?
-
Разобьём доску размером
на непересекающиеся квадраты размером клетки.
Всего таких квадратов: -
Рассмотрим каждый такой фиксированный квадрат
сетки разбиения: - Если внутрь этого квадрата вообще не попадают границы наклеенных стикеров (то есть стикеры либо покрывают его целиком, либо не покрывают вовсе), то верхний слой представляет собой либо исходную доску (
чёрных клеток), либо стикер (ровно чёрные клетки). - Если на этот квадрат частично накладываются другие стикеры, то верхний стикер (тот, который был наклеен позже всех остальных в своей области) не может быть перекрыт ничем сверху. Последний наклеенный стикер, задевающий клетки этого квадрата
, содержит в себе как минимум одну белую клетку стикера на каждые две клетки стикера одной строки/столбца.
- Если внутрь этого квадрата вообще не попадают границы наклеенных стикеров (то есть стикеры либо покрывают его целиком, либо не покрывают вовсе), то верхний слой представляет собой либо исходную доску (
Более строго, раскрасим доску
На любом стикере
- либо только на чёрных полях шахматной доски,
- либо только на белых полях шахматной доски.
Таким образом, стикер первого типа может сделать чёрными только клетки первого шахматного цвета, а стикер второго типа — только клетки второго шахматного цвета. Но стикер не может одновременно делать чёрными поля обоих шахматных цветов.
Рассмотрим любой квадрат
Проверим максимальную долю чёрных клеток:
Можно ли получить
Да, достаточно замостить всю доску
Покажем, что больше
В любом квадрате
Более того, в каждом столбце или строке при любом наложении стикеров невозможно получить более половины чёрных клеток, так как на любом стикере отношение чёрных клеток к белым равно
Действительно, стикер
Значит, на всей доске может быть не более:
Каждый стикер состоит из
