Results 1 to 4 of 4

Math Help - Unsolvable Puzzle Challenge #1

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    1

    Wink

    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 :]
    Last edited by mr fantastic; November 7th 2009 at 02:33 AM. Reason: Merged posts
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Oct 2009
    From
    Brisbane
    Posts
    311
    Thanks
    2
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Debsta View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Oct 2009
    From
    Brisbane
    Posts
    311
    Thanks
    2
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. unsolvable in a normal way integral mmn 15 5
    Posted in the Calculus Forum
    Replies: 22
    Last Post: June 15th 2011, 11:38 PM
  2. unsolvable cosine law question.
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: February 3rd 2010, 12:34 AM
  3. Unsolvable problem?
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: April 26th 2009, 10:06 AM
  4. unsolvable differential equation ?
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: July 28th 2008, 04:45 AM
  5. Integration Unsolvable Problem
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: June 18th 2006, 09:26 AM

Search Tags


/mathhelpforum @mathhelpforum