(Close Window) 
Topic: 10 Gnomes and their hats 


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 singlefile row. This means that the tenth gnome sees the back of the gnome 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 and 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." Raising or lowering one’s voice, tapping other gnomes on their shoulder, and all other nonverbal cues is illegal. If you say anything else, the king will shoot you and all of the remaining gnomes. 


With the proper strategy, the gnomes can guarantee that [b]at least[/b] nine of them survive the king's cruel game. 


[quote] On 20060713 08:36, stanalger wrote: With the proper strategy, the gnomes can guarantee that [b]at least[/b] nine of them survive the king's cruel game. [/quote] Wow! See what happens when you say the right thing. :) 


Stanalger is correct! So, what's the strategy that they should use? 


Stanalger got it!! Here's the answer  The gnomes could use this strategy: In the absence of evidence to the contrary, they assume the total number of black hats is an even number. Let's call the gnome at the back of the line "Gnome #1." Gnome #1 is the first to guess. If he sees an even number of black hats on the other gnomes, he guesses "white." If he sees an odd number of black hats on the other gnomes, he guesses "black." The other gnomes hear the first gnome's guess. If the guess is followed by the sound of a gun shot, the remaining gnomes now know two things: the total number of black hats is, in fact, odd, and the first gnome's hat was, in fact, opposite in color of the first gnome's guess. If the guess is not followed by a gun shot, the remaining gnomes know that the total number of black hats is even. And the first gnome's hat is the color that he guessed it to be. From this point on, each gnome has enough info to deduce the color of his hat. He knows whether the total number of black hats is even or odd, sees the colors of the hats in front of him, and knows the colors of the hats behind him (because he's heard all of the previous "guesses.") "Guesses" was put in quotes because only the first gnome guessed. Fifty percent of the time, this strategy spares the lives of all ten gnomes. Fifty percent of the time, this strategy spares the lives of all the gnomes except Gnome #1. Of course, no gnome would like to be the one to stand at the back of the line. Pity the mentalist among the gnomes. His fellow gnomes are likely to gang up against him and INSIST that HE stand in the dreaded last position. After all, if he's such a master of body language and other advanced psychological principles.... Stan Alger 


To quote a good question from Nir, the last time this problem was up here: "All but the first call can be determined precisely. Do you know what is the limit of the number of colors is, so this would still be true? Can you briefly describe the solution?" I must say that I didn't quite understand how, if the gunshot is heard, that gives any usable info. They could shoot the first gnome with a silencer and the strategy would still work. It's enough to simply listen to the gnome's guess, right? And ignore if he's shot or not, unless you have an emotional connection to him or are very curious about which color his hat was? /Tomas 


True, indeed. The gunshots are irrelevant. These two paragraphs can (SHOULD) be removed from Stanalger's reply (which I posted above by copy/pasting from a PM). ************************************************************************ "If the guess is followed by the sound of a gun shot, the remaining gnomes now know two things: the total number of black hats is, in fact, odd, and the first gnome's hat was, in fact, opposite in color of the first gnome's guess." "If the guess is not followed by a gun shot, the remaining gnomes know that the total number of black hats is even, and the first gnome's hat is the color that he guessed it to be." 


Thanks, Tomas, for pointing out that my solution was unnecessarily complicated. (I didn't know that this problem had already been discussed here at "Puzzle Me This...") I see, now, that if the gnomes know how many different colors of hats the king has in his bag, they can always devise a strategy that would guarantee the survival of all but one gnome. Stan 


Stanalger, They don't have to know how many of each hat the king has in the bag, and they don't have to hear the gunshot. As long as #10 indicates an odd/even number of black hats in front of him (by the method you described), they simply have to listen to the gnomes behind them. They'll all alive (except for #10), so there won't be any gunshots (except for #10, possibly). Again, hearing whether or not # 10 lives is irrelevant to guarantee the survival of the remaining nine. 


Although, removing the silencer protects you from the psycho murder/suicide gnome who decides to take everyone out with him. 


Stan, what is the strategy? I have only found one that works for four colors or less. :/ /Tomas 


Tomas, Try arranging the colors in a cyclic order. Nir 


[quote] On 20060713 20:23, Munseys_Magic wrote: Stanalger, They don't have to know how many of each hat the king has in the bag, and they don't have to hear the gunshot. [/quote] Yes, I now understand that they don't have to hear the gunshot. They do need to know how many DIFFERENT colors of hats the king has. There could be just two colors: black and white. There could be ten colors. In any event, there is a strategy that guarantees that, at most, one gnome will die. Stan Alger 


The gnomes only need to know an upper bound for the number of different colors. For example, if they know there are no more than 12 different colors in the king's hat supply, they can devise a strategy that will result in, at most, one gnome's death. 


[quote] On 20060714 16:18, stanalger wrote: They do need to know how many DIFFERENT colors of hats the king has. [/quote] True, but the original story says that only 2 colors are used (black and white). And just to be clear for everybody else, they don't have to know how many of each hat are in play. 


[quote] On 20060714 17:35, stanalger wrote: The gnomes only need to know an upper bound for the number of different colors. [/quote] Won't they also need to know which colors those are, and not only how many different colors there can be? /Tomas 


Tomas, Correct you are! I'm out of town with limited web access, so I'm posting a bit carelessly. Stan 


HI, I have just discovered this thread created long time ago. Maybe I am missing something, but what if gnome at tenth position simply says the color of the gnome at ninth position and so on? Nothing is needed to be known in advance, either the number of hats, its parity, or even the number of colors. This way, it is always guaranteed that all but the last will save their lives, and even the tenth gnome has some chance to survive if he and the ninth gnome have the same color. 


I hope the gnomes did not follow my suggested procedure, since the uncertain fate of the tenth gnome would apply to all the rest. This is what happens when one provide answers without enough thinking. 


This is my favorite challenge .. I even shared it with my son. :sun: 