Задача 5. Клетки без квадратов

Почему нужен отдельный довод о минимуме

Если мы нашли удачные вырезы, это доказывает только, что их достаточно. Чтобы доказать минимум, сначала выделим непересекающиеся квадраты $2\times2$: из каждого придётся вырезать свою клетку. Важно, чтобы ни в одном не было уже удалённого угла.

Нижняя оценка

Разобьём 100 строк на 50 полос по две. В первой и последней полосах выделим по 49 квадратов со столбцами $2$–$3$, $4$–$5$, …, $98$–$99$. Они не содержат углов. В остальных 48 полосах выделим по 50 квадратов со столбцами $1$–$2$, $3$–$4$, …, $99$–$100$. Все квадраты попарно не пересекаются. Поэтому дополнительно нужно удалить не меньше

клеток.

Строим вырезы строка за строкой

Строки нумеруем сверху вниз, столбцы слева направо. Четыре угла уже удалены; в счёт ниже они не входят.

• В строке 2 удалим клетки столбцов $3,5,\ldots,99$: 49 клеток.

• В каждой паре строк $(3,4),(5,6),\ldots,(97,98)$ в первой удалим столбцы $1,3,\ldots,97$, а во второй — только столбец 99. Это $49+1=50$ клеток на пару, всего $48\cdot50$.

• В строке 99 удалим столбцы $2,4,\ldots,98$: ещё 49 клеток.

Получили ровно $49+48\cdot50+49=2498$ дополнительных вырезов.

Почему не осталось целого 2×2

Любой квадрат $2\times2$ занимает две соседние строки и два соседних столбца. Посмотрим на объединение дырок в каждой паре строк.

Для строк 1–2 угловая дырка в столбце 1 и дырки в нечётных столбцах $3,5,\ldots,99$ перекрывают каждую пару соседних столбцов. Для любой пары от 2–3 до 97–98 объединение содержит все нечётные столбцы $1,3,\ldots,99$. Для строк 98–99 есть столбец 99 и все чётные от 2 до 98. Для строк 99–100 — чётные от 2 до 98 и угловые столбцы 1 и 100. Во всех случаях каждая пара соседних столбцов содержит дырку. Значит, целого квадрата $2\times2$ не осталось.

Оценка достигнута

Меньше 2498 дополнительных вырезов не хватает по непересекающимся квадратам, а наша конструкция использует ровно столько. Поэтому это минимум. Исследование 8×8 помогает увидеть рисунок, но вывод о 100×100 опирается на предыдущие общие доводы.