Республиканская олимпиада по математике, 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}}$.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.