Bài toán đếm số cách bước cầu thang

Ở các bài toán sau, mỗi lần người đó có thể bước một hoặc hai bậc.

Bài toán 1. Biết số bậc cầu thang là 2. Tìm số cách đi.

Giải. Người đó có thể bước theo các cách: 1 bậc – 1 bậc; 2 bậc. Tổng số cách đi là 2.

Đáp số: 2 cách.

Bài toán 2. Biết số bậc cầu thang là 3. Tìm số cách đi.

Giải. Người đó có thể bước theo 3 cách: 1 bậc – 1 bậc – 1 bậc; 1 bậc – 2 bậc; 2 bậc – 1 bậc.

Đáp số: 3 cách.

Bài toán 3. Biết số bậc cầu thang là 4. Tìm số cách đi.

Giải. 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.

Đáp số: 5 cách.

Bài toán 4. Biết số bậc cầu thang là 5. Tìm số cách đi.

Giải. Theo bài toán 3, để bước lên bậc 4 thì có 5 cách. Từ bậc 4, ta có 1 cách đi lên bậc 5.

Theo bài toán 2, để bước lên bậc 3 thì có 3 cách. Từ bậc 3, ta có 1 cách đi lên bậc 5 mà không đi qua bậc 4 (bước hai bậc). Ta không tính cách bước lên 1 bậc – 1 bậc vì như thế sẽ trùng với cách đi lên bậc 4 ở bài toán 3.

Ta có 5 + 3 = 8.

Đáp số: 8 cách.

Nhận xét. Ký hiệu số cách đi n bậc cầu thang là F(n).

Ta có F(1) = 1, F(2) = 2, F(3) = 3, F(4) = 5, F(5) = 8.

Trong trường hợp tổng quát, để đếm số cách đi, ta có thể liệt kê dãy số trên theo cách: Những số đứng sau bằng tổng của hai số đứng ngay trước nó. Ta có F(6) =

5 + 8 = 13, F(7) = 8 + 13 = 21, F(8) = 13 + 21 = 34.

Dãy số 1, 2, 3, 5, 8, 13, 21, 34... chính là dãy số Fibonacci quen thuộc.

Bài toán 5. Một ngôi nhà có 3 tầng, mỗi tầng có 8 bậc cầu thang. Hai người bước lên cầu thang, người thứ nhất luôn bước 2 bậc mỗi lần còn người thứ hai bước 3 bậc mỗi lần.

a) Tính số lần bước chân của mỗi người.

b) Tính số bậc cầu thang mà cả hai người cùng đặt chân.

Giải. Tổng số bậc khi đi từ tầng 1 lên tầng 2 là 8 + 1 = 9.

Tổng số bậc khi đi từ tầng 1 lên tầng 3 là 9 × 2 = 18.

Cách 1. a) Số lần bước chân của người thứ nhất là 18 : 2 = 9.

Số lần bước chân của người thứ hai là 18 : 3 = 6.

b) Những bậc thang hai người cùng đặt chân là một số chia hết cho cả 2 và 3: 6, 12, 18. Ta có 3 bậc trùng nhau.

Cách 2. Ta liệt kê số bậc mà hai người đặt chân là: 2, 4, 6, 8, 10, 12, 14, 16, 18; 3, 6, 9, 12, 15, 18.

Đáp số: a) 9, 6; b) 3.

Kết quả kỳ trước. Ta có [0, 9] = 1/9, [0, 9, 9] = 9/82, [0, 9, 9, 9] = 1/(9 + 9/82) = 82/747...

Kỳ này. Tương tự bài 5, thay 3 tầng bởi 5 tầng. Câu trả lời gửi về chuyên mục “Toán học, học mà chơi”, tòa soạn Báo Hànộimới, 44 Lê Thái Tổ, Hoàn Kiếm, Hà Nội.