Задача
COM-B1-M10-P024 Домино и L-тримино
Доску \(2\times6\) замощают домино и L-тримино. Найдите число замощений.
Введите два состояния: полная доска и доска с одной угловой дыркой справа.
Пусть \(A_n\) - число полных замощений \(2\times n\), а \(B_n\) - число замощений доски \(2\times n\) с одной удаленной угловой клеткой справа. Тогда \(B_n=A_{n-2}+B_{n-1}\): дырку можно закрыть L-тримино, оставив полный прямоугольник ширины \(n-2\), или продолжить состояние дырки на один столбец. Для полной доски \(A_n=A_{n-1}+A_{n-2}+2B_{n-1}\): последний блок - вертикальное домино, две горизонтальные домино или два симметричных способа закрыть правую часть L-тримино с дырочным состоянием. Начальные значения: \(A_0=1\), \(A_1=1\), \(B_0=0\), \(B_1=0\). Получаем \(B_2=1\), \(A_2=2\); \(B_3=2\), \(A_3=5\); \(B_4=4\), \(A_4=11\); \(B_5=9\), \(A_5=24\); \(B_6=20\), \(A_6=53\). Ответ: \(53\).
Сильная задача на дополнительные состояния; это уже настоящая динамика.