Μax number of bags

Question

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?

Answer 1

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.

Answer 2

You can use up to $15$ bags ($16$ bags if "empty" is also count).

Here is the figure answer (you said you can put bags inside bigger bags):

The numbers $1;2;3;4;5;6;\cdots$ are the ball number (ball #$1$, #$2$, #$3$, not $1$ ball, $2$ balls, $3$ balls,...).