I heard this puzzle from a trainee maths teacher while I was doing my teacher training a few years ago. I believe that he had a computer science background, which may be relevant, though you certainly don’t need to know any computer science to find the solution.
Maths knowledge required: None
Puzzle: Somewhat inconveniently, you have been kidnapped.
One minute, you and your nine friends were out on the town, celebrating the unexpected discovery of a new integer between seven and eight; the next, all ten of you were tied up in an abandoned aircraft hangar, very much at the mercy of a worryingly unstable looking kidnapper.
In a decidedly bizarre turn of events (yet a depressingly familiar one for the inhabitants of the land of narrative puzzles), your captor gleefully informs you that your lives now depend on whether or not you can correctly deduce the colours of some hats.
You will be made to stand in a line, each facing the back of the person in front, as seen in this diagram:
Starting at the back, your captor will walk up the line, placing a hat on each person’s head. Each hat will be either magenta or puce, but you will not know how many hats of each colour there are. All combinations are possible, including the possibility that all hats will be the same colour.
No one will know the colour of their own hat. However, the person at the back of the line will be able to see the nine hats worn by those in front, the next person will be able to see eight hats, and so on, up to the person at the front of the line, who will not be able to see any hats at all.
You will then each have the opportunity to say a single word, which must be either “magenta” or “puce”. If you say the colour of the hat that is on your own head, then you will be free to go (after everyone has spoken). If you say the wrong colour, you will be shot.
Words must be spoken separately, at intervals of precisely thirty seconds, as measured out by a clock visible to you all, though the order in which you speak is not specified. If anyone turns around, speaks too soon, says any word other than “magenta” or “puce” or tries to communicate in any way other than through their chosen word (for example, by varying their tone of voice, their speed of delivery, and so on…) then you will all be shot.
Before lining you up, your captor allows you all two minutes to discuss your predicament.
What strategy should you employ?
For the solution to the puzzle, click HERE.
UPDATE: I have edited the problem slightly to make the Mad Hatter more bloodthirsty (i.e. he now shoots everyone if anyone breaks the rules). This closes up the cunning loophole identified by Troy (see the comments below).
* – Not too taxing
** – Requires significant thought
*** – Extremely difficult
!!!! – Requires high level mathematics / Unsolved / Insoluble
Thomas Oléron Evans, 2015