Câu 2. Người ta muốn lát kín một bảng ô vuông kích thước $3\times 13$ (3 hàng 13 cột) bằng các tấm bìa kích thước $1\times 2$ và $1\times 3$ sao cho các tấm bìa không được chồng lên nhau hay phủ ra ngoài bảng. Có bao nhiêu cách lát nếu ta được phép xoay các tấm bìa nhưng cạnh dài của tất cả các tấm bìa đều phải song song với nhau (số lượng mỗi loại tấm bìa không hạn chế)?

Theo bảng đáp án chính thức (Mã đề 0101, trang 9), Câu 2 (Phần III) có đáp số là $4097$.

Vì cạnh dài của tất cả các tấm bìa đều phải song song với nhau, có 2 trường hợp:
- TH1: Tất cả tấm bìa đặt thẳng đứng (kích thước theo cột là 2 hoặc 3). Chiều cao bảng là 3, nên chỉ có thể dùng các tấm $1\times 3$ đặt dọc phủ kín cả cột. Có đúng 1 cách lát cho toàn bộ 13 cột.
- TH2: Tất cả tấm bìa đặt nằm ngang (kích thước theo hàng là 2 hoặc 3). Ta cần lát từng hàng độ dài 13 bằng các đoạn độ dài 2 và 3.
Gọi $x_n$ là số cách lát hàng độ dài $n$ bằng các khối 2 và 3. Ta có công thức truy hồi: $x_n=x_{n-2}+x_{n-3}$.
Tính dãy: $x_1=0,x_2=1,x_3=1,x_4=1,x_5=2,x_6=2,x_7=3,x_8=4,x_9=5,x_{10}=7,x_{11}=9,x_{12}=12,x_{13}=16$.
Vì bảng có 3 hàng độc lập, số cách lát là $16^3=4096$.
Tổng số cách cho cả hai trường hợp: $1+4096=4097$ cách.