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.
bipakuoeu
wpsdjeqlnrr