9-я Международная Жаутыковская олимпиада, 2013 год

Таблица $10\times 10$ разбита на 100 единичных квадратиков. Назовем блоком любой квадрат $2\times 2$, состоящий из четырех единичных квадратиков этой таблицы. Множество $C$, состоящее из $n$ блоков, покрывает таблицу (т.е. каждый единичный квадратик таблицы накрыт некоторым блоком из $C$), но никакие $n-1$ блоков из $C$ эту таблицу не покрывают. Найдите наибольшее возможное значение $n$.

Комментарий/решение

$n=39$. Ключевая идея: разбить доску на центральный квадрат $6 \times 6$ и оставшуюся рамку. В рамке, как легко проверить, максимум $20$ блоков, а в квадрате $6 \times 6$ и на границе не более $19$ блоков. Действительно, разобьем доску $6 \times 6$ на $4$ квадрата $3 \times 3$. Из условия следует, что у каждого блока есть своя уникальная клетка. Несложно проверить, что в каждом квадрате $3 \times 3$ максимум $5$ уникальных клеток из различных блоков, значит в общем таких блоков не более $20$, но все условия не могут одновременно повторяться, поэтому их не более $19$.

Суммарно, наибольшее значение $n$ - $39$