Ten Gnomes
The Problem
Ten gnomes are about to be executed. Although they don’t like the idea, they are each selfless and want to do anything (even by sacrificing themselves) in order to help their fellow gnomes. They are told what will happen to them: They will each be lined up single file, so that they are each facing the gnome in front of them. Each of them will be given a red or a white hat on their head, and from the back of the line (the gnome who can see everyone else) they will ask him to state his hat color, ‘red’ or ‘white.’ If he can state it correctly (he cannot see his own hat, only those in front of him), he is allowed to live. Knowing what is going to happen to them, they are allowed to devise a strategy beforehand. How many people can they guarantee to save, and what strategy will ensure this? (There are NOT five reds and five whites necessarily!)
The Solution
The fact that they’re willing to sacrifice themselves is a hint. There is a 50/50 chance of saving 10. 9 can be saved for sure. Each gnome will shout the color of the hat on the head of the gnome in front of them. If the color of the hat on the gnome at the back of the line is the same as the color of the hat on the head of the gnome in front of him all 10 gnomes will be saved. Otherwise only the front-most 9 will live.
