Пол зала разбит на 4×4 квадратных клеток. В двух клетках, отмеченных на рисунке, стоят колонны. Остальную часть пола покрывают плитками 1×2 клетки без наложений и зазоров. Плитки можно поворачивать. Сколькими способами можно уложить плитки?
(Колонны стоят в третьей строке сверху: в первой и в четвёртой клетках.)
Нумеруем строки сверху вниз, столбцы слева направо. Колонны стоят в клетках (
Строка
- клетки
, , , ; - клетки
, ; - клетки
, ; - клетки
, ; - никакие (плитки
и ).
Это
Строка
- Если в строке
заняты клетки , , , , или , , или , , то в строку ничего не опускается ( способ в каждом случае). - Если в строке
нет занятых клеток, свободные клетки , , , закрываются только плитками и . Опустить можно только пару и , но тогда клетки и останутся одинокими. Значит, ничего не опускается ( способ). - Если в строке
заняты клетки и , свободны клетки и . Есть два способа: горизонтальная плитка (ничего не опускается) или две вертикальные плитки (заняты клетки и в строке ).
Итого: «ничего не опускается» —
Строка
- Если они не заняты (
способов), нужна горизонтальная плитка . Вертикальные плитки вниз дали бы в строке свободные клетки и , которые не закрыть, так что этот вариант не подходит. Остаётся способов. - Если клетки
и уже заняты ( способ), то в строке больше ничего класть не нужно, и это способ.
Строка
Задачу удобно решать по строкам: для каждой строки считаем, какие клетки следующей строки занимают вертикальные плитки, и складываем способы.
