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
Puzzle Solution
