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. (Wink)
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 :] (Nerd)
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.
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.
Originally Posted by Debsta
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.