Đáp án bài toán “Khỉ bán chuối” là gì?

Tổng: / 10 DởHay 

Rõ ràng là chỉ cần lộn ngược lại điểm ban đầu không quá 2 lần, vì mỗi lần là bê đi được 1000 quả chuối, và tổng cộng chỉ có 3000 quả. Trong các lần bê chuối đi về hướng chợ, khỉ càng cố gắng bê nhiều lên, thì chỉ có làm cho kết quả cuối cùng tốt lên hay vẫn thế, chứ không làm cho kết quả tồi đi được, vì mục đích là dịch chuyển chuối về hướng chợ được càng nhiều càng tốt. Và chỉ cần 3 lần cố gắng là bê được hết đống chuối từ điểm ban đầu đi về hướng chợ.

Thay vì nói đến số lần quay đầu, ta nói đến số lần mà khỉ đi qua mỗi khúc đường thì có lẽ dễ hình dung hơn: Ví dụ như là nếu khỉ quay đầu về điểm xuất phát 2 lần, thì tức là khúc đường đầu tiên được đi qua tổng cộng 5 lần: xuôi – ngược – xuôi – ngược – xuôi – ngược. Nếu chia toàn bộ chặng đường 1000km ra thành các khúc đường theo các điểm quay đầu, thì mỗi khúc như vậy có số lần mà khỉ đi qua là một số lẻ: số lần đi xuôi nhiều hơn số lần đi ngược đúng 1 lần.

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 đội 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ó:

(1) D_1 + D_2 + D_3 = 1000

và tất nhiên là

(2) D_1 \geq 0,D_2 \geq 0,D_3 = 1000- D_1 - D_2 \geq 0

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

(3) X \leq 1000 - D_1

Nếu tính từ điểm A, thì khỉ sẽ vác được cùng lắm là 2000 chuối (vì quay lại 1 lần), nhưng ăn mất số chuối 3 D2 + D1 trên đường đến đến chợ tính từ điểm đó, nên ta có

(4) X \leq 2000 - D_1 - 3D_2

Tương tự như vậy, tính từ điểm xuất phát ban đầu, số chuối mà khỉ ăn là D1 + 3D2 + 5D3, và ta có

(5) X \leq 3000 - D_1 - 3D_2 - 5D_3

(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 ?

Có một cách là, nhân các bất đẳng thức trên theo các hệ số dương nào đó, rồi cộng chúng vào với nhau, để được một bất đẳng thức trong đó chỉ còn có X mà không còn D1, D2, D3 nữa. Trước khi làm vậy, có thể loại bớt D3 đi cho đơn giản, bằng cách thay thế D_3 = 1000 - D_1 - D_2 theo đẳng thức (1). Khi thay thế như vậy, bất đẳng thứ (5) trở thành:

(5′) X \leq 4D_1 + 2D_2 - 2000

Lấy 2 lần bất đẳng thứ (4) cộng với 3 lần bất đẳng thức (5′), để loại đi D2, rồi cộng thêm với 10 lần bất đẳng thức (3) để loại nốt D1, ta được:

(10+2+3)X \leq 10 (1000 - D_1) + 2 (2000 - D_1 - 3D_2) + 3 (4D_1 + 2D_2 - 2000)
hay là

15 X \leq 8000
từ đó ta có

X \leq 8000/15 = 533.33

Vì X là số nguyên, nên giá trị cực đại mà X có thể nhận được là 533, đúng như cách lúc trước cho. Con số này ứng với D3=200, D2=333, D1 = 467