Республиканская олимпиада по математике, 2014 год, 9 класс


Из доски $2^n \times 2^n$ ($n \geq 3$) вырезали одну клетку. Докажите, что оставшуюся часть доски можно покрыть без наложений уголками из 3-х клеток по крайней мере $4^{3 \cdot 4^{n-3}}$ различными способами. ( Д. Елиусизов )
посмотреть в олимпиаде

Комментарий/решение:

Комментарии от администратора Комментарии от администратора №1.     Докажем требуемое по индукции.
1) База $n=3$. Для начала заметим, что квадрат $4 \times 4$ без одной клетки всегда можно замостить уголками как показано на рисунке ниже.

(Без ограничения общности можно считать, что вырезана клетка в $A$.)
Для таблицы $8 \times 8$, пусть вырезанная клетка находятся в $A'$.

Тогда этот квадрат целиком можно покрыть уголками, а оставшуюся часть разделим на уголки и шесть прямоугольников. Заметим, что каждый из шести прямоугольников $3 \times 2$ можно разделить на уголки двумя способами: и откуда получим $2^6 = 64$ способов покрытия.
2) Предположим, что есть по крайней мере $4^{3 \cdot 4^{n-3}}$ способов покрыть уголками таблицу $2^n \times 2^n$ без одной клетки.
3) Докажем утверждение для доски $2^{n+1} \times 2^{n+1}$. Разделим её на четыре квадрата $2^n \times 2^n$.
Пусть вырезанная клетка находится в $A$. Добавим один уголок как на рисунке ниже.

Тогда можно считать, что в $B$, $C$ и $D$ также вырезали по одной клетке. Следовательно, есть по крайней мере $4^{3 \cdot 4^{n-3}}$ способов покрытия для каждого из $A$, $B$, $C$ и $D$. Тогда общее количество способов для таблицы $2^{n+1} \times 2^{n+1}$ больше или равно $4^{3 \cdot 4^{n-3}} \cdot 4^{3 \cdot 4^{n-3}} \cdot 4^{3 \cdot 4^{n-3}} \cdot 4^{3 \cdot 4^{n-3}} = 4^{3 \cdot 4^{n-2}}$.