Filling up 100 coins in 10 bags

Question

There's a king who wants to appoint a new minister. To check the intelligence of the interested men, he gives the following problem:

There are 10 bags and there are 100 coins. You have to fill all the 100 coins into the 10 bags. You may fill any number of coins into any bag. You may keep a bag empty, but you must fill all the coins into the bags. Then you must seal the bags. Then I'll ask you to give me any number of coins and you must be able to give me that exact amount without opening any of the bags. In other words, you must hand me over several bag/s which will contain coins equal to what I have asked for.

Only one person could do it, and he was appointed minister.

How would you do it?

Answer 1

You need only 7 bags, of size 1, 2, 4, 8, 16, 32 and 37 [=100-(64-1)].

For an amount less than 37, convert the number into binary and give the bags required. For values above 37, give the 37 bag, subtract it from the value, and then give the rest as in above method.

Answer 2

Already answered, but how I did it was by unintentionally disregarding the "not all bags need to be used" stipulation and dividing amongst 10 bags.

With the numbers 1, 2, 3, 4 and 5 any nonzero digit can be created with addition, meaning there are 85 coins(1+2+3+4+5=15) and 5 bags left over to make every base ten number up to 100. To complete this I got 5, 10, 20, 20 and 30, rounding out 10 bags that can make every sum from 1 - 100. Explaining the intuition would be quite clumsy, but it basically boils down to considering the addition of the existing multiples of 10 with respect to future possibilities.