# Gnomes puzzle

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.

Hi Elliot. I couldn’t post on your guestbook, so I was checking out your blog. I like puzzles like this. I think the solution is for the every other gnome to agree to answer with the color of the gnome before’s hat color. That means the 10th gnome would respond with the color of the hat worn by the 9th gnome. That gives the 10th gnome a 50% chance of survival, but the 9th gnome, when it’s his turn has a 100% accuracy. Gnome 8 answers with the color of the hat in front of him, giving him a 50% chance, but 7 has 100% accuracy, and so on up the line. You are guaranteed to save 5 gnomes this way.

That’s what I thought of too. Unfortunately, I cheated and read the answer on how to guarantee the lives of 9 gnomes (can you figure it out?)… but it’s still a great puzzle.

The answer seems to be invalid in that it assumes there are 5 white and 5 black hats. In the puzzle it is stated that the amount of black/white could not be equal, so there could be 9 black and 1 white etc.

Here’s the actual answer.

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”. If the number is odd, 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.

To prove that 9 gnomes are safe, consider just the front 9 hats.

The rearmost gnome reports the parity of the number of black hats.

The next gnome compares the parity of the 8 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 7th case,

and so on.

bipakuoeuwpsdjeqlnrr