Задание 2. Пол зала разбит на 4 × 4 квадратных клеток. В двух клетках, отмеченных на рисунке (в верхней строке — в крайней правой клетке, в нижней строке — во второй клетке слева), стоят колонны. Остальную часть пола покрывают плитками 1 × 2 клетки без наложений и зазоров. Плитки можно поворачивать. Сколькими способами можно уложить плитки?

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

После первой строки возможны три состояния: вертикальная плитка занимает одну из первых трёх клеток. После второй строки количества способов для состояний, занятых вертикальными плитками, равны: для первой клетки — 1, второй — 1, третьей — 1, четвёртой — 2.

После третьей строки количества способов для этих четырёх состояний составляют соответственно 3, 3, 3 и 2. В последней строке, с учётом колонны во второй клетке, завершить укладку можно только при состоянии, когда вертикальная плитка занимает первую клетку; такому состоянию соответствуют 3 способа.

Ответ: 3 способа.