Problem:
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?
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).