The Magic Café
Username:
Password:
[ Lost Password ]
  [ Forgot Username ]
The Magic Cafe Forum Index » » Puzzle me this... » » 10 Gnomes and their hats (3 Likes) Printer Friendly Version

Munseys_Magic
View Profile
Elite user
494 Posts

Profile of Munseys_Magic
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.
Jim Munsey
Munsey's Magic
http://www.MunseysMagic.com
stanalger
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
With the proper strategy, the gnomes can guarantee that at least nine of them survive the king's cruel game.
Jonathan Townsend
View Profile
Eternal Order
Ossining, NY
26945 Posts

Profile of Jonathan Townsend
Quote:
On 2006-07-13 08:36, stanalger wrote:
With the proper strategy, the gnomes can guarantee that
at least nine of them survive the king's cruel
game.


Wow! See what happens when you say the right thing. Smile
...to all the coins I've dropped here
Munseys_Magic
View Profile
Elite user
494 Posts

Profile of Munseys_Magic
Stanalger is correct! So, what's the strategy that they should use?
Jim Munsey
Munsey's Magic
http://www.MunseysMagic.com
Munseys_Magic
View Profile
Elite user
494 Posts

Profile of Munseys_Magic
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
Jim Munsey
Munsey's Magic
http://www.MunseysMagic.com
TomasB
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
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
View Profile
Elite user
494 Posts

Profile of Munseys_Magic
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."
Jim Munsey
Munsey's Magic
http://www.MunseysMagic.com
stanalger
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
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
View Profile
Elite user
494 Posts

Profile of Munseys_Magic
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.
Jim Munsey
Munsey's Magic
http://www.MunseysMagic.com
LobowolfXXX
View Profile
Inner circle
La Famiglia
1170 Posts

Profile of LobowolfXXX
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
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
Stan, what is the strategy? I have only found one that works for four colors or less. :-/

/Tomas
Nir Dahan
View Profile
Inner circle
Munich, Germany
1390 Posts

Profile of Nir Dahan
Tomas,

Try arranging the colors in a cyclic order.

Nir
stanalger
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
Quote:
On 2006-07-13 20:23, Munseys_Magic wrote:
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.


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
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
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
View Profile
Elite user
494 Posts

Profile of Munseys_Magic
Quote:
On 2006-07-14 16:18, stanalger wrote:
They do need to know how many DIFFERENT colors of hats the king has.



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.
Jim Munsey
Munsey's Magic
http://www.MunseysMagic.com
TomasB
View Profile
Inner circle
Sweden
1143 Posts

Profile of TomasB
Quote:
On 2006-07-14 17:35, stanalger wrote:
The gnomes only need to know an upper bound for the number
of different colors.

Won't they also need to know which colors those are, and not only how many different colors there can be?

/Tomas
stanalger
View Profile
Special user
St. Louis, MO
996 Posts

Profile of stanalger
Tomas,

Correct you are! I'm out of town with limited web access, so I'm posting a bit carelessly.

Stan
alicauchy
View Profile
Veteran user
Málaga, Spain
311 Posts

Profile of alicauchy
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
View Profile
Veteran user
Málaga, Spain
311 Posts

Profile of alicauchy
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
View Profile
Eternal Order
Orlando
17404 Posts

Profile of Slim King
This is my favorite challenge .. I even shared it with my son. Smile
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-2019 Steve Brooks. All Rights Reserved.
This page was created in 0.16 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 <

ROTFL Billions and billions served! ROTFL