Математикадан республикалық олимпиада, 2013-2014 оқу жылы, 9 сынып


Өлшемі $2^n \times 2^n$ ($n \ge 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}}$.