Реши

Краткий ответ: \(\boxed{109}\).

Пусть \(f(n)\) — число способов замостить прямоугольник \(3\times n\).

Рассмотрим его левый край:

1. Можно поставить вертикальный прямоугольник \(3\times1\). Это занимает 1 столбец.
2. Можно поставить квадрат \(3\times3\). Это занимает 3 столбца.
3. Можно поставить три горизонтальных прямоугольника \(1\times3\), по одному в каждой строке. Это тоже занимает 3 столбца.

Поэтому:

\[ f(n)=f(n-1)+2f(n-3), \]

где \(f(0)=f(1)=f(2)=1\).

Вычисляем:

\[ \begin{aligned} f(3)&=3,\\ f(4)&=5,\\ f(5)&=7,\\ f(6)&=13,\\ f(7)&=23,\\ f(8)&=37,\\ f(9)&=63,\\ f(10)&=f(9)+2f(7)=63+2\cdot23=109. \end{aligned} \]

Проверка по числу трёхстолбцовых блоков:

\[ \sum_{k=0}^{3}\binom{10-2k}{k}2^k =1+16+60+32=109. \]