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?

If "nesting" (placing one or more bags inside another and countint the marbles inside the nested bag toward the outer bag's total) is allowed you get 101 bags all with a different number of marbles within:

The first bag is empty. It has 0 marbles.
The second bag contains the first plus one marble. It has one marble.
The third bag contains the second plus one marble. It has two marbles.
The fourth bag contains the third plus one marble. It has three marbles.
....
The 100th bag contains the 99th bag plus one marble. It has 99 marbles.
The 101st bag contains the 100th bag plus one marble. It has 100 marbles.

If nesting is not allowed, then an upper limit can be approximated by the formula for the sum of the first n whole numbers:
T(n)=n(n+1)/2≤100; n(n+1)≤200
13(14)=182; 14(15)=210
There can be no more than 13 differently "weighted" bags.

Posted by TomM on 2003-04-29 08:47:10