Associated Topics || Dr. Math Home || Search Dr. Math

### Gnomes and Hats

```
Date: 11/13/2001 at 15:24:15
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.

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

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
```
Associated Topics:
College Probability

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search