|
|
 |
Условие
Дано натуральное число $n > 1$. Что больше: количество способов разрезать клетчатый квадрат $3n \times 3n$ на клетчатые прямоугольники $1 \times 3$ или количество способов разрезать клетчатый квадрат $2n \times 2n$ на клетчатые прямоугольники $1 \times 2$?Решение
Дадим конструкцию отображения, каждому разбиению доски $2n \times 2n$ на доминошки сопоставляющего разбиение доски $3n \times 3n$ на триминошки.
Предположим, что задано некоторое разбиение доски $2n \times 2n$ на доминошки. Пронумеруем все вертикали числами от $1$ до $2n$ и все горизонтали числами от $1$ до $2n$. Сделает $n$ горизонтальных разрезов через горизонтали с четным номером и $n$ вертикальных разрезов через вертикали с четным номером. Получится доска $3n \times 3n$ (правда, разбитая на неравные клетки, но ничего страшного), далее её будем называть новой доской. Каждая отдельная клетка старой доски стала либо одной, либо двумя, либо четырьмя клетками новой (если соответственно нуль, одна или обе координаты старой клетки были четными числами). Доминошки после этой операции становятся либо триминошками, либо прямоугольниками $2 \times 3$. Так вот, разрежем каждый из этих прямоугольников $2 \times 3$ на две триминошки. Получим, наконец, некоторое разбиение доски $3n \times 3n$ на триминошки.
Докажем, что при этом из разных разбиений на доминошки получаются разные разбиения на триминошки. Предположим противное: пусть два различных разрезания на доминошки доски $2n \times 2n$ при построенном отображении становятся одним разрезанием на триминошки доски $3n \times 3n$. Поскольку разрезания на доминошки различны, существует клетка $A$ доски $2n \times 2n$, накрытая в этих разрезаниях доминошками по-разному. Но тогда после нашей операции то, во что превратится клетка $A$, т.е. 1, 2, или 4 клеточки, будет накрыто триминошками по-разному. Значит, и разрезания на триминошки разные, что противоречит предположению.
Тем самым, мы доказали, что разрезаний на триминошки не меньше, чем разрезаний на доминошки. Осталось предъявить хотя бы одно разрезание $3n \times 3n$ на триминошки, которое не получается из разрезания $2n \times 2n$ на доминошки. Проверьте, что подойдет любое разбиение на триминошки, в котором к правому нижнему углу, (т.е. образованному последними строкой и столбцом), примыкает горизонтальная триминошка, а на ней стоят три вертикальные (пример см. на рисунке ниже).
