Thread: Unsolvable Puzzle Challenge #1

Hello everyone :]
i like to browse around the web searching for math problems and puzzles that are quite difficult, and nearly unsolvable. they are interesting brain excersises, some of which i can solve and some of which i cant. This particular one I can't figure out how to go about solving it, so I will post it here as both a challenge and a question to anyone willing to try it.

here it is:

A man has 4967 coins. Suppose he divides those coins into several coin pouches so that if you ask for any whole number of coins between 1 and 4967, he can give you the proper amount by giving you a certain number of pouches. What is the minimum number of pouches required for him to do this?


note: i did NOT make this up, i found it on the web.

even if you dont know the answer, any tips or advice on how to start this would be appreciated :]

Seems to me it's got something to do with powers of 2.
He must have a bag with 1 coin in it - so that he can give you that bag if you ask for one coin.
He must also have one with 2 in it.
Doesn't need one with 3, because he coul give you Bag1 and Bag2.
Need a Bag4.
Don't need a 5 (Bag1 & Bag4) or 6 (Bag 2 and 4) or 7 (Bag3 and Bag4).
Need a Bag8.
Don't need 9,10,11,12,13,14,15 because these can be made up from the bags you already have.
Need a 16.
SO..... you need Bag1, Bag2, Bag4, Bag8, Bag 16 .... up to Bag 4096.
ie Bag (2^0), Bag(2^1), Bag(2^2) ....Bag(2^12)......ie 13 bags in all.

Originally Posted by Debsta

Seems to me it's got something to do with powers of 2.
He must have a bag with 1 coin in it - so that he can give you that bag if you ask for one coin.
He must also have one with 2 in it.
Doesn't need one with 3, because he could give you Bag1 and Bag2.
Need a Bag4.
Don't need a 5 (Bag1 & Bag4) or 6 (Bag 2 and 4) or 7 (Bag3 and Bag4).
Need a Bag8.
Don't need 9,10,11,12,13,14,15 because these can be made up from the bags you already have.
Need a 16.
SO..... you need Bag1, Bag2, Bag4, Bag8, Bag 16 .... up to Bag 4096.
ie Bag (2^0), Bag(2^1), Bag(2^2) ....Bag(2^12)......ie 13 bags in all.

That's almost but not completely correct, because 1 + 2 + 4 + ... + 4096 = 8191, which is quite a bit more than the total number of coins available. However, the answer 13 bags is correct, and so is the method, except that the powers of 2 should only go up to 2^11 = 2048. That uses 12 bags containing a total of 4095 coins. The remaining 852 (= 4967 – 4095) coins go into the 13th bag.

There are many other solutions using 13 bags, but there is no possibility of getting an answer with fewer than 13 bags. In fact, a set of 12 elements has only 2^12 – 1 = 4095 nonempty subsets, so 12 bags could only provide for a maximum of 4095 different possible combinations.

Thanks. Yes I agree mine is incorrect now, I hadn't taken into account that he only had 4097 to start with.
So anything over 4095, needs the last(13th) bag and can make up the rest from a selection of the first 12. Makes sense.