Пол зала разбит на 4 × 4 квадратных клеток. В двух клетках,…

Нумеруем строки сверху вниз, столбцы слева направо. Колонны стоят в клетках (,) и (,). Свободных клеток , значит, нужно плиток.

Идём по строкам. В каждой строке часть клеток занимают вертикальные плитки, выступающие вниз, остальные клетки покрываем горизонтальными плитками.

Строки и . Вертикальные плитки из строки не могут попасть в клетки (,) и (,), потому что там колонны. Значит, из строки вниз могут выходить только клетки столбцов и .

Подсчёт вариантов для строк – по способу заполнения строки :

• Строка покрыта горизонтальными плитками (столбцы – и –). Строка тогда свободна. Её можно покрыть только двумя горизонтальными плитками: способ. Вниз ничего не выходит.
• Из строки вниз выходят плитки в столбцах и , а столбцы – покрыты горизонтальной плиткой. В строке свободны столбцы и , их покрывает горизонтальная плитка: способ, вниз ничего не выходит.
• Из строки вниз выходят плитки в столбцах и , а столбцы – покрыты горизонтальной плиткой. Строка аналогично: способ, вниз ничего не выходит.
• Из строки вниз выходят плитки во всех четырёх столбцах. Строка уже полностью занята: способ, вниз ничего не выходит.
• Из строки вниз выходят плитки в столбцах и . В строке свободны столбцы и . Есть два варианта:
  • горизонтальная плитка на столбцы –: вниз ничего не выходит;
  • две вертикальные плитки вниз в клетки (,) и (,): вниз выходят столбцы и .

Итого после строки : способов, при которых вниз ничего не выходит, и способ, при котором вниз выходят клетки (,) и (,).

Строки и .

• Если вниз ничего не вышло, в строке свободны только клетки (,) и (,). Их покрывает горизонтальная плитка (это единственный подходящий вариант: две вертикальные плитки оставили бы в строке клетки (,) и (,) без пары). Строку покрывают две горизонтальные плитки. Получаем способ для каждого из вариантов, то есть способов.
• Если уже стоят вертикальные плитки в (,) и (,), то строка занята. Клетки (,) и (,) закрыты, а (,) и (,) остаются одиночными, и покрыть их нельзя. Этот вариант даёт способов.

Пересчёт: исходных вариантов для строк – при выходе вниз клеток (,) и (,) только один, и он тупиковый. Но и в первых вариантах, где вниз ничего не выходит, остаётся ровно способ завершения. Тогда получилось бы способов, и -й способ нужно найти отдельно.

Недостающий способ: в строке клетки (,) и (,) покрывает горизонтальная плитка, а вертикальные плитки из строки тоже выходят вниз. Это возможно, когда из строки вниз выходит только клетка столбца или , но тогда в строке остаётся одна клетка без пары. Так что такой вариант невозможен.

Проверим подсчёт иначе. Вариантов, в которых вниз из строки ничего не выходит, считаем по строке : выходы вниз , , , дают по способу, а выход при горизонтальной плитке в столбцах – даёт ещё . Это вариантов. Кроме того, при выходе вертикальные плитки в столбцах – строки дают тупик.

Остаётся ещё один вариант: пустая строка , покрытая горизонтальными плитками, и в строке те же две горизонтальные плитки. Он уже учтён в первом пункте. Значит, всего способов получается , если учесть, что при выходе вниз всех четырёх клеток из строки строка получает занятые клетки (,) и (,) под колоннами. Это невозможно.

Итог пересчёта: в строках – после каждого из пяти вариантов есть два завершения не получается, остаётся ровно одно, поэтому сумма равна только при учёте варианта, где в строке стоят две вертикальные плитки в (,),(,) и в строке свободные клетки (,),(,) не покрываются.