Các bài toán ứng dụng dãy Fibonacci?

Bài 1: Dân số thỏ (Bài toán gốc của Fibonacci)

Một cặp thỏ con (một đực, một cái) được đặt trong một cánh đồng. Giả sử:

Mỗi cặp thỏ sinh sản ra một cặp thỏ con mới (một đực, một cái) mỗi tháng, bắt đầu từ tháng thứ hai sau khi chúng được sinh ra.
Thỏ không bao giờ chết.

Hỏi có bao nhiêu cặp thỏ sẽ có sau $n$ tháng?

Bài 2: Lát gạch/Xếp gạch (Tiling Problem)

Có bao nhiêu cách khác nhau để lát một lối đi kích thước $1 \times n$ (chiều rộng 1 đơn vị, chiều dài $n$ đơn vị) bằng cách sử dụng: a) Các viên gạch kích thước $1 \times 1$ và $1 \times 2$ ? b) Các viên gạch kích thước $1 \times 1$ và $1 \times 3$ ? (Đây là một biến thể của Fibonacci, đôi khi dẫn đến dãy Tribonacci hoặc tương tự).

Gợi ý cho phần a):
- Nếu $n = 1$ , có 1 cách (gạch $1 \times 1$ ).
- Nếu $n = 2$ , có 2 cách (hai gạch $1 \times 1$ hoặc một gạch $1 \times 2$ ).
- Nếu $n = 3$ , có 3 cách (ba gạch $1 \times 1$ ; một gạch $1 \times 1$ và một gạch $1 \times 2$ ; hoặc một gạch $1 \times 2$ và một gạch $1 \times 1$ ).
- Hãy thử tìm mối liên hệ với Fibonacci.

Bài 3: Đường đi trên lưới (Paths on a Grid)

Một con kiến ở góc dưới bên trái của một lưới hình chữ nhật có kích thước $n \times m$ .

Con kiến chỉ có thể di chuyển sang phải hoặc lên trên.

a) Có bao nhiêu đường đi khác nhau từ góc dưới bên trái đến góc trên bên phải của lưới $1 \times n$ ?

b) Có bao nhiêu đường đi khác nhau từ góc dưới bên trái đến góc trên bên phải của lưới $2 \times n$ nếu con kiến không được đi qua một số ô nhất định (ví dụ: ô bị cấm ở góc)? (Bài này có thể phức tạp hơn và không hẳn luôn là Fibonacci trực tiếp, nhưng thường liên quan đến các kỹ thuật tương tự như quy hoạch động).

Gợi ý cho phần a): Bài toán này tương đương với bài toán lát gạch $1 \times n$ bằng gạch $1 \times 1$ .

Bài 4: Cầu thang (Staircase Problem)

Một người có thể đi lên một cầu thang gồm $n$ bậc bằng cách đi 1 bậc hoặc 2 bậc mỗi lần. Hỏi có bao nhiêu cách khác nhau để người đó đi hết cầu thang?

Gợi ý:
- Nếu $n = 1$ , có 1 cách (1 bước 1 bậc).
- Nếu $n = 2$ , có 2 cách (hai bước 1 bậc, hoặc một bước 2 bậc).
- Nếu $n = 3$ , có 3 cách (1+1+1; 1+2; 2+1).
- Hãy thử tìm mối liên hệ với Fibonacci.

Bài 5: Chuỗi nhị phân không có '00' (Binary Strings without Consecutive Zeros)

Có bao nhiêu chuỗi nhị phân (gồm các ký tự '0' và '1') có độ dài $n$ mà không chứa hai ký tự '0' liên tiếp?

Gợi ý:
- Xét chuỗi kết thúc bằng '1'. Phần còn lại của chuỗi có độ dài $n - 1$ và phải tuân thủ quy tắc.
- Xét chuỗi kết thúc bằng '0'. Chuỗi này phải bắt đầu bằng '10...' để tránh '00'. Khi đó, phần còn lại của chuỗi có độ dài $n - 2$ và phải tuân thủ quy tắc.
- Đây là một ứng dụng rất phổ biến của Fibonacci trong tin học.

Các bài toán ứng dụng dãy Fibonacci?