|
|
Munseys_Magic Special user 520 Posts |
There are ten gnomes who have gotten themselves into quite a predicament. They are in the dungeon of a castle of a tyrannical king. Despite the evilness of the king, he has a silver lining in his heart. He has given the gnomes a chance of survival. Here is the offer:
The King lines the gnomes up in a single-file row. This means that the tenth gnome sees the back of the gnome in front of him, and there is no gnome behind the tenth gnome. The ninth gnome has the tenth gnome behind him, and the eighth gnome directly in front of him, and so on. Finally, the first gnome has the second gnome directly behind him, but there is no one in front of the first gnome. The king has a large bag full of many black and white hats. There is not necessarily the same number of black hats as white hats. The king randomly reaches into his bag and places a hat on each of the gnomes. This means that the tenth gnome can see everyone's hat except his own, the ninth gnome can see everyone's hat except his own and the tenth gnome's hat, and so on. The first gnome can see no one's hat. The king, then, takes out his gun and puts it to the temple of the tenth gnome. The king asks the gnome, "What color is your hat?" If the gnome answers correctly, he lives and gets freed from the dungeon. If he does not, he dies. He continues up the line in this progression. However, before placing the hats on the gnomes, he allows the gnomes to meet as a group and discuss a strategy to save as many of the gnomes as possible. Imagine that you are one of these gnomes. What strategy would you develop? How many gnomes can you guarantee to save? REMEMBER: When it is your turn to say the color of your hat, you must ONLY say "white" or "black." Raising or lowering one’s voice, tapping other gnomes on their shoulder, and all other nonverbal cues is illegal. If you say anything else, the king will shoot you and all of the remaining gnomes. |
stanalger Special user St. Louis, MO 998 Posts |
With the proper strategy, the gnomes can guarantee that at least nine of them survive the king's cruel game.
|
Jonathan Townsend Eternal Order Ossining, NY 27297 Posts |
Quote:
On 2006-07-13 08:36, stanalger wrote: Wow! See what happens when you say the right thing.
...to all the coins I've dropped here
|
Munseys_Magic Special user 520 Posts |
Stanalger is correct! So, what's the strategy that they should use?
|
Munseys_Magic Special user 520 Posts |
Stanalger got it!! Here's the answer -
The gnomes could use this strategy: In the absence of evidence to the contrary, they assume the total number of black hats is an even number. Let's call the gnome at the back of the line "Gnome #1." Gnome #1 is the first to guess. If he sees an even number of black hats on the other gnomes, he guesses "white." If he sees an odd number of black hats on the other gnomes, he guesses "black." The other gnomes hear the first gnome's guess. If the guess is followed by the sound of a gun shot, the remaining gnomes now know two things: the total number of black hats is, in fact, odd, and the first gnome's hat was, in fact, opposite in color of the first gnome's guess. If the guess is not followed by a gun shot, the remaining gnomes know that the total number of black hats is even. And the first gnome's hat is the color that he guessed it to be. From this point on, each gnome has enough info to deduce the color of his hat. He knows whether the total number of black hats is even or odd, sees the colors of the hats in front of him, and knows the colors of the hats behind him (because he's heard all of the previous "guesses.") "Guesses" was put in quotes because only the first gnome guessed. Fifty percent of the time, this strategy spares the lives of all ten gnomes. Fifty percent of the time, this strategy spares the lives of all the gnomes except Gnome #1. Of course, no gnome would like to be the one to stand at the back of the line. Pity the mentalist among the gnomes. His fellow gnomes are likely to gang up against him and INSIST that HE stand in the dreaded last position. After all, if he's such a master of body language and other advanced psychological principles.... Stan Alger |
TomasB Inner circle Sweden 1144 Posts |
To quote a good question from Nir, the last time this problem was up here:
"All but the first call can be determined precisely. Do you know what is the limit of the number of colors is, so this would still be true? Can you briefly describe the solution?" I must say that I didn't quite understand how, if the gunshot is heard, that gives any usable info. They could shoot the first gnome with a silencer and the strategy would still work. It's enough to simply listen to the gnome's guess, right? And ignore if he's shot or not, unless you have an emotional connection to him or are very curious about which color his hat was? /Tomas |
Munseys_Magic Special user 520 Posts |
True, indeed. The gunshots are irrelevant.
These two paragraphs can (SHOULD) be removed from Stanalger's reply (which I posted above by copy/pasting from a PM). ************************************************************************ "If the guess is followed by the sound of a gun shot, the remaining gnomes now know two things: the total number of black hats is, in fact, odd, and the first gnome's hat was, in fact, opposite in color of the first gnome's guess." "If the guess is not followed by a gun shot, the remaining gnomes know that the total number of black hats is even, and the first gnome's hat is the color that he guessed it to be." |
stanalger Special user St. Louis, MO 998 Posts |
Thanks, Tomas, for pointing out that my solution was unnecessarily complicated. (I didn't know that this problem had already been discussed here at "Puzzle Me
This...") I see, now, that if the gnomes know how many different colors of hats the king has in his bag, they can always devise a strategy that would guarantee the survival of all but one gnome. Stan |
Munseys_Magic Special user 520 Posts |
Stanalger,
They don't have to know how many of each hat the king has in the bag, and they don't have to hear the gunshot. As long as #10 indicates an odd/even number of black hats in front of him (by the method you described), they simply have to listen to the gnomes behind them. They'll all alive (except for #10), so there won't be any gunshots (except for #10, possibly). Again, hearing whether or not # 10 lives is irrelevant to guarantee the survival of the remaining nine. |
LobowolfXXX Inner circle La Famiglia 1196 Posts |
Although, removing the silencer protects you from the psycho murder/suicide gnome who decides to take everyone out with him.
"Torture doesn't work" lol
Guess they forgot to tell Bill Buckley. "...as we reason and love, we are able to hope. And hope enables us to resist those things that would enslave us." |
TomasB Inner circle Sweden 1144 Posts |
Stan, what is the strategy? I have only found one that works for four colors or less. :-/
/Tomas |
Nir Dahan Inner circle Munich, Germany 1390 Posts |
Tomas,
Try arranging the colors in a cyclic order. Nir |
stanalger Special user St. Louis, MO 998 Posts |
Quote:
On 2006-07-13 20:23, Munseys_Magic wrote: Yes, I now understand that they don't have to hear the gunshot. They do need to know how many DIFFERENT colors of hats the king has. There could be just two colors: black and white. There could be ten colors. In any event, there is a strategy that guarantees that, at most, one gnome will die. Stan Alger |
stanalger Special user St. Louis, MO 998 Posts |
The gnomes only need to know an upper bound for the number of different colors.
For example, if they know there are no more than 12 different colors in the king's hat supply, they can devise a strategy that will result in, at most, one gnome's death. |
Munseys_Magic Special user 520 Posts |
Quote:
On 2006-07-14 16:18, stanalger wrote: True, but the original story says that only 2 colors are used (black and white). And just to be clear for everybody else, they don't have to know how many of each hat are in play. |
TomasB Inner circle Sweden 1144 Posts |
Quote:
On 2006-07-14 17:35, stanalger wrote: Won't they also need to know which colors those are, and not only how many different colors there can be? /Tomas |
stanalger Special user St. Louis, MO 998 Posts |
Tomas,
Correct you are! I'm out of town with limited web access, so I'm posting a bit carelessly. Stan |
alicauchy Veteran user Málaga, Spain 310 Posts |
HI,
I have just discovered this thread created long time ago. Maybe I am missing something, but what if gnome at tenth position simply says the color of the gnome at ninth position and so on? Nothing is needed to be known in advance, either the number of hats, its parity, or even the number of colors. This way, it is always guaranteed that all but the last will save their lives, and even the tenth gnome has some chance to survive if he and the ninth gnome have the same color.
So much to do, so little time . . .
|
alicauchy Veteran user Málaga, Spain 310 Posts |
I hope the gnomes did not follow my suggested procedure, since the uncertain fate of the tenth gnome would apply to all the rest.
This is what happens when one provide answers without enough thinking.
So much to do, so little time . . .
|
Slim King Eternal Order Orlando 18012 Posts |
This is my favorite challenge .. I even shared it with my son.
THE MAN THE SKEPTICS REFUSE TO TEST FOR ONE MILLION DOLLARS.. The Worlds Foremost Authority on Houdini's Life after Death.....
|
The Magic Cafe Forum Index » » Puzzle me this... » » 10 Gnomes and their hats (3 Likes) |
[ Top of Page ] |
All content & postings Copyright © 2001-2024 Steve Brooks. All Rights Reserved. This page was created in 0.06 seconds requiring 5 database queries. |
The views and comments expressed on The Magic Café are not necessarily those of The Magic Café, Steve Brooks, or Steve Brooks Magic. > Privacy Statement < |