Bài toán cầu thang - Đề thi hsg, Toán quốc gia, quốc tế Toán lớp 6
BÀI TOÁN CẦU THANG
Step: bậc
Go up: đi lên
Way: cách
VD1: Một cầu thang có 9 bậc. A có thể bước lên trên 1 bậc hoặc 2 bậc mỗi lần. Hỏi có bao nhiêu cách để A bước hết cầu thang?
Bài giải: số cách bước lên một bậc bất kì bằng tổng số cách bước lên các bậc liên trước nó (trước 1 bậc hoặc 2 bậc)
Vậy có 55 cách.
VD2: Mỗi cầu thang có 9 bậc. A có thể bước lên trên 1 bậc hoặc 3 bậc mỗi lần. Hỏi có bao nhiêu cách để A bước lên bậc thang?
Bài giải: Số cách bước lên một bậc bất kì bằng tổng số cách bước lên các bậc liền trước nó. Vậy 19 cách
VD3: Một cầu thang có 9 bậc. A có thẻ bước lên trên 1 bậc hoặc 2 bậc mỗi lần. Bậc thứ 5 bị hỏng nên không thể bước lên được. Hỏi có bao nhiêu cách để bước hết cầu thang?
Bài giải: 15 cách
BÀI TƯƠNG TỰ
Bài 1: Một cầu thang có 6 bậc. A có thể đi 1 bậc hoặc 2 bậc mỗi lần. Hỏi có bao nhiêu cách để đi hết cầu thang?
Bài 2: Mỗi ngày A phải uống 1 hoặc 2 viên thuốc. Biết rằng A có tất cả 8 viên thuốc. Hỏi có bao nhiêu cách khác nhau để A uống hết số thuốc đó?
Bài 3: Mỗi ngày A phải làm 2 hoặc 3 bài tập. Biết rằng A có tất cả 9 bài tập. Hỏi có bao nhiêu cách khác nhau để A làm xong hết số bài tập đó?
Bài 4: Một cầu thang có 9 bậc. A có thể đi 1 bậc hoặc 2 bậc cùng một lúc . Bậc thang thứ 6 không thể đi bởi vì nó hỏng. Hỏi có bao nhiêu cách để A đi hết cầu thang?
HƯỚNG DẪN
Bài 1: Cầu thang 6 bậc, mỗi lần đi 1 hoặc 2 bậc
Gọi f(n) là số cách để đi hết cầu thang có bậc.
-
Công thức đệ quy:
f(n)=f(n−1)+f(n−2)
-
Với: f(0)=1(khoˆng bước naˋo)f(1)=1(chỉ 1 caˊch đi 1 bậc)
Áp dụng:
| n | f(n) |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
| 6 | 13 |
✅ Đáp án: 13 cách
Bài 2: 8 viên thuốc, mỗi ngày uống 1 hoặc 2 viên
Tương tự như Bài 1: mỗi bước là 1 hoặc 2 viên → giống bài toán cầu thang 8 bậc.
-
Gọi f(n) là số cách uống hết n viên:
f(n)=f(n−1)+f(n−2),f(0)=1,f(1)=1
Áp dụng:
| n | f(n) |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
| 6 | 13 |
| 7 | 21 |
| 8 | 34 |
✅ Đáp án: 34 cách
Bài 3: 9 bài tập, mỗi ngày làm 2 hoặc 3 bài
Gọi f(n) là số cách làm xong n bài, mỗi bước là 2 hoặc 3 bài:
-
Công thức đệ quy:
f(n)=f(n−2)+f(n−3)
-
Với: f(0)=1(laˋm xong roˆˋi)f(1)=0(khoˆng thể laˋm 1 baˋi vıˋ chỉ được 2 hoặc 3)f(2)=1(1 caˊch: 2)f(3)=1(1 caˊch: 3)
Tính tiếp:
| n | f(n) |
|---|---|
| 0 | 1 |
| 1 | 0 |
| 2 | 1 |
| 3 | 1 |
| 4 | f(2)+f(1)=1+0 = 1 |
| 5 | f(3)+f(2)=1+1 = 2 |
| 6 | f(4)+f(3)=1+1 = 2 |
| 7 | f(5)+f(4)=2+1 = 3 |
| 8 | f(6)+f(5)=2+2 = 4 |
| 9 | f(7)+f(6)=3+2 = 5 |
✅ Đáp án: 5 cách
Bài 4: Cầu thang 9 bậc, không đi vào bậc 6
Gọi f(n) là số cách đi đến bậc thứ n, tránh bậc 6.
-
Công thức cơ bản: f(n)=f(n−1)+f(n−2)
-
Với điều kiện: Không đi vào bậc 6 ⇒ f(6) = 0
Bắt đầu:
| n | f(n) |
|---|---|
| 0 | 1 |
| 1 | 1 |
| 2 | 2 = 1+1 |
| 3 | 3 = 2+1 |
| 4 | 5 = 3+2 |
| 5 | 8 = 5+3 |
| 6 | 0 |
| 7 | f(6)+f(5)=0+8 = 8 |
| 8 | f(7)+f(6)=8+0 = 8 |
| 9 | f(8)+f(7)=8+8 = 16 |
✅ Đáp án: 16 cách
✅ Tổng kết:
| Bài | Đáp án |
|---|---|
| 1 | 13 |
| 2 | 34 |
| 3 | 5 |
| 4 | 16 |
