BÀI TOÁN DÁN TƯỜNG - Học sinh giỏi lớp 10,11,12 - Toán tư duy quốc gia quốc tế

BÀI TOÁN DÁN TƯỜNG

Bạn A tìm mua được các miếng dán cùng loại, cùng màu và có cùng kích thước ×3m dùng để trang trí kín một mảng tường hình chữ nhật có kích thước là ×n (với là số nguyên dương, các kích thước có đơn vị là mét).

Mỗi miếng dán có thể dán ngang hoặc dọc sao cho đảm bảo không có miếng dán nào bị cắt và không có miếng dán nào chồng lên nhau. (Miếng dán và mảng tường cần trang trí có dạng như hình vẽ).

Miếng dán ×3: Một hình chữ nhật được chia làm 3 ô vuông nhỏ.
Mảng tường hình chữ nhật kích thước ×n: Một lưới gồm 3 hàng và cột.

CHỌN ĐÚNG SAI

1) Nếu mảng tường có kích thước ×2m thì bạn A phải dùng hai miếng dán và chỉ có duy nhất 1 cách dán là xoay dọc cả hai miếng dán.
2) Nếu mảng tường có kích thước ×3m thì bạn A phải dùng 3 miếng dán và chỉ có đúng 2 cách dán là xoay dọc cả 3 miếng hoặc xoay ngang cả 3 miếng.
3) Nếu mảng tường có kích thước ×6m thì bạn A sẽ có tất cả 4 cách dán.
4) Mảng tường thực tế bạn A cần dán có kích thước ×14m, khi đó bạn A có tất cả 129 cách dán.

BÀI TƯƠNG TỰ

Bài 1 (Xếp gạch $2 \times n$ )

Một sàn nhà hình chữ nhật kích thước $2 \times n$ (với $n$ là số nguyên dương) cần được lát kín bằng các viên gạch hình chữ nhật kích thước $1 \times 2$ . Các viên gạch có thể đặt ngang hoặc đặt dọc. Gọi $a_{n}$ là số cách lát kín sàn nhà kích thước $2 \times n$ . a) Tính $a_{1}, a_{2}, a_{3}$ . b) Lập công thức truy hồi cho $a_{n}$ . c) Tính số cách lát nếu sàn nhà có kích thước $2 \times 8$ .

Bài 2 (Xếp gạch $1 \times n$ với gạch $1 \times 1$ và $1 \times 2$ )

Có bao nhiêu cách để lát một con đường kích thước $1 \times n$ bằng các viên gạch kích thước $1 \times 1$ và $1 \times 2$ ? a) Tính số cách lát khi $n = 1, 2, 3$ . b) Lập công thức truy hồi cho số cách lát khi con đường có kích thước $1 \times n$ . c) Tính số cách lát khi con đường có kích thước $1 \times 10$ .

Bài 3 (Đi lên cầu thang)

Một người muốn đi lên một cái cầu thang có $n$ bậc. Mỗi bước, người đó có thể đi 1 bậc, 2 bậc hoặc 3 bậc. Gọi $b_{n}$ là số cách để người đó đi hết $n$ bậc thang. a) Tính $b_{1}, b_{2}, b_{3}$ . b) Lập công thức truy hồi cho $b_{n}$ . c) Tính số cách để đi hết cầu thang 7 bậc.

Bài 4 (Mã hóa nhị phân không có chuỗi '00')

Có bao nhiêu chuỗi nhị phân (chỉ gồm các ký tự '0' và '1') có độ dài $n$ mà không có hai ký tự '0' nào đứng cạnh nhau? a) Liệt kê các chuỗi khi $n = 1, 2, 3$ . b) Lập công thức truy hồi cho số chuỗi như vậy. c) Tính số chuỗi nhị phân có độ dài 8 thỏa mãn điều kiện trên.

Bài 5 (Xếp tháp Domino)

Có bao nhiêu cách để xây một tòa tháp có chiều cao $n$ bằng cách xếp các viên gạch domino kích thước $2 \times 1$ ? Các viên gạch có thể đặt ngang hoặc dọc. Giả sử tòa tháp có chiều rộng không đổi là 2 đơn vị.

BÀI TOÁN DÁN TƯỜNG - Học sinh giỏi lớp 10,11,12 - Toán tư duy quốc gia quốc tế