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.