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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.