Μax number of bags We have $15$ tennis balls and want to place them into plastic bags. What is the largest number of bags we can use, so that each bag has a different number of balls? My initial approach is: Obviously $1+2+3+4+5=15$ bags, so we use $5$ bags so far. Then we use $1$ bag to put inside bags with $2$ and with $4$ ($=6$ in total) and $1$ bag to put $3+5=8$ in total. Then $1$ more bag to put these $2$ ($=14$ in total) and $1$ more to put this last one along with the initial bag with $1$ ($=15$). All in all $9$ bags. But I was told that it is possible to use even more bags. Any ideas?

An upper limit is $16$: the number of balls in each bag is between $0$ and $15$, so if we have more than $16$ bags, two are forced to have the same number of balls.

We can achieve $16$ as follows:

1. Leave bag #0 empty.
2. Put bag #0 and a ball inside bag #1.
3. Put bag #1 and a ball inside bag #2.
4. Put bag #2 and a ball inside bag #3.
5. And so on.



Then bag #$k$ contains $k$ balls total: the $k-1$ balls inside the previous bag, and one more.