One of my friends likes to present lots of interesting puzzles. I think the first one that he presented was the “line of gnomes” problem. It’s certainly not a completely original problem, but I think it’s cool none the less. Here’s the basic problem statement:

An evil witch is hungry and wants to eat all the gnomes (hundreds of them) in a local village. For some reason, the gnomes don’t want to be eaten, so they work out a deal with the witch that involves a simple game (since gnomes, with their infinite logic and memory capabilities, love games). After explaining the game to the gnomes, the gnomes will be allowed to work out a game strategy, then will not be allowed to communicate with each other until the game completes.

The game works as follows: The witch will line all the gnomes up (facing North) so that each gnome can see the gnomes in front of him, but can’t see himself or any gnomes behind him. The witch will then proceed to place a white or black hat on each gnome, randomly chosen. The witch will then go to the back of the line, to the gnome who is able to see everyone else, and asks “What color hat do you wear?”. If the gnome answers correctly, the witch will not eat him, but if he answers incorrectly, he will be immediately devoured. The witch will then do the same for each of the following gnomes. When asking each gnome what hat he wears, the gnome responds either “black” or “white,” without any voice inflections (so no hidden information can be hidden in the response).

Given there are $N$ gnomes in the line, and that each gnome plays optimally:

1. How many gnomes can be guaranteed survival?
2. What is the expected number of gnomes that will live?

show