Hat Color Puzzles

Four Fishermen in the Sand

I buried four fishermen up to their necks in the sand on the beach at low tide for keeping their fishing spot a secret from me. I positioned them on either side of a wall, and placed either white or black hats on their heads, as shown in the accompanying photograph I took of them. Knowing only that there are two white hats and two black hats, they must correctly deduce the color of their own hat as quickly as possible. Which one will first be able to do this with 100% confidence? Assume they are sufficiently motivated to deduce, but not make random guesses.

100 Wizards and a Witch

An evil witch / kindergarten teacher / Republican has sentenced 100 wizards / kindergarten students / homosexual atheists to the following fate: After a short amount of time in which they may develop a guessing strategy, the wizards will line up in random order, all facing the same direction, and have white or black hats placed on their heads. Starting at the back of the line (the wizard who can see the other 99 and their hats), the witch will give each wizard one chance to correctly guess their own hat color. This single guess ("white!" or "black!") is also the only way that they are able to communicate with one another (no whispering or coded vocal inflections, etc.). Wizards are not even aware of whether previous guesses were correct or not. Furthermore, the witch can listen as the wizards discuss their strategy before she decides how she will distribute an unknown combination of white and black hats. What strategy should the wizards employ?

Four Fisherman in the Sand
SOLUTION

Fishermen A and B see nothing but wall and are totally out of the loop; they wait patiently, futilely, for any information that might help them. Fisherman C sees a white hat, and cannot immediately deduce anything; he waits for further information. Fisherman D sees a white and black hat, and also cannot make any solid conclusions.

But consider, from Fisherman C's perspective: if Fisherman D saw two white hats (or two black hats), he would be able to deduce his own hat color. Fisherman D's uncertainty and silence is very telling to Fisherman C. After Fisherman C is sure that Fisherman D has nothing to say, he can safely deduce that his own hat is black, says so, and is free.

This information does not help the other fishermen, and they remain silent until their lungs fill with sea water.

100 Wizards and a Witch
SOLUTION

The most obvious strategy is that Wizards #100, #98, #96, etc. name the hat color in front of them, allowing Wizards #99, #97, etc. to guess with 100% accuracy, thereby saving at least half the wizards for sure and, depending on the breaks, about 75 of them on average.

(And no matter what strategy these wizards come up with, the one at the back of the line is doomed to a 50% chance of survival, since no one but the witch ever knows what color his hat is.)

However, there is a surefire strategy that saves the lives of at least 99 wizards. The strategy uses a set of rules (detailed below), whereby each wizard can compare whether the number of black hats he sees agrees with the number of black hats the previous wizard saw. This is all the information needed in order to deduce whether ones own hat is black. Here's the strategy:

• Guessing Scheme A: even # of black hats → guess "black!"; odd number of black hats → guess "white!"
• Guessing Scheme B: even # of black hats → guess "white!"; odd number of black hats → guess "black!"
• The first wizard uses Guessing Scheme A.
• Wizards switch guessing schemes every time they hear "black!"

For simplicity, let's reduce it to a 10-wizard case, pictured here:
Wizard #10 is at the rear, and is the first to guess his hat color. As mentioned before, his own hat color is irrelevant to the overall strategy. He sees 5 black hats in front of him and (incorrectly, poor bastard) says "white!" according to Scheme A.

Wizard #9 now knows two things: 1) He sees an odd number of black hats and 2) Wizard #10 also saw an odd number of black hats. Wizard #9 can safely deduce his own hat is white, as prescribed by Scheme A.

Wizard #8 knows his two buddies saw an odd number of black hats, but he sees an even number of them, so he knows his own must be black, and says so (according, again, to Scheme A).

After hearing Wizard #8 say "black!", Wizard #7 switches to Scheme B, and takes the even number of black hats in front of him to mean his own is white.

And so on.