Một cầu thang có 10 bậc. David có thể đi lên 1 bậc hoặc 2 bậc mỗi bước. Biết rằng bậc thứ 5 không thể bước lên do nó đã bị hỏng. Hỏi có bao nhiêu cách để David đi hết cầu thang?

Đáp án: 25 cách

Giải thích các bước giải:

* Do bậc số 5 bị hỏng, nên để bước lên được bậc số 6 bắt buộc phải bước lên bậc số 4 sau đó bước 1 bước 2 bậc lên đến bậc số 6.

1) Để bước từ bậc số 1 lên bậc số 4, Người đó có thể bước theo 5 cách: 1 bậc – 1 bậc – 1 bậc – 1 bậc; 1 bậc – 1 bậc – 2 bậc; 1 bậc – 2 bậc – 1 bậc; 2 bậc – 1 bậc – 1 bậc; 2 bậc – 2 bậc.
2) Để bước từ bậc số 4 lên bậc số 6 chỉ có 1 cách bước (bước 1 bước 2 bậc).

3) Để bước từ bậc số 6 lên bậc số 10, tương tự có 5 cách (do từ bậc số 6 lên bậc số 10 có 4 bậc).

=> Tổng số cách bước là: 5x1x5=25 (cách)