The Smurf Problem

This problem is great for making people think. Even "non-math" people can enjoy this one! That is, unless you are bothered by dead smurfs...

An evil wizard has kidnapped 100 smurfs. His evil plan is to line them all up and to give each smurf either a red hat or a blue hat. Then, he will ask each smurf to guess the colour of their hat, starting with the back of the line. If a smurf guesses wrong, then 'poof' he's dead.

The smurfs can see the colours of all hats in front of them and can hear the responses of all smurfs behind them. Suppose that the smurfs had time to talk beforehand and devise a strategy for survival.

Question 1: What is the strategy that minimizes the number of smurf fatalities? And what is the minimum number?

FAQ

Q: Can the first smurf sacrifice himself by yelling out the whole list of colours really quickly?

A: No! Let's assume that if any smurf breaks the rules, then everyone dies! Moreover, this solution would still be (slightly) sub-optimal :) (hint hint).

Q: Can the smurfs use different tones or accents to indicate whether the person in front of them is red or blue? For example, "blue" means the next person is blue and "bluUUuuEEee" means the next person is red.

A: Nice try (Matt Beeson). Let's consider that to be cheating.

Q: Is anything known about the number or red/blue hats, or at least the distribution?

A: Nope, not necessary.

Question 2: What if there are n smurfs and m different colours?

This problem is not mine, and you can probably find the solution on the net, but try not to give in to temptation! The solution is easy enough, though not trivial.

Feel free to contact me with solutions or ideas, or leave a comment below.