2014-06-08
Доказать, что квадратную доску размером $2n \times 2n$, где $n$ не делится на 3, из которой удалена одна произвольная клетка, можно покрыть правильными тримино. (Правильное тримино - это квадрат размером $2 \times 2$, из которого удалена одна клетка.)
Решение:
рис.1
рис.2
рис.3
рис.4
Заметим, что прямоугольник $3 \times 2$ можно покрыть тримино (рис. 1). Поэтому, если выкинутая клетка не лежит в фигуре, являющейся объединением полос шириной в шесть клеток, прилегающих к двум смежным сторонам квадрата, то мы можем покрыть эту фигуру прямоугольниками $3 \times 2$ (рис. 2) и перейти к оставшемуся квадрату $2(n - 3) \times 2(n - 3)$ с выкинутой клеткой. Так как такую операцию всегда можно проделать при $n \geq 7$, то без ограничения общности можно считать, что $n \leq 5$. Рассмотрим все возможные случаи.
1) $n = 1$. Квадрат $2 \times 2$ без одной клетки покрывается одним тримино.
2) $n = 2$. Выкинутая клетка лежит в одном из четырех квадратов $2 \times 2$, три оставшиеся клетки которого покрываются одним тримино (рис.3).
3) $n = 4$. Воспользуемся тем, что, как было показано в случае 2), квадрат $4 \times 4$ с любой выкинутой клеткой можно покрыть тримино (рис. 4).
4) $n = 5$. Квадрат $10 \times 10$ выкинутой клеткой всегда можно разбить на два прямоугольника $3 \times 10$ и один прямоугольник $4 \times 10$ так, чтобы выкинутая клетка лежала в прямоугольнике $4 \times 10$. Прямоугольник $3 \times 10$ покрыть тримино можно. Прямоугольник $4 \times 10$ можно разбить на два прямоугольника $3 \times 4$ .и один квадрат $4 \times 4$ так, чтобы выкинутая клетка лежала в квадрате $4 \times 4$. И прямоугольник $3 \times 4$, и квадрат $4 \times 4$ с выкинутой клеткой можно покрыть тримино.