My Photo
Name: Tyler
Location: Mountain View, California, United States

thinking := [life, games, movies, philosophy, math, coding, pizza, &c.]

Saturday, November 10, 2007

The gnomes in a circle brainteaser

A friend of mine (Neil S) recently told me about the following puzzle:

A group of n gnomes have been captured by an evil wizard. The wizard, in his twisted ways, has granted the gnomes a tricky opportunity to save themselves from a grisly demise.

The wizard has chosen n colors and he will individually paint each gnome's foreheard one of these colors. Then all the gnomes will stand in a circle, so they can see everyone else's colors, but not their own. They then must simultaneously write down a guess at their own forehead's color. If any gnome is correct (even just one), they all go free. Otherwise they will be forced into a lifetime career of unsolicited telemarketing.

Beforehand, the gnomes know what all n colors are, and they have one chance to meet to agree on a strategy. Can you think of a strategy which is guaranteed to save all the gnomes?

Just to be clear, the wizard is allowed to do strange things such as paint everyone's forehead a single color, or use only 3 colors even if there are 100 gnomes (and therefore 100 possible colors).

I should admit ahead of time that the only answer I know is pretty mathy :)

I'll post the answer in a little while.