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