A certain gourmet donut store prides itself on being able to provide its customers with any number of donuts between 1 and 80. A customer may go to the counter and say "I want 43 donuts" and 43 donuts will appear in under a minute.
The restaurant wants to use four different sized containers. Your job is to figure out what those sizes should be to minimize the number of packets needed to fill the average order.
To get you started on the problem, suppose the packet sizes are 1, 5, 10 and 20. If someone orders 48 donuts, then the number of packets required is six: two packets of 20, one of 5 and three of 1.
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
One strategy for finding the best set of packet sizes is to try all possible different combinations of four sizes and find the optimal one. But think a little before you take that route. First, one of the sizes must be 1, so really you only have to test ascending triplets of sizes between 2 and 80. When evaluating a triplet, include a packet of size 1, calculate the average cost (that is, the average number of packets in an order and simply keep the triplet with the lowest cost.
Warm-Up:
Suppose the number of donuts in an order ranged only between 1 and 12 with equal probabilities of each size order. If there were four packet sizes, what should they be to minimize the number of packets used to deliver an order?
Solution to Warm-Up:
An optimal set of packet sizes would be 1, 3, 5 and 6. We know this is optimal because no number of donuts in an order requires more than two packets (e.g. an order of two requires two packets of 1 each and an order of 11 requires two packets, one of size 5 and one of size 6) and four orders require only one packet. No other set of packet sizes can be better.
Problems
1. Assuming all orders between 1 and 80 are equally likely, what would be four packet sizes, so the number of packets given to a customer will be minimized on the average?
2. Suppose that orders involving 10 to 20 (inclusive) donuts are four times as likely as any other orders. That is, it is four times as likely for an order to be for, say 14 donuts as for 23. On the other hand, 14 is as likely as 10, and 23 is as likely as 76. If so, what four packet sizes will on average minimize the number of packets given to a customer?
Hint: If you know how to program, that skill might help you find the answer.
