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?

Answer: 27. Put 1, 2, 3 ... 13 in the first 13 bags. Then put bag 11 plus 3 marbles in bag 14, bag 13 plus 2 in 15, and bag 12 plus 4 in 16. Then combine bags as follows: 8&9 in 17, 2&16 in 18, 7&14 in 21, and 15,3&1 in 19. At this point the bag count is 20. Continue combining bags: 5&17 in 22, 6&18 in 24, 4&21 in 25, and 10&19 in 29. Total now is 24. Finally 22&24 in 46, 25&29 in 54, and 46&54 in 100.

Posted by Thomas on 2003-08-01 10:47:26