Đề bài:
Pi là một cậu bé hiếu động. Mỗi buổi sáng, khi tỉnh dậy, cậu đều chạy từ lầu 2 xuống lầu 1, bật nhạc nhảy một điệu nhảy để thức cả nhà dậy.
Khi xuống cầu thang, Pi có thể bước 1 bậc hoặc 2 bậc theo một thứ tự tùy ý.
Nếu cầu thang có tất cả 19 bậc thì cậu bé Pi có tất cả bao nhiêu cách xuống cầu thang? Ví dụ nếu cầu thang chỉ có 4 bậc thì Pi có 5 cách xuống cầu thang: (1, 1, 1, 1); (1, 1, 2); (1, 2, 1); (2, 1, 1); (2, 2).
Lời giải:
Ta giải bài này bằng phương pháp dự đoán quy luật. Nếu cầu thang có 1 bậc thì Pi chỉ có 1 cách đi xuống: bước 1 bước 1. Nếu cầu thang có 2 bậc thì Pi có 2 cách bước: bước 2 bước 1 hoặc bước 1 bước 2. Nếu cầu thang có 3 bậc thì Pi có 3 cách bước: (1, 1, 1), (1, 2) hoặc (2, 1).
Thế nếu có 4 bậc thì sao? Mấy cách? 4 à? Không phải. Ngay trong đề bài đã cho ví dụ là nếu có 4 bậc thì có 5 cách mà. Vậy dãy số là 1, 2, 3, 5 chứ không phải là 1, 2, 3, 4.
Vậy với 5 bậc thì đáp số là mấy? Ta nhận thấy, với bước đi đầu tiên, Pi có 2 cách bước: hoặc bước 1 để còn 4 bậc phải bước (sau đó có 5 cách bước để hoàn thành việc đi xuống), hoặc bước 2 để còn 3 bậc phải bước (sau đó có 3 cách để hoàn thành việc đi xuống). Từ đó suy ra với 5 bậc thì ta có 5 + 3 = 8 cách bước.
Cứ lý luận như vậy, ta thu được bảng sau
| Số bậc | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Số cách | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
| Số bậc | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| Số cách | 144 | 233 | 377 | 610 | 987 | 1597 | 2584 | 4181 | 6765 |
Vậy đáp số là 6.765 cách.
Như vậy Pi có thể đi xuống nghe nhạc trong vòng 18 năm mà mỗi ngày đều xuống bằng một cách khác nhau.
Dãy số xuất hiện trong lời giải: 1, 2, 3, 5, 8, … được gọi là dãy số Fibonacci, là dãy số có nhiều tính chất thú vị và có nhiều ứng dụng trong thực tế.
TS Trần Nam Dũng
ĐH Khoa học Tự nhiên, ĐH Quốc gia TP HCM