| |
 |
|
| Science Forum Index » Mathematics Forum » Unsolvable Puzzle Challenge #1... |
|
Page 1 of 2 Goto page 1, 2 Next |
|
| Author |
Message |
| sarah... |
 Posted: Fri Nov 06, 2009 3:15 pm |
|
|
|
Guest
|
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. |
|
|
| Back to top |
|
|
|
| Achava Nakhash, the Loving Snake... |
| Posted: Fri Nov 06, 2009 3:54 pm |
|
|
|
Guest
|
On Nov 6, 5:15 pm, sarah <academic.g... at (no spam) gmail.com> wrote:
[quote]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.
[/quote]
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.
Regards,
Achava |
|
|
| Back to top |
|
|
|
| Mensanator... |
| Posted: Fri Nov 06, 2009 4:27 pm |
|
|
|
Guest
|
On Nov 6, 7:15 pm, sarah <academic.g... at (no spam) gmail.com> wrote:
[quote]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.
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Mensanator... |
| Posted: Fri Nov 06, 2009 6:56 pm |
|
|
|
Guest
|
On Nov 6, 9:01�pm, "Mike Terry"
<news.dead.person.sto... at (no spam) darjeeling.plus.com> wrote:
[quote]"Mensanator" <mensana... at (no spam) aol.com> wrote in message
news:4c0de00c-910c-4cdb-9fb1-4c5ff258cb9d at (no spam) v25g2000yqk.googlegroups.com...> On Nov 6, 7:15 pm, sarah <academic.g... at (no spam) 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] ?
[/quote]
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.
[quote]
Mike[/quote] |
|
|
| Back to top |
|
|
|
| James Waldby... |
| Posted: Fri Nov 06, 2009 9:05 pm |
|
|
|
Guest
|
On Fri, 06 Nov 2009 20:15:02 -0500, sarah wrote:
....
[quote]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?
....[/quote]
Here are two relevant articles:
<http://en.wikipedia.org/wiki/Binary_number_system#Counting_in_binary>
and <http://en.wikipedia.org/wiki/Pigeonhole_principle>. Apply the
former in the obvious way. To apply the latter, compute the total
number of different combinations of 12 pouches and compare that
number to 4967.
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.
--
jiw |
|
|
| Back to top |
|
|
|
| Mike Terry... |
| Posted: Fri Nov 06, 2009 10:01 pm |
|
|
|
Guest
|
"Mensanator" <mensanator at (no spam) aol.com> wrote in message
news:4c0de00c-910c-4cdb-9fb1-4c5ff258cb9d at (no spam) v25g2000yqk.googlegroups.com...
[quote]On Nov 6, 7:15 pm, sarah <academic.g... at (no spam) 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[/quote]
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.
[quote]
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,[/quote]
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?
[quote]
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
[/quote]
Why not just [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 872] ?
Mike |
|
|
| Back to top |
|
|
|
| The Qurqirish Dragon... |
| Posted: Sat Nov 07, 2009 2:45 am |
|
|
|
Guest
|
On Nov 6, 8:15 pm, sarah <academic.g... at (no spam) gmail.com> wrote:
[quote]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.
[/quote]
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. |
|
|
| Back to top |
|
|
|
| bill... |
| Posted: Sun Nov 08, 2009 12:37 pm |
|
|
|
Guest
|
On Nov 6, 8:56 pm, Mensanator <mensana... at (no spam) aol.com> wrote:
[quote]On Nov 6, 9:01 pm, "Mike Terry"
news.dead.person.sto... at (no spam) darjeeling.plus.com> wrote:
"Mensanator" <mensana... at (no spam) aol.com> wrote in message
news:4c0de00c-910c-4cdb-9fb1-4c5ff258cb9d at (no spam) v25g2000yqk.googlegroups.com....> On Nov 6, 7:15 pm, sarah <academic.g... at (no spam) 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] ?
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
[/quote]
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.
regards Bill J |
|
|
| Back to top |
|
|
|
| Nunemica... |
| Posted: Sun Nov 08, 2009 3:18 pm |
|
|
|
Guest
|
On Nov 6, 6:27 pm, Mensanator <mensana... at (no spam) aol.com> wrote:
[quote]On Nov 6, 7:15 pm, sarah <academic.g... at (no spam) 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...
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Virgil... |
| Posted: Sun Nov 08, 2009 5:46 pm |
|
|
|
Guest
|
In article
<c18d250e-bce2-4c14-be2b-70d095d0ff7d at (no spam) a21g2000yqc.googlegroups.com>,
bill <b92057 at (no spam) yahoo.com> wrote:
[quote]On Nov 6, 8:56 pm, Mensanator <mensana... at (no spam) aol.com> wrote:
On Nov 6, 9:01 pm, "Mike Terry"
news.dead.person.sto... at (no spam) darjeeling.plus.com> wrote:
"Mensanator" <mensana... at (no spam) aol.com> wrote in message
news:4c0de00c-910c-4cdb-9fb1-4c5ff258cb9d at (no spam) v25g2000yqk.googlegroups.com...
On Nov 6, 7:15 pm, sarah <academic.g... at (no spam) 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] ?
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.
[/quote]
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. |
|
|
| Back to top |
|
|
|
| Mensanator... |
| Posted: Sun Nov 08, 2009 6:59 pm |
|
|
|
Guest
|
On Nov 8, 7:18�pm, Nunemica <tinabarbarar... at (no spam) gmail.com> wrote:
[quote]On Nov 6, 6:27�pm, Mensanator <mensana... at (no spam) aol.com> wrote:
On Nov 6, 7:15�pm, sarah <academic.g... at (no spam) 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
[/quote]
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? |
|
|
| Back to top |
|
|
|
| Joshua Cranmer... |
| Posted: Sun Nov 08, 2009 7:06 pm |
|
|
|
Guest
|
On 11/08/2009 05:37 PM, bill wrote:
[quote]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.
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Leon Aigret... |
| Posted: Sun Nov 08, 2009 7:09 pm |
|
|
|
Guest
|
On Sun, 8 Nov 2009 14:37:50 -0800 (PST), bill <b92057 at (no spam) yahoo.com>
wrote:
[quote]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.
[/quote]
Some suggestions are just that. With 12 pouches there can only be
2^12 = 4096 possible pouch selections.
Leon |
|
|
| Back to top |
|
|
|
| Virgil... |
| Posted: Mon Nov 09, 2009 12:14 am |
|
|
|
Guest
|
In article
<9fb871e4-432b-4c09-8912-711c850cad49 at (no spam) g27g2000yqn.googlegroups.com>,
Mensanator <mensanator at (no spam) aol.com> wrote:
[quote]On Nov 8, 7:18?pm, Nunemica <tinabarbarar... at (no spam) gmail.com> wrote:
On Nov 6, 6:27?pm, Mensanator <mensana... at (no spam) aol.com> wrote:
On Nov 6, 7:15?pm, sarah <academic.g... at (no spam) 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?
[/quote]
You could even throw in a few empty pouches, if you had more pouches
than coins. |
|
|
| Back to top |
|
|
|
| Nunemica... |
| Posted: Mon Nov 09, 2009 1:59 am |
|
|
|
Guest
|
On Nov 8, 8:59 pm, Mensanator <mensana... at (no spam) aol.com> wrote:
[quote]On Nov 8, 7:18 pm, Nunemica <tinabarbarar... at (no spam) gmail.com> wrote:
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?
[/quote]
No - that would be the solution to the maximum number of pouches. |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Sat Nov 21, 2009 5:42 pm
|
|