Có một cầu thang gồm 15 bậc, bậc 5, 10 và 15 bị gãy và không được dừng lại. Có bao nhiêu cách để đi hết cầu thang này, nếu mỗi lần được phép đi bộ 1 hoặc 2 bước?
Có một cầu thang gồm 15 bậc, bậc 5, 10 và 15 bị gãy và không được dừng lại. Có bao nhiêu cách để đi hết cầu thang này, nếu mỗi lần được phép đi bộ 1 hoặc 2 bước?
– Số cách để lên bậc 1: 1 cách (1)
-Số cách để lên bậc 2: 2 cách (1-1;2)
-Số cách để lên bậc 3: 3 cách ( 1-1-1;1-2;2-1)
– Số cách để lên bậc 4: 5 cách (1-1-1-1;1-1-2;1-2-1;2-1-1;2-2)
Ta thấy dãy trên chính là dãy phibonaci: 1,2,3,5,8,13,21,34,55,89,144,…
+) Do bậc 5 vị gãy nên khi lên đến bậc 4 thì phải bước thêm 2 bước liền.
⇒ Để đến bậc 6 có 5 cách.
Tiếp tục áp dụng dãy phibonaci:
– Số cách để lên bậc 9 : 21 cách
⇒ Để đến bậc 11 có 21 cách
⇒ Số cách để lên bậc 14 ( hoặc đi hết cầu thang) là: 89 cách
Vậy có 89 cách để đi hết cầu thang
Ly gửi ạ:33
Do 1 lần chỉ được bước 1 hoặc 2 bước nên để bước lên bậc thứ 6 ta phải bước đến bậc thứ 4. Tương tự với các bậc còn lại.
Ta sẽ tính số cách bước từ bậc 1 đến bậc 4, số cách bước từ bậc 6 đến bậc 9, từ bậc 11 đến bậc 14.
Từ bậc 1 đến bậc 4 có 5 cách đi: 1 – 1 – 1 – 1, 2 – 1 – 1, 1 – 2 – 1, 1 – 1 – 2, 2 – 2.
Từ bậc 6 đến 9 có 3 cách đi: 1 – 1 – 1, 1 – 2, 2 – 1.
Từ 11 đến 14 có 3 cách đi: 1 – 1 – 1, 1 – 2, 2 – 1.
Tổng cộng có: 5x3x3 = 45 cách.