Решения: Республиканская олимпиада, Заключительный этап

Республиканская олимпиада по математике, 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}}$ .