Topic: 10 Gnomes and their hats
 Message: Posted by: Munseys_Magic (Jul 12, 2006 04:34PM)
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.
 Message: Posted by: stanalger (Jul 13, 2006 07:36AM)
With the proper strategy, the gnomes can guarantee that [b]at least[/b] nine of them survive the king's cruel game.
 Message: Posted by: Jonathan Townsend (Jul 13, 2006 07:43AM)
[quote]
On 2006-07-13 08:36, stanalger wrote:
With the proper strategy, the gnomes can guarantee that
[b]at least[/b] nine of them survive the king's cruel
game.
[/quote]

Wow! See what happens when you say the right thing. :)
 Message: Posted by: Munseys_Magic (Jul 13, 2006 08:01AM)
Stanalger is correct! So, what's the strategy that they should use?
 Message: Posted by: Munseys_Magic (Jul 13, 2006 12:05PM)
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
 Message: Posted by: TomasB (Jul 13, 2006 05:03PM)
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
 Message: Posted by: Munseys_Magic (Jul 13, 2006 05:29PM)
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."
 Message: Posted by: stanalger (Jul 13, 2006 06:19PM)
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
 Message: Posted by: Munseys_Magic (Jul 13, 2006 07:23PM)
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.
 Message: Posted by: LobowolfXXX (Jul 13, 2006 10:00PM)
Although, removing the silencer protects you from the psycho murder/suicide gnome who decides to take everyone out with him.
 Message: Posted by: TomasB (Jul 14, 2006 01:45AM)
Stan, what is the strategy? I have only found one that works for four colors or less. :-/

/Tomas
 Message: Posted by: Nir Dahan (Jul 14, 2006 02:28PM)
Tomas,

Try arranging the colors in a cyclic order.

Nir
 Message: Posted by: stanalger (Jul 14, 2006 03:18PM)
[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. [/quote]

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
 Message: Posted by: stanalger (Jul 14, 2006 04:35PM)
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.
 Message: Posted by: Munseys_Magic (Jul 14, 2006 04:46PM)
[quote]
On 2006-07-14 16:18, stanalger wrote:
They do need to know how many DIFFERENT colors of hats the king has. [/quote]

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.
 Message: Posted by: TomasB (Jul 15, 2006 01:38AM)
[quote]
On 2006-07-14 17:35, stanalger wrote:
The gnomes only need to know an upper bound for the number
of different colors.
[/quote]
Won't they also need to know which colors those are, and not only how many different colors there can be?

/Tomas
 Message: Posted by: stanalger (Jul 15, 2006 11:20PM)
Tomas,

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

Stan
 Message: Posted by: alicauchy (Feb 11, 2019 01:05PM)
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.
 Message: Posted by: alicauchy (Feb 12, 2019 07:01AM)
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.
 Message: Posted by: Slim King (Sep 18, 2019 09:15PM)
This is my favorite challenge .. I even shared it with my son. :sun: