Tin tức tổng hợp : Lời giải bài toán “Khỉ bán chuối”

Trang chủ

Tin tức tổng hợp

Lời giải bài toán “Khỉ bán chuối”

Dân trí Chỉ sau 1 ngày Dân trí đăng tải bài toán “Khỉ bán chuối” đã nhận được hàng nghìn comment độc giả bình luận và đưa ra nhiều cách giải khác nhau rất thú vị. Dưới đây là lời giải của bài toán mà nhiều độc giả chờ đợi.

Bài Toán “Khỉ bán chuối” do bạn Nguyễn Đình Thành Công – trường ĐH Ngoại thương cung cấp đã được đề cập trong cuốn sách “Các bài giảng về toán cho Mirella” (trong Tủ sách Sputnik của Sputnik Education) của Giáo sư Nguyễn Tiến Dũng (Đại Học Toulouse). Ở đây, Giáo sư Dũng cũng đã đưa ra những phân tích rất thú vị về bài toán này.

Lời giải của bài toán cụ thể như sau:

Ký hiệu Dn là hợp của các đoạn đường mà khỉ đi qua (2n-1) lần: D1 tức là chỉ đi xuôi qua 1 lần, D2 tức là có 1 lần đi ngược lại qua đó, D3 tức là có 2 lần đi ngược lại qua đó...v..v..

Như có nhận xét từ trước, vì chỉ có 3000 quả chuối, vác xuôi 3 lần là hết, và số chuối càng ngày chỉ càng giảm đi chứ không nhiều lên, nên không có đoạn nào cần đi ngược lại quá 2 lần. Hơn nữa, nếu có đoạn nào mà chỉ đi ngược lại x lần (x= 0,1, …) thì tổng số chuối chở theo hướng xuôi qua đoạn đó là không quá 1000x quả, và như vậy ở các đoạn sau đoạn đó (tính về phía chợ) cũng không cần phải đi ngược lại quá x lần làm gì, mà chỉ cần đi ngược lại cùng lắm x lần là khuân được hết các quả chuối muốn khuân về phía chợ.

Lý luận trên có nghĩa là: tổng cộng đường đi của cách tối ưu gồm 3 phần D1, D2, D3, trong đó phần D3 là phần tính từ điểm xuất phát đến một một A nào đó, phần D2 là từ mốc A đến mốc B, và phần D1 là từ mốc B đến chợ.(Mỗi phần D1, D2, D3 là một đoạn thẳng, chứ không gồm nhiều đoạn đan xen kẽ nhau).

Để đỡ phải đưa ra ký hiệu mới, ta gọi luôn độ dài của đoạn D1 là D1 (tính theo km), và tương tự như vậy với D2, D3. Khi đó ta có:

Gọi số chuối mà khỉ mang được đến chợ là X.

Tính từ điểm mốc B, khỉ chỉ vác được 1000 chuối là cùng (vì không quay ngược lại để vác thêm) và sẽ ăn hết D1 chuối trước khi đến chợ, nên số chuối mang được đến chợ phải thỏa mãn bất đẳng thức

Normal

(Các số phía bên phải trong các bất đẳng thức trên, nếu không phải là số nguyên, thì có thể làm tròn lên trên thành số nguyên).

Bài toán bây giờ trở thành bài toán tối ưu có ràng buộc: tìm số nguyên X lớn nhất thỏa mãn các điều kiện (1), (2), (3), (4), (5). Cần giải hệ bất phương trình này để tìm ra X to nhất có thể và D1, D2, D3 tương ứng. Giải nó thế nào ?