Results 1 to 4 of 4

Thread: 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; Nov 7th 2009 at 02:33 AM. Reason: Merged posts
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Oct 2009
    From
    Brisbane
    Posts
    895
    Thanks
    200
    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
    10
    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
    Super Member
    Joined
    Oct 2009
    From
    Brisbane
    Posts
    895
    Thanks
    200
    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: Jun 15th 2011, 11:38 PM
  2. unsolvable cosine law question.
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: Feb 3rd 2010, 12:34 AM
  3. Unsolvable problem?
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: Apr 26th 2009, 10:06 AM
  4. unsolvable differential equation ?
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: Jul 28th 2008, 04:45 AM
  5. Integration Unsolvable Problem
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: Jun 18th 2006, 09:26 AM

Search Tags


/mathhelpforum @mathhelpforum