Задача 2.1. Крестики на доске 7×9

Разрежем шесть строк на квадраты 3×3

Условие говорит, сколько крестиков в каждом квадрате $3\times3$, и ещё — сколько их всего: $24$. Чтобы связать эти числа, разрежем часть доски на квадраты $3\times3$, которые не налегают друг на друга. Тогда каждый крестик этой части попадёт ровно в один квадрат, и крестиков в ней будет $4$, умноженное на число квадратов.

Положим доску так, чтобы в ней было $7$ строк по $9$ клеток (если доску повернуть, рассуждение не изменится). Строки нумеруем сверху вниз от $1$ до $7$, столбцы — слева направо от $1$ до $9$.

Всю доску на квадраты $3\times3$ не разрезать: $7$ не делится на $3$. Зато строки $1$–$6$ образуют прямоугольник $6\times9$, а $6$ и $9$ делятся на $3$. Он разрезается на $2\cdot3=6$ квадратов $3\times3$ (см. рисунок). В каждом ровно $4$ крестика, поэтому в строках $1$–$6$ ровно $6\cdot4=24$ крестика. Но всего крестиков тоже $24$, и на строку $7$ не осталось ни одного. Значит, строка $7$ пустая.

Ещё две нарезки: пустые строки 1 и 4

Тот же приём работает и для других строк — нужно лишь, чтобы вне квадратов снова осталась одна строка.

• Строки $2$–$7$ — тоже прямоугольник $6\times9$, то есть шесть квадратов $3\times3$ и $24$ крестика. Значит, пустая строка $1$.
• Строки $1$–$3$ и строки $5$–$7$ — две полосы $3\times9$, каждая разрезается на три квадрата $3\times3$. В них $3\cdot4+3\cdot4=24$ крестика, значит, пустая строка $4$.

Итак, все $24$ крестика стоят в строках $2$, $3$, $5$ и $6$. До сих пор мы пользовались только квадратами $3\times3$. Теперь подключим условие про квадраты $5\times5$.

Квадрат 5×5 в строках 2–6

В квадрате $5\times5$ всего $25$ клеток. Требование «не менее $14$ пустых клеток» значит, что крестиков в нём не больше $25-14=11$. Найдём квадрат $5\times5$, в котором крестиков заведомо больше.

Возьмём квадрат $5\times5$ в строках $2$–$6$ и столбцах $1$–$5$. Почему его? Он захватывает все четыре строки с крестиками, а пустая строка $4$ проходит ровно через его середину. Значит, все его крестики стоят в двух полосках: в строках $2$–$3$ и в строках $5$–$6$.

Посчитаем верхнюю полоску: строки $2$–$3$, столбцы $1$–$5$. Вместе с пустой строкой $4$ под ней это прямоугольник $3\times5$. Разрезать его на квадраты $3\times3$ без наложений, как в шагах 1–2, не получится: $5$ не делится на $3$. Поэтому накроем его двумя квадратами $3\times3$, которые налегают по одному столбцу, а то, что посчитано дважды, потом вычтем. Левый квадрат — строки $2$–$4$, столбцы $1$–$3$, правый — строки $2$–$4$, столбцы $3$–$5$. В каждом ровно $4$ крестика, и все они стоят в полоске, ведь строка $4$ пустая. Сложим: $4+4=8$. Крестики в столбцах $1$–$2$ и $4$–$5$ мы посчитали по одному разу, а крестики в столбце $3$ — дважды: этот столбец входит в оба квадрата. У полоски в столбце $3$ всего $2$ клетки, поэтому лишнего мы насчитали не больше $2$. Значит, в верхней полоске крестиков не меньше

Нижнюю полоску (строки $5$–$6$) так же накрывают два квадрата: в строках $4$–$6$ и столбцах $1$–$3$ и $3$–$5$. В ней тоже не меньше $6$ крестиков.

Противоречие

Соберём оценки: в строках $2$–$3$ не меньше $6$ крестиков, в строке $4$ — ни одного, в строках $5$–$6$ — не меньше $6$. Значит, в выбранном квадрате $5\times5$ крестиков не меньше

Тогда пустых клеток в нём не больше $25-12=13$, а нужно не меньше $14$. Противоречие.

Мы ни разу не смотрели, где именно стоят крестики, — пользовались только условиями задачи. Поэтому противоречие получится при любой расстановке: выполнить все требования сразу нельзя.