Extra day! Hat puzzle.

Today is an extra day. As a special bonus, it is also snowing big, fluffy flakes, and it's not too cold. This is a good sampling of weather for the prospective students who are visiting the department this week. Last night, the department sent us forth in groups of {two current, four potential} students to eat dinner. The dinner degenerated (after a long period of substantive, informative conversation) into puzzles. I love puzzles!

... and so I shall introduce you to the "hat" puzzle. There are many versions of this puzzle, but I heard this one first so I think of it as the canonical "hat" puzzle. I am sure I will post many more.

A hundred mathematicians are shipwrecked on a cannibal-infested island. The cannibals are sporting, though, so rather than skewer and roast all the mathematicians right away, they give them a chance to win their freedom, saying,

Tomorrow at dawn we will line you up on the beach, each facing the back of the next person in line. Then we will take a bunch of red and blue hats and put one hat on each person's head.

Starting with the last person in line (that is, the person who can see everyone else), we will ask you what color hat you are wearing. If you answer correctly, you will be set free. If you answer incorrectly, we will drag you off to "participate" in the evening feast.

What strategy do the mathematicians develop to save themselves? Can they save everyone?


This post's theme song: "Problem Girl" by Rob Thomas.