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.
Difficulty: **
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:
Arrows indicate the direction in which each person is facing.
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).
DIFFICULTY RATINGS:
* – Not too taxing
** – Requires significant thought
*** – Extremely difficult
!!!! – Requires high level mathematics / Unsolved / Insoluble
IMAGE: Rajeevvadakkedath
Thomas Oléron Evans, 2015
Nobody has visibility of the person’s hat at the end of the line except for the Mad Hatter, and his only response is to let that guesser live or to shoot the person. I will line up at the end, shout the number generated by treating puce = 1 and magenta = 0, and then converting to binary, and die knowing nine others know their hat’s color without guessing.
Cunning, though not what I intended. Good thinking, but I have edited the text slightly to exclude this option. In any case, there is an unambiguously better strategy…
NOOOOOO!! Is there no end to his madness?!?!
I know. What can I say. Bad guys break the rules.
My next thought was not completely right either, but I feel like it is closer:
Guess the color opposite all forward unguessed hats once all remaining are the same color and only silence from behind.
This doesn’t account for the first and last person though, and listening for silence may violate the timer condition.
Another nice idea. However, as you say, it is scuppered by the timer.
What… ??
None may have information about the hat of the 1st person (who sees everyone else) if no information on at least the parity of hat type is provided.
I really don’t see how the 1st person could ever make a statement which is not a coin flip in this case.
This is a fair point, which should be taken into account. The question only asks for the best possible strategy, it does not say how good that strategy might be.
Hum, ok, good enough… Then, I guess that the discovery of a new integer between 7 and 8 must be unfortunately tied to a 50% probability of living or diying.
I won’t post my solution too early to avoid spoil 🙂