Bài toán tính số cách lên cầu thang và lời giải

Bạn đọc Tuấn Kiệt của diễn đàn toán học VN có hỏi một câu hỏi tổ hợp về số cách lên cầu thang như sau: Bài toán . Một cầu thang có $20$ bậc...

Bạn đọc Tuấn Kiệt của diễn đàn toán học VN có hỏi một câu hỏi tổ hợp về số cách lên cầu thang như sau:

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$). 

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ó:

Áp dụng công thức này, ta được số cách lên cầu thang $20$ bậc là: $$A(20)=F_{21}=10946.$$

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.