|
|
 |
Условие
Докажите, что количество способов разрезать квадрат $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$, получаем утверждение задачи.
