You have one hundred marbles, and an infinite supply of trash bags. If you were to put the marbles in the bags, so that no two bags had the same amount of marbles, what is the most bags that you could use?

(In reply to

answer by K Sengupta)

Let N be the maximum number of bags. Then the N bags will contain 0, 1, 2, ...., N-1 marbles in some order.

Without loss of generality, the first bag is empty, so that it

contains 0 marbles.

We put one marble in the second bag and put the second bag

inside the third bag. One marble now placed in the third bag

but is located outside the second bag.

The third bag is now put inside the third bag, a marble is

put inside the fourth bag, but outside the third bag, and

the process is repeated till the Nth bag.

Accodingly the bag number N contains (N-1) marbles, so that

bag number i contains (i-1) marbles, for i = 1,2,..., N

Thus, the required minimum number of bags is N.

In the given problem, we are given 100 marbles, so that:

N-1 = 100, giving: N = 101

Consequently, the required maximum number of bags that one can use is 101.

*Edited on ***April 2, 2008, 5:59 am**