Bài toán đếm số bước chân
Xã hội - Ngày đăng : 07:26, 11/12/2011
Ta hãy giải bài toán trên với các trường hợp đi từ đơn giản đến phức tạp, phụ thuộc vào giá trị tăng dần của số bậc thang n.
Với n = 1, có một cách đi là bước 1 bậc 1 lần.
Với n = 2, ta thấy có hai cách đi, biểu diễn dưới dạng số bước chân lần lượt là: 1 + 1, 2.
Với n = 3, ta có 3 = 1 + 1 + 1 = 1 + 2 = 2 +1. Tức là có 3 cách đi.
Với n = 4, ta có 4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = 2 + 2. Có tất cả 5 cách đi.
Khi n lớn một chút thì cách liệt kê như trên là rất dài và trong trường hợp tổng quát thì giải theo cách này cũng không hiệu quả. Vậy ta phải tìm ra một cách khác. Muốn vậy, ta tiếp tục thử liệt kê để tìm số cách đi với n lớn hơn. Với n = 5, có 8 cách đi. Với n = 6, có 13 cách đi. Liệt kê dãy số cách đi, tương ứng với n tăng dần từ 1, ta được: 1, 2, 3, 5, 8, 13.
Quy luật của dãy số có một vài trường hợp quen thuộc là số thứ n phụ thuộc vào n hoặc phụ thuộc vào một hay hai số trước nó. Ở đây ta thấy 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13. Ta dự đoán rằng đây là dãy số Fibônaxi (là dãy số mà kể từ số thứ ba, mỗi số bằng tổng hai số trước nó). Nhìn nhận dưới góc độ này, ta sẽ có một cách nhìn khác, ngắn gọn hơn cách liệt kê để tìm ra đáp số của bài toán trên. Chẳng hạn ta tìm đáp số cho n = 5 khi đã biết đáp số của bài toán với giá trị n là 1, 2, 3, 4. Để bước lên bậc thang thứ 5, cần xuất phát từ bậc thứ 4 hoặc thứ 3. Từ bậc 4 bước lên 1 bậc (cách 1). Từ bậc 3 bước 1 lần 2 bậc (cách 2) hoặc bước 2 lần 1 bậc, cách này trùng với cách 1. Nghĩa là không tính trùng nhau thì số cách đi với n = 5 bằng tổng số cách đi với n = 3 và n = 4. Đến đây, ta hoàn thành xong chứng minh dự đoán trên.
Bài toán sẽ khó hơn nếu ta thay giả thiết số bước chân mỗi lần sẽ là 1, 2 hoặc 3. Liệt kê dãy cách đi, tương ứng với n tăng dần từ 1, ta được: 1, 2, 4, 7... Bạn hãy tìm hiểu xem có đúng là trong dãy số này, mỗi số hạng, kể từ số thứ tư bằng tổng của ba số trước nó hay không nhé.
Bài tập kỳ này. Giải bài toán ban đầu với n = 9.
Bài giải gửi về Hoàng Trọng Hảo, Tạp chí Toán Tuổi thơ, 361 Trường Chinh, Thanh Xuân, Hà Nội. Ngoài phong bì ghi dự thi "Học mà chơi - chơi mà học" của Báo Hànộimới.