Gnomes and Hats

Date: 11/13/2001 at 15:24:15
From: Adam
Subject: Probability with Gnomes

Here's the problem from the probability unit for my college math 
course: 

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 person 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 hats and many 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."  If you say anything else, the king will 
shoot you and all of the remaining gnomes.

I've been thinking about this problem for the past two days, and I 
just can't figure out how to do it. I try reasoning it out using 
logic, but it doesn't work. Maybe there's a way to do it using 
probabiliy formulas? This question has completely baffled me. Can 
you help?

Date: 11/13/2001 at 15:36:52
From: Doctor Tom
Subject: Re: Probability with Gnomes

I can see a way to get 7.5, on average. Each even-numbered gnome names 
the color of the hat directly in front of him. Five gnomes are saved 
for sure, and the even ones have a 50-50 chance.

But maybe you can do better; I'll leave this question open so that 
other math doctors can also think about it.

By the way, if the proportion of hats is not 50-50, my solution is 
even better. But if the king does not put on the hats randomly, he'll 
alternate them and five gnomes die.

- Doctor Tom, The Math Forum
  http://mathforum.org/dr.math/   

Date: 11/13/2001 at 19:51:34
From: Doctor Shawn
Subject: Re: Probability with Gnomes

Adam,

I wonder what this king has against gnomes?

I think that Doctor Tom's response is right on the mark, but I think I 
might be able to prove it. Each gnome can use his response in one of 
two ways: to CONVEY information to another gnome, or to USE 
information for himself. The two do not necessarily exclude each 
other, but unfortunately they don't have to coincide either.

Let's look at the tenth gnome. Since he has no idea what color his hat 
is, he answers the color of the ninth gnome's hat (it's prearranged).  
The tenth either lives or dies, and now the ninth knows what color his 
hat is. The eighth gnome unfortunately has a different color hat than 
the ninth gnome. If the ninth gnome answers with the color of his own 
hat and lives, the eighth has no useful information about the color of 
his own hat. If the ninth tells the eighth what his color hat is (and 
dies in the process) then the eigth will know the color of his hat, 
but will be in the same position regarding the seventh.

So half the gnomes can guarantee the survival of the other half, via
whatever pattern they use - the first will always survive, and the 
tenth will always be at risk, but other than that anything goes. More 
than five will probably not always die, but five is the maximum that 
can be guaranteed.

- Doctor Shawn, The Math Forum
  http://mathforum.org/dr.math/   

Date: 12/11/2001 at 10:08:36 
From: Andrew Love 
Subject: Solution to Gnome puzzle

Dear Dr. Math,

I checked your pages out yesterday as I do periodically, and noticed 
that you didn't come up with what I believe is a solution to the 
"gnomes" puzzle. In my solution, regardless of the number of gnomes 
(N), N-1 gnomes are guaranteed to survive the King's challenge, 
regardless of the sequence of hats that the King chooses.  

Since each gnome can see all the hats in front of him and hear all the 
answers in back of him, here's what he does. If the number of black 
hats in front of him plus the number of times a gnome in back of him 
said "black" is even, then he says "white"; otherwise he says "black."  
In other words, the rearmost gnome reports the parity of the hats in 
front of him, and each subsequent gnome compares the parity report 
from behind him to the parity he sees in front of him - a sneaky way 
to both use the information and pass it forward.  

Here's an example:

The sequence of hats (back to front) is WBWBBBWBWW

W: This gnome sees 5 black hats so he says "Black" (Incorrect) 
B: This gnome sees 4 black hats and heard "Black" once, 
   so he says "Black" (Right) 
W: This gnome sees 4 black hats and heard "Black" twice, 
   so he says "White" (Right) 
B: This gnome sees 3 black hats and heard "Black" twice, 
   so he says "Black" (Right) 
B: This gnome sees 2 black hats and heard "Black" thrice, 
   so he says "Black" (Right) 
B: This gnome sees 1 black hat and heard "Black" four times, 
   so he says "Black" (Right) 
W: This gnome sees 1 black hat and heard "Black" 5 times, 
   so he says "White" (Right) 
B:  This gnome sees no black hats and heard "Black" 5 times, 
   so he says "Black" (Right) 
W: This gnome sees no black hats and heard "Black" 6 times, 
   so he says "White" (Right) 
W: This gnome sees no black hats and heard "Black" 6 times, 
   so he says "White" (Right)

To prove that N-1 gnomes are safe, consider just the front N-1 hats. 
The rearmost gnome reports the parity of the number of black hats. 
The next gnome compares the parity of the N-2 hat sequence in front of 
him with the parity the last gnome reported. If the parities are the 
same, he says "White", because he knows that that's the only way the 
parities could be the same and if the parities are different he says 
"Black" - in both cases, he both saves his life, and provides the next 
gnome forward with an update of the parity to use for the N- 3 case, 
and so on.

A coworker gave me this puzzle a few years ago, and it took me about 
a week to figure it out.

Andy Love