Practice Lateral Thinking with Riddle #3: Black and White Hat Demon

Riddle of the Black and White Hat Demon
(Difficulty: Hard)

Yet another riddle that I've done a poor job renaming. This is a riddle I heard while I was in Game Theory class several years ago, I take no credit for it other than butchering the actual details.

It goes a little something like this:

Somewhere in the world there is a small village of people who live on a tiny island. They have a population of only 100 people, but every single citizen has perfect logic, perfect memory, perfect hearing, and perfect vision. Life is good on the island.

However, one day a powerful and cruel demon appears and declares that he will kill the inhabitants. But unfortunately for him there are rules that he must follow. He has to let the citizens play for their lives. He must line up all the citizens single-file so they all face the same direction. He must then go about putting black hats and white hats on their heads (he does it randomly, so there is no set number of white or black hats). The citizens are not able to move, but they are able to see every person in front of them, as well as every hat they wear. The citizens are not allowed to gesture or speak until the demon gets to them, and they cannot see behind them. However, they can hear what the others say.

The demon then starts at the back of the line and asks "what color of hat are you wearing?". To which the citizen is allowed to say only "black" or "white", and nothing else. If they are correct, they live. If they are incorrect, they die.

The demon gives them a night to congregate and talk out their plan. The ritual starts in the morning.

What should the citizens do?

Whew, what long riddle. No doubt you're a bit unsure of where to start.

Here are some things to consider:

• The citizens are essentially unable to act until it comes to their turn. When it arrives at their turn, the only thing they are able to do is say "black" or "white". So whatever you do, the response of "black" or "white" has to be telling.
• The citizens are basically super-human. So if you think of an answer that wouldn't work for normal humans, you might actually be okay.

COMMON STRATEGIES (possible answers you may have come up with)

Given that, here are some ideas that I've heard which are good, but not the best response:

• Strategy 1: Say the color of the hat of the person directly in front of you. While everyone things this plan is brilliant at first, unfortunately it doesn't save as many people as you might think. 
  
  Lets say these are the hat colors of the first 6 people:BWWBWB
  B= black hat
  W= white hatHere is how it would play out:1. first person(B) says "white" since the next citizen is wearing a white hat- dies
  2. The second person(W) says "white" because he knows his hat color is white- lives
  3. The third person(W) says "black" because the next person is wearing black- dies
  4. The fourth person (B) says "black" because he knows he is wearing black- lives
  5. The fifth person (W) says "black" because the next person is wearing black- dies
  6. The sixth person (B) says "black" because he knows his hat is black- livesAs we can see, every other person will live, and if the person in between is lucky, he gets to live too. With this method you will save somewhere above 50% of all citizens. The method is not terrible, but given the circumstances there are better methods.
• Strategy 2: Another interesting response I've heard is, "The first person whose turn it is, will pick the color that has the majority".So the first person will look at the number of black and white hats, and see which color is more popular. He would then say "white" if white is the dominant hat color. The rest of the people in line would also say that color. So it would basically be responding with all white, or all black. This is an interesting strategy since it guarantees that at least the majority will survive (51% and upwards). Depending on the demographic of black hat wearers and white hat wearers, this could do better than the previous answer. But is not the best.
• Strategy 3: In this strategy, every person will look at the line ahead of him and say the most common color of hat. This is essentially a mix of the two strategies above. The thought behind it is that in case there is a block of black hats in a majority of white hats such as WWWWWBBB, nearing the end you will be able to account for those black hats with perfect accuracy; which is something strategy 2 had issues with.However great this strategy seems at first, it is ultimately flawed. I'll demonstrate it with an example:If you have this pattern: BWBWBWBWBWBWWith an equal number of black and white hats, you will end up saving no one:
  The first person will see a majority of white hats and say W (and die), the second person will see a majority of black hats and say B (and die), this process continues until everyone dies.

Go ahead, give it a shot.
I'll provide a walkthrough with the answer at this link here (coming soon).