Chelsea goes to La Verde's at MIT and buys 100 coconuts, each weighing 4 pounds, and 100 honeydews, each weighing 5 pounds. She wants to distribute them among bags, so that each bag contains at most 13 pounds of fruit. What is the minimum for which this is possible?
Problem 843
Official solution
Solution:
The answer is , given by 50 bags containing one honeydew and two coconuts (13 pounds), and 25 bags containing two honeydews (10 pounds).
To show that this is optimal, assign each coconut 1 point and each honeydew 2 points, so that 300 points worth of fruit are bought in total. Then, we claim that each bag can contain at most 4 points of fruit, thus requiring . To see this, note that each bag containing greater than 4 points must contain either five coconuts (20 pounds), three coconuts and a honeydew (17 pounds), one coconut and two honeydews (14 pounds), or three honeydews (15 pounds).