# Problem of the Week Problem C and Solution Jellybean Surprise

## Problem

Ru has $$100$$ jellybeans that she is placing in small boxes for a party game. She has decided that each box must contain at least one jellybean and no two boxes can contain the same number of jellybeans. As well, no box can go inside any other box.

Determine the maximum number of boxes Ru can use for her jellybeans.

## Solution

In order to maximize the number of boxes, each box must contain the smallest number of jellybeans possible. However, no two boxes can contain the same number of jellybeans. The simplest way to approach this problem is to put one jellybean in the first box and then let the number of jellybeans in each box after that be one more than the number of jellybeans in the box before it, until all $$100$$ jellybeans are in boxes.

We will put $$1$$ jellybean in the first box, $$2$$ jellybeans in the second box, $$3$$ jellybeans in the third box, and so on. After filling $$12$$ boxes this way, we have used $$1+2+3+4 + 5 + 6 + 7 + 8 + 9 + 10+11+12=78$$ jellybeans. After putting $$13$$ jellybeans in the thirteenth box, we have used $$78+13=91$$ jellybeans. There are $$9$$ jellybeans left, but we already have a box containing $$9$$ jellybeans. The remaining $$9$$ jellybeans must therefore be distributed among the existing boxes while maintaining the condition that no two boxes contain the same number of jellybeans.

One way to do this is to put the $$9$$ jellybeans in the last box which already contains $$13$$ jellybeans. This would mean that the final box would contain $$13+9=22$$ jellybeans. Another solution is to increase the number of jellybeans in each of the final nine boxes by one jellybean each. This solution is summarized in the following table.

 Box Number $$1$$ $$2$$ $$3$$ $$4$$ $$5$$ $$6$$ $$7$$ $$8$$ $$9$$ $$10$$ $$11$$ $$12$$ $$13$$ Number of Jellybeans $$1$$ $$2$$ $$3$$ $$4$$ $$6$$ $$7$$ $$8$$ $$9$$ $$10$$ $$11$$ $$12$$ $$13$$ $$14$$

Either way, the maximum number of boxes required is $$13$$.

If you had $$14$$ boxes, with the first box containing $$1$$ jellybean and each box after that containing one more jellybean than the box before, you would need $$1+2+3+\cdots+13+14=105$$ jellybeans, which is more than the number of jellybeans Ru has.