Bài toán. Một cầu thang có $20$ bậc. Mỗi lần có thể bước lên một hoặc hai bậc. Hỏi có bao nhiêu cách lên cầu thang?
Lời giải 1. (Nguyễn Hữu Hồng)
Để lên tới bậc thang thứ $n$, ta có thể thực hiện theo hai cách sau:
Cách 1: Lên tới bậc $n-2$ rồi bước $1$ bước hai bậc.
Cách 2: Lên tới bậc $n-1$ rồi bước thêm $1 $ bước một bậc.
Như vậy: (Số cách lên tới bậc $n$) = (số cách lên tới bậc $n-2$) + (số cách lên tới bậc $n-1$).
Cách 1: Lên tới bậc $n-2$ rồi bước $1$ bước hai bậc.
Cách 2: Lên tới bậc $n-1$ rồi bước thêm $1 $ bước một bậc.
Như vậy: (Số cách lên tới bậc $n$) = (số cách lên tới bậc $n-2$) + (số cách lên tới bậc $n-1$).
Gọi $A(n)$ là số cách lên tới bậc thang thứ $n$ thì ta có:
$$A(n)=A(n-1)+A(n-2)$$
Và ta dễ dàng tính được $A(1)=1, A(2)=2.$
Như vậy $A(n)$ chính là số hạng thứ $n+1$ của dãy Fibonacci $(F_n).$
Theo công thức Binet, ta có:
Lời giải 2. (Ae Hero, Sơn Tùng Mai)
Có $11$ trường hợp sau:
TH1: toàn bộ đều là bước 1 bậc: có $1$ cách
TH2: 1 bước 2 bậc và 18 bước 1 bậc: $C_{19}^1$
TH3: 2 bước 2, 16 bước 1 : $C_{18}^2$
TH4: 3 bước 2, 14 bước 1 : $C_{17}^3$
...
TH10: 9 bước 2, 2 bước 1 : $C_{11}^9$
TH11: toàn bộ 10 bước 2 : có $1$ cách
Vậy số cách lên cầu thang là: $$1+ \sum\limits_{k=1}^{9} C_{20-k}^k +1=10946.$$
Xem thêm: DÃY FIBONACCI
Người đăng: MiR Math.