Các bài giảng về toán cho Mirella (9)

 

Lần này, papa lấy được từ internet về một bài toán đố vui sau cho Mirella:

Bài toán khỉ bán chuối

Có một con khỉ gorilla có 3000 quả chuối để đem bán cho một cái chợ ở cách chỗ nó những 1000 km. Mỗi lần khỉ chỉ bê được 1000 quả chuối thôi, và cũng không có ai giúp nó. Cứ đi được 1km thì khỉ ăn hết 1 quả chuối, bất kể là có đang vác bao nhiêu chuối trên người. (Lúc nào nó cũng phải có chuối để ăn, không đi tay không được 1km nếu không có chuối). Đến khi bán được chuối ở chợ rồi, thì khỉ không cần chuối để ăn trên đường về nữa (mà sẽ được nhận ở lại làm gác chợ hoặc cho đi lái máy bay chẳng hạn :D). Hỏi rằng con khỉ sẽ mang được đến chợ nhiều nhất là bao nhiêu quả chuối để bán?

Đây là một loại bài toán tối ưu. Khỉ phải nghĩ ra cách nào thông minh để mang được chuối đến chợ, chứ nếu vác 1000 quả chuối đi liền tù tỳ 1000km, thì đến được đến chợ đã ăn hết chuối chẳng còn quả nào để mà bán. Ta giả thiết rằng, trên đường đi đến chợ không có chỗ nào có sẵn chuối cho khỉ ăn, mà chỉ có các quả chuối mang từ nhà khỉ đi thôi. Hơn nữa, nếu khỉ có để chuối ở đâu đó giữa đường mà không trông, thì lúc sau quay lại vẫn còn chuối chứ không bị ai lấy mất, không thì chú khỉ tội nghiệp của ta chỉ còn cách ngồi nhà ăn chuối chứ không mất công bê đi bán nữa :D

Mirella nhận thấy rằng, khỉ phải có lúc để chuối giữa đường quay lại tìm tiếp chuối. Nhưng để lại những chỗ nào ? Sau một lúc suy nghĩ, Mirella đưa ra một cách sau:

Khi mang 1000 quả chuỗi, dọc đường cứ 1km thì thả 1 quả xuống đất và ăn 1 quả. Đi được 250km thì thả thêm 250 quả xuống, còn đem 250 quả đi ngược lại để vừa đi vừa ăn cho đến khi về đến chỗ cũ. Sau đó lại đem 1000 quả chuối, trên đường ăn những quả thả dưới đất. Như vậy đi được 250km vẫn còn 1000 quả, rồi đem 1000 quả này đi tiếp thêm 750km, sẽ ăn hết 750 quả và khi đến chợ còn được 250 quả ?

Cách trên của Mirella đã thông minh hơn con khỉ mang 1000 quả đi được đến chợ ăn hết cả 1000 quả, chẳng còn quá nào để bán rồi. Tuy nhiên khỉ còn để thừa lại lúc ban đầu 1000 quả, và ở chặng 250km để thừa ở đó thêm 250 quả nữa. Papa hỏi “thế khỉ làm gì với những quá đó”. Mirella trả lời “nó làm xiếc tung chúng lên trời!”

Bỏ qua chuyện “nói ngang” của Mirella, bạn đọc có thấy phương pháp của Mirella là tối ưu chưa, hay có thể làm cách khác tốt hơn?

Có một cách đơn giản để tối ưu hóa cách làm của Mirella là: lần đầu tiên khỉ đi, vẫn thả 1 quả chuối trên từng km, nhưng đi 333km thay vì chỉ đi 250 km rồi đi ngược lại về điểm xuất phát, không cần để lại quả chuối nào ở chỗ mốc 333km cả. Lần thứ hai khỉ đi, thì trên đoạn đường 333km đầu chỉ cần nhặt chuối lên ăn, vẫn còn nguyên 1000 quả khi đi hết 333km. Sau đó mới ăn mỗi km một quả đang đem theo, và khi đến được đến chợ thì cón 333 quả. Nhưng cách này đã tối ưu chưa?

Sau khi Mirella không chịu tìm thêm phương án khác, mà mải mê với việc “khỉ làm xiếc”, papa gợi ý cho Mirella một cách khác tốt hơn:

Đầu tiên là mang 1000 quả đi 200km, ăn mất 200 quả, để lại 600 quả, trên đường về ăn nốt 200 quả. Lặp lại như vậy 1 lần, để được thêm 600 quả. Đến lần thứ ba, thì đem nốt 1000 quả còn lại, đến mốc 200km còn 800 quả, cộng với 600+600 = 1200 quả đã để đó từ lúc trước, thành 2000 quả.

Từ mốc 200km, mang 1000 quả đi thêm 333km, ăn 333 quả, để lại 334 quả, còn 333 quả để ắn trên đường đi ngược lại về mốc 200km. Rồi mang nốt 1000 quả ở đó đi tiếp, khi được thêm 333km thì ăn thêm 333 quả. Đến được đến mốc 200+333=533km còn (1000-333) quả, nhưng vì có sẵn ở đó 334 quả từ trước, nên bây giờ còn 1001 quả.

Nghỉ giải lao tự thưởng cho mình 1 quả. Còn 1000 quả vác đi tiếp. Phải đi một đoạn còn lại là 1000 – 533 (= 467) km, và ăn hết từng đó quả chuối. Số quả chuối còn lại là 533 quả khi đến được đến chợ. Như vậy khỉ sẽ có 533 quả chuối ở chợ để bán, nếu làm như vậy?

533 quả đã phải là đáp án tốt nhất nhưa? Có thể có cách nào tốt hơn không? Mirella thì bảo là không, nhưng không lý luận được chặt chẽ vì sao.

Theo bạn đọc thì thế nào? Nếu 533 là kết quả tốt nhất, thì vì sao không có cách nào mang được nhiều quả chuối hơn đến chợ? Còn nếu không phải, thì hãy chỉ ra cách khác tốt hơn?

Hãy thử suy luận tìm phương án tối ứu (và giải thích vì sao nó tối ưu?), rồi so sánh với  lời giải ở trang sau.

Print Friendly
 

Pages: 1 2

Leave a Reply

  

  

  

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Spam Protection by WP-SpamFree