Tính số cách lên cầu thang khi có 1 bậc bị hỏng

Một độc giả của fanpage Diễn đàn Toán học VN có hỏi bài toán sau.

Bài toán.


Một cầu thang có 11 bậc. Nam đi lên cầu thang bằng cách bước từng bậc hoặc 3 bậc mỗi lần. Biết rằng Nam không thể bước lên bậc thang thứ 6 vì nó đã bị hỏng. Hỏi có tất cả bao nhiêu cách để bạn Nam có thể đi lên cầu thang theo cách trên?

Lời giải 1. (Trần Công Băng)


Gọi $S(n)$ là số cách đi lên tới bậc thứ $n$.
Ta có:
$S(11)= S(10)+S(8) = S(9)+S(7)+S(8) \\= 2S(8)+S(7) = 2(S(7)+S(5))+ S(7)\\ = 3S(7)+2S(5) = 3S(4)+2S(5) \\ = 3S(4)+2(S(4)+S(2)) = 5S(4) + 2S(2) \\ = 5(S(3)+S(1)) + 2 S(2) = 5S(3) + 7S(1)$
Dễ thấy $S(3)=2, S(1)=1$.
Vậy $S(11)=5\times 2+7\times 1=17.$

Lời giải 2. (Minh Hoàng)


Nếu gọi $x$ là số lần bước 1, $y$ là số lần bước 3 thì ta có $x+3y=11$.

+Nếu $y=1$ thì chỉ có thể bước thang từ 4-7 hoặc 5-8 tức là có 2 cách

+Nếu $y=2$, cố định một bước 3 là 4-7 thì sẽ có 4C1 cách đặt bước 3 còn lại. Tương tự với cố định bước 5-8. Vậy sẽ có $2\times 4C1 = 8$ cách.

+Nếu $y=3$ nếu cố định bước 4-7 thì chỉ có $2\times 2 =4$ cách (2 cách 0-3 và 1-4 nhân với 2 cách 7-10 và 8-11). Tuy nhiên nếu cố định bước 5-8 thì bước 8-11 chắc chắn xảy ra nên có có 3 cách cho bước 3 còn lại là 0-3 , 1-4 và 2-5

Vậy có tất cả $2+8+4+3= 17$ cách lên cầu thang.
Theo FB MathVn. Người đăng: Mr. Math.

Đăng nhận xét

Please Select Embedded Mode To Show The Comment System.*

Mới hơn Cũ hơn