Here’s an example of Roy Doty‘s work in MAKE. (Click on thumbnail for enlargement) (The puzzle was selected by Michael H. Pryor.)
Point of Gnome Return
One hundred very smart garden gnomes are snatched from their homes by an evil wizard. He tells them he is going to line them all up in a row, and place red and blue hats on each of their heads. They won’t be able to see the color of their own hats or anyone’s behind them, but they will be able to see the hats of the gnomes in front of them. The wizard will start at the back of the line and ask each gnome to tell the color of his own hat. Each gnome can only answer either “red” or “blue.” If he gives the wrong answer, he will be led off to work on the wizard’s landscaping for the rest of eternity. If he answers correctly, he will be returned to his own garden. Then the wizard will move on to the next gnome in line.
All of the gnomes will be able to hear the answers of the gnomes behind them, but they will not know if they were led off to forced labor or if they answered correctly and were set free. The gnomes are allowed to consult and agree on a strategy beforehand (while the wizard listens in) but after being lined up, they will not be able to communicate in any other way besides their answer of “red” or “blue” (in other words, they won’t be able to change the pitch of their voice or give any other clues to the other gnomes once they are in line and the hats are placed on their heads). What strategy should the gnomes use to maximize the total number of gnomes that will be set free? Hint: They can do pretty well, even if the wizard hears their plan and puts the hats on in such a way to thwart whatever idea they come up with.
