Задача 5. Доминошки и кресты

Что требуется и почему мало считать клетки

В задаче два разных вопроса. Для подходящих $n$ нужно предъявить разрезание — нарисовать его и проверить. Для остальных $n$ нужно доказать, что никакого разрезания нет, какие фигуры ни ставь.

Первое, что приходит в голову, — посчитать клетки. Пусть доминошек $a$, а крестов $b$ (по условию $a\ge 1$ и $b\ge 1$). Тогда $2a+5b=n^2$. Для $n=7$ это не запрещает ничего: $49=5\cdot 1+2\cdot 22$. Но попробуй на модели разрезать квадрат $7\times 7$ — каждый раз какая-то клетка остаётся отрезанной. Значит, нужна более тонкая причина, чем количество клеток.

Шахматная раскраска: что закрывает каждая фигура

Покрасим клетки квадрата в шахматном порядке: соседние по стороне клетки — разного цвета. Посмотрим, сколько клеток каждого цвета закрывает одна фигура.

• Доминошка — две соседние клетки, значит, одна чёрная и одна белая.

• Крест — центральная клетка и четыре её соседа по сторонам. Все четыре соседа другого цвета, чем центр. Поэтому крест закрывает либо $1$ чёрную и $4$ белые клетки, либо $4$ чёрные и $1$ белую.

Удобно следить за одной величиной — разностью «чёрных минус белых» среди клеток фигуры. У доминошки она равна $0$, у креста — $-3$ или $+3$. В любом случае эта разность делится на $3$.

Зачем это нужно: если квадрат разрезан на фигуры, то разность «чёрных минус белых» для всего квадрата равна сумме таких разностей по всем фигурам, ведь каждая клетка попала ровно в одну фигуру.

Нечётное $n$: разрезания нет

Пусть $n$ нечётное. Тогда в шахматной раскраске квадрата $n\times n$ все четыре угла одного цвета — назовём его чёрным — и чёрных клеток на одну больше, чем белых: всего клеток $n^2$ (нечётное число), чёрных $\dfrac{n^2+1}{2}$, белых $\dfrac{n^2-1}{2}$. Например, в квадрате $7\times 7$ чёрных $25$, белых $24$.

Допустим, квадрат всё же разрезан на доминошки и кресты. Сложим разности «чёрных минус белых» по всем фигурам: каждое слагаемое делится на $3$, значит, и сумма делится на $3$. Но эта сумма равна разности для всего квадрата, то есть $1$, а $1$ на $3$ не делится. Противоречие.

Итак, при нечётном $n$ квадрат нельзя разрезать на доминошки и кресты вообще — даже если не требовать, чтобы были фигуры обоих видов. В модели это видно по кнопке «Раскраска»: разность непокрытых чёрных и белых клеток начинается с $1$, доминошки её не меняют, кресты меняют на $3$, а в конце она должна стать $0$.

Чётное $n$: сначала квадрат $6\times 6$

Для чётного $n$ нужно предъявить разрезание. Начнём с наименьшего, $n=6$: $36=5\cdot 2+2\cdot 13$ — два креста и $13$ доминошек. Поставим два креста рядом в четвёртой строке, центрами в клетках $(4,\,2)$ и $(4,\,5)$: тогда вся четвёртая строка занята крестами, а сверху и снизу остаются куски, которые закрываются доминошками (рисунок ниже).

Проверим: кресты не накладываются, $13$ доминошек закрывают остальные $26$ клеток, $10+26=36$. Фигуры обоих видов есть. Такое разрезание не единственное: компьютерный перебор находит $28$ разрезаний квадрата $6\times 6$ с двумя крестами и ещё $2$ с четырьмя, но достаточно одного.

Как это найти самому: крестов мало и они «неудобные» — поставь их первыми и так, чтобы рядом с ними не осталось одиночных клеток, а доминошки доделают остальное.

От $6\times 6$ к любому чётному $n$

Пусть $n$ чётное и $n\ge 8$; тогда $n-6$ тоже чётное. Поставим квадрат $6\times 6$ с готовым разрезанием в левый верхний угол. Справа от него остаётся прямоугольник $6\times(n-6)$: его ширина чётная, поэтому каждую строку режем на горизонтальные доминошки. Снизу остаётся прямоугольник $(n-6)\times n$: его высота чётная, и каждый столбец режем на вертикальные доминошки (рисунок ниже для $n=8$). Фигуры обоих видов есть — кресты стоят в угловом квадрате.

Ответ: квадрат можно разрезать требуемым образом при всех чётных $n$, больших $5$, и ни при одном нечётном.