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.
On Nov 6, 5:15 pm, sarah <academic.g...@gmail.com> wrote:
> 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.
Sarah,
You write as if your are a native speaker of English, but there are still many countries you could possibly come from. This group is quite international, and the coinage can vary significantly from country to country. What country do have in mind, and since not all of know the types of coins of all countries, so it would be a good idea to clue us in on that.
> 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?
Regarding Achava's question about the denominations of the coins, that seems irrelevant because the question is about numbers of whole coins, rather than dollars, rupees, rubles, or whatever.
On Nov 6, 7:15 pm, sarah <academic.g...@gmail.com> wrote:
> 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.
pouches [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 1, 2, 4, 32, 64, 256, 512, 1] total coins 4967 [] if empty, all integers found
> On Nov 6, 7:15 pm, sarah <academic.g...@gmail.com> wrote: > > 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.
> pouches [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 1, 2, 4, > 32, 64, 256, 512, 1] > total coins 4967 > [] if empty, all integers found
Why not just [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 872] ?
> 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.
> > pouches [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 1, 2, 4, > > 32, 64, 256, 512, 1] > > total coins 4967 > > [] if empty, all integers found
> Why not just [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 872] ?
Because I thought you needed to make make all the integers between 4095 and 4967 (which you do), but that can be accomplished by selecting all pouches to get 4967, and then subtracting pouches to walk backwards to 4095. For example, select all pouches and then deselect the first to get 4966, the second to get 4965, the first and second to get 4964, etc.
On Nov 6, 8:15 pm, sarah <academic.g...@gmail.com> wrote:
> 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.
Mike Terry already posted (one) correct answer. For reasoning: You need to make 4968 different amounts (including 0, even though the problem doesn't ask for it, it saves a lot of "-1"s in the answer). Since each bag (regardless of the number of coins in it) is either "in" or "out", if you have n bags, you can only make at most 2^n values (including 0). The smallest n such that 2^n is greater than 4968 is 13 (2^12 = 4096), so you need at least 13 bags. Using the list that Mike used is one solution that uses 13 bags, and so 13 is achievable.
As a side note, to illustrate that there are other possibilities, you can replace the last 2 bags in the list (2048 and 872) with any two amounts that use all the remaining 2920 coins, as long as neither is larger than 2484.
Puzzle Question: assuming that 13 bags are used, what it the least amount that MUST appear in at least one bag? The above note shows that you don't need more than 1460, but that can be improved.
> > 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.
> > Why not just [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 872] ?
> Because I thought you needed to make make all the > integers between 4095 and 4967 (which you do), but > that can be accomplished by selecting all pouches > to get 4967, and then subtracting pouches to walk > backwards to 4095. For example, select all pouches > and then deselect the first to get 4966, the second > to get 4965, the first and second to get 4964, etc.
> > Mike
Mike is correct. For counts less than 4096, select from the 12 smaller pouches. For counts over 4096, start with the 842 pouch and get the additionally necessary coins from among the 12 smaller pouches.
The ease with which the 13 pouch solution is achieved suggests that a 12 pouch solution might be available.
> > > 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.
> > > Why not just [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 872] ?
> > Because I thought you needed to make make all the > > integers between 4095 and 4967 (which you do), but > > that can be accomplished by selecting all pouches > > to get 4967, and then subtracting pouches to walk > > backwards to 4095. For example, select all pouches > > and then deselect the first to get 4966, the second > > to get 4965, the first and second to get 4964, etc.
> > > Mike
> Mike is correct. For counts less than 4096, select from the 12 smaller > pouches. For counts over 4096, > start with the 842 pouch and get the additionally > necessary coins from among the 12 smaller pouches.
> The ease with which the 13 pouch solution is > achieved suggests that a 12 pouch solution might be > available.
It is fairly easily shown, using binary notation that in order to get every number from 1 up through 2^12 - 1 = 4096 - 1 = 4095, one needs at least twelve pouches, and that every possible combination of those 12 pouches must be used in order to get ALL those numbers.
That certainly strongly suggests that to get all numbers from 1 up to any number in excess of 4095, one would need at least 13 pouches.
On Sun, 8 Nov 2009 14:37:50 -0800 (PST), bill <b92...@yahoo.com> wrote:
>Mike is correct. For counts less than 4096, select from the 12 smaller >pouches. For counts over 4096, >start with the 842 pouch and get the additionally >necessary coins from among the 12 smaller pouches.
>The ease with which the 13 pouch solution is >achieved suggests that a 12 pouch solution might be >available.
Some suggestions are just that. With 12 pouches there can only be 2^12 = 4096 possible pouch selections.
> Mike is correct. For counts less than 4096, select from the 12 smaller > pouches. For counts over 4096, > start with the 842 pouch and get the additionally > necessary coins from among the 12 smaller pouches.
> The ease with which the 13 pouch solution is > achieved suggests that a 12 pouch solution might be > available.
I doubt it: I think you can prove that the maximum k such that n pouches can produce all values from 1-k is 2^n - 1.
Proof attempt: If you have n pouches, you can either use it or not use it to generate a value v. There are therefore 2^n values you can generate. One of these values is 0 (you take no pouches); therefore the maximum range of consecutive values is of length 2^n - 1. If you start at 1, your largest number is therefore 2^n - 1.
-- Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
On Nov 6, 6:27 pm, Mensanator <mensana...@aol.com> wrote:
> On Nov 6, 7:15 pm, sarah <academic.g...@gmail.com> wrote:
> > 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...
Ummm I calculated this in a hurry but my solution is:
551 pouches containing 9 coins per pouch = 4959 8 pouches containing 1 coin per pouch = 8
On Nov 8, 7:18 pm, Nunemica <tinabarbarar...@gmail.com> wrote:
> On Nov 6, 6:27 pm, Mensanator <mensana...@aol.com> wrote:
> > On Nov 6, 7:15 pm, sarah <academic.g...@gmail.com> wrote:
> > > 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...
> Ummm I calculated this in a hurry but my solution is:
> 551 pouches containing 9 coins per pouch = 4959 > 8 pouches containing 1 coin per pouch = 8
Hell, for that matter you could have 4967 pouches with 1 coin each.
Of course, that wouldn't exactly be the MINIMUM solution, would it?
Mensanator <mensana...@aol.com> wrote: > On Nov 8, 7:18?pm, Nunemica <tinabarbarar...@gmail.com> wrote: > > On Nov 6, 6:27?pm, Mensanator <mensana...@aol.com> wrote:
> > > On Nov 6, 7:15?pm, sarah <academic.g...@gmail.com> wrote:
> > > > 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...
> > Ummm I calculated this in a hurry but my solution is:
On 2009-11-07, sarah <academic.g...@gmail.com> wrote:
> 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?
The best possible case is where every possible combination of pouches gives a different sum of coins. With 12, there are 2^12 = 4096 different choices, so that 4967 combinations cannot be achieved with 12 pouches.
It is possible to do it with 13 pouches. If he puts 2^(n-1) coins in pouch n for n < 12, then he can select any number of coins from 0 to 4095 using only those. Putting the remaining coins in a 13th pouch, this is extended to 4967 (though with overlap in amounts for some combinations).
> On 2009-11-07, sarah <academic.g...@gmail.com> wrote: > > 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?
> The best possible case is where every possible > combination of pouches > gives a different sum of coins. With 12, there are > 2^12 = 4096 > different choices, so that 4967 combinations cannot > be achieved with > 12 pouches.
> It is possible to do it with 13 pouches. If he puts > 2^(n-1) coins in > pouch n for n < 12, then he can select any number of > coins from 0 to > 4095 using only those. Putting the remaining coins > in a 13th pouch, > this is extended to 4967 (though with overlap in > amounts for some > combinations).
>On 2009-11-07, sarah <academic.g...@gmail.com> wrote: >> 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?
>The best possible case is where every possible combination of pouches >gives a different sum of coins. With 12, there are 2^12 = 4096 >different choices, so that 4967 combinations cannot be achieved with >12 pouches.
>It is possible to do it with 13 pouches. If he puts 2^(n-1) coins in >pouch n for n < 12, then he can select any number of coins from 0 to >4095 using only those. Putting the remaining coins in a 13th pouch, >this is extended to 4967 (though with overlap in amounts for some >combinations).
Okay. Now that we know it is 13 pouches, minimize the maximum number of coins in any pounch.
> In article > <slrnhfhua9.n6v....@soprano.little-possums.net>, > Tim Little <t...@little-possums.net> wrote: > >On 2009-11-07, sarah <academic.g...@gmail.com> > wrote: > >> 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?
> >The best possible case is where every possible > combination of pouches > >gives a different sum of coins. With 12, there are > 2^12 = 4096 > >different choices, so that 4967 combinations cannot > be achieved with > >12 pouches.
> >It is possible to do it with 13 pouches. If he puts > 2^(n-1) coins in > >pouch n for n < 12, then he can select any number of > coins from 0 to > >4095 using only those. Putting the remaining coins > in a 13th pouch, > >this is extended to 4967 (though with overlap in > amounts for some > >combinations).
> Okay. Now that we know it is 13 pouches, minimize > the maximum number > of coins in any pounch.
> Alan
> >- Tim
> -- > Defendit numerus
sigh ...
they still dont understand !
and it was ME , TOMMY1729 who answered correctly as the first.
On Nov 6, 5:15 pm, sarah <academic.g...@gmail.com> wrote:
> 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.
Am I the only one wondering if 4967 was a random or deliberate choice?
> In article <slrnhfhua9.n6v....@soprano.little-possums.net>, > Tim Little <t...@little-possums.net> wrote: > >On 2009-11-07, sarah <academic.g...@gmail.com> wrote: > >> 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?
> >The best possible case is where every possible combination of pouches > >gives a different sum of coins. With 12, there are 2^12 = 4096 > >different choices, so that 4967 combinations cannot be achieved with > >12 pouches.
> >It is possible to do it with 13 pouches. If he puts 2^(n-1) coins in > >pouch n for n < 12, then he can select any number of coins from 0 to > >4095 using only those. Putting the remaining coins in a 13th pouch, > >this is extended to 4967 (though with overlap in amounts for some > >combinations).
> Okay. Now that we know it is 13 pouches, minimize the maximum number > of coins in any pounch.
Pounch?
1, 2, 4, 8, ..., 1024 is 11 pouches and gets everything through 2047. Now a couple of 1460 will get everything to 4967, so you can get the maximum down to 1460.
-- Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
|
