Задача 66483

Тема:    [ Разрезания (прочее) ]

Сложность: 5 Классы: 8,9,10,11

Условие

Автор: Чеканов Ю.В.

Докажите, что количество способов разрезать квадрат $999 \times 999$ на уголки из трёх клеток делится на $2^7$.

Решение

Для каждого разрезания квадрата на уголки определим соответствующее ему разрезание квадрата на уголки и прямоугольники $2 \times 3$ следующим образом. Посмотрим на разрезание $R$. Если в нем найдется уголок, примыкающий к сторонам квадрата и образующий вместе с еще каким-то уголком прямоугольник $2 \times 3$, заменим эти два уголка на прямоугольник. Проведем все возможные такие замены. Будем говорить, что мы получили предразрезание $\mathfrak{R}$, соответствующее разрезанию $R$. Заметим, что по каждому разрезанию мы строим единственное предразрезание: в самом деле, один уголок может входить только в один прямоугольник $2 \times 3$. В частности, отсюда следует, что если взять разрезание $R$ и заменить в нем два уголка, образующих прямоугольник $2 \times 3$, на два других уголка, дающих тот же прямоугольник (как на рисунке),

мы получим разрезание $R'$, имеющее то же самое предразрезание, что и $R$. Это означает, что предразрезанию $\mathfrak{R}$ соответствуют ровно $2^k$ разрезаний, где $k$ — число прямоугольников в предразрезании.

Докажем, что в каждом предразрезании хотя бы 4 прямоугольника. В самом деле, длина стороны нечетна, значит, к каждой стороне хотя бы один из уголков примыкает одной клеткой, причем один уголок не может одной клеткой примыкать к двум сторонам. Каждый из четырех таких уголков образует вместе с еще одним уголком прямоугольник $2\times 3$.

Теперь докажем, что количество предразрезаний с фиксированным $k$ делится на 8. У квадрата есть 8 движений: четыре поворота на $0^{\circ}$, $90^{\circ}$, $180^{\circ}$ и $270^{\circ}$ и четыре осевых симметрии: две относительно диагоналей, две относительно средних линий. Для каждого предразрезания $\mathfrak{R}$ рассмотрим его образы при этих движениях; если все 8 образов разные, то мы разбили множество предразрезаний с фиксированным $k$ на группы по 8. Предположим, что какие-то два образа совпали. Посмотрим на центральную клетку. Она покрыта уголком (здесь нам важно, что прямоугольники примыкали к границам, значит, до центра не дотягиваются). При движении центральная клетка переходит в себя, значит, и покрывающий ее уголок тоже. Это возможно в единственном случае: если движение является симметрией относительно диагонали, а уголок лежит центром на центральной клетке симметрично относительно этой диагонали. Но тогда посмотрим на клетку, дополняющую этот уголок до квадрата $2\times 2$, эта клетка снова на диагонали, значит, переходит в себя, значит, покрывающая ее фигура — тоже. Тогда это снова уголок (прямоугольники $2 \times 3$ не переходят в себя при симметрии относительно диагонали квадрата), он снова лежит симметрично относительно диагонали, у него снова есть такая клетка, и так далее. Строя такую последовательность уголков, мы упремся в угол квадрата и получим непокрытую клетку: противоречие.

Итак, мы доказали, что число предразрезаний с фиксированным $k \ge 4$ кратно 8, значит, и число соответствующих им разрезаний делится на $2^{3+k}$, то есть хотя бы на $2^7$. Складывая по всем возможным $k$, получаем утверждение задачи.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	81
Год	2018
класс
Класс	10
задача
Номер	6