For me, this is one of those puzzles in which the answer is beautiful because it seems so counter-intuitive. Despite the fact that the information available to the captives appears to be desperately limited, there is in fact a strategy that is guaranteed to save nine out of the ten people in line, with a decent chance of saving all ten.

Read on for an explanation of how to solve the problem logically, or scroll to the bottom for the solution.

Initially, the situation seems pretty hopeless. If anyone uses their word to give information to someone else (by saying the colour of the hat immediately in front of them, for example), then it seems that they are giving up their chance to save themselves by saying the colour of the hat that is on their own head. However, this line of reasoning fails when we realise that, in a strategy in which most people are correctly identifying the colour of their own hat, the word that each person says is itself a piece of information about the complete ‘system’ of ten hats, which could be used by those in front of them.

First off, guaranteeing the survival of nine out of ten of the captives is definitely the best that we can hope for. Clearly, there is nothing whatsoever that the person at the back of the line can do to work out the colour of their own hat. Whatever they say, it is a shot in the dark. It follows that they should use their word to give as much information as possible to the other captives. Indeed, if it is possible to guarantee the safety of the other nine (and it is), the person at the back is, in some sense, the only person who can use their word to give any direct information to the others about the colours of their hats.

It is also clear that, if we are to guarantee the safety of nine people, the person at the back must speak first. Before anyone has spoken, no one has enough information to deduce the colour of their own hat, but we want everyone but the person at the back to be sure of their colour before they speak. So the person at the back will speak first.

Who will speak next? Well, the penultimate person in the queue now has all the information that they are ever going to have. They know the colour of all eight hats in front of them and they have heard the word spoken by the one behind. If they don’t know the colour of their hat at this point, they never will, so they should speak next. A similar logic suggests that the captives should speak in the order in which they are standing, from the back of the line to the front.

Now, if the front nine people all say the correct colours, then when each person speaks they will know two things:

• a) The colour of every hat except their own (and that of the person at the back);
• b) The word spoken by the person at the back (“magenta” or “puce”).

Since the first piece of information is clearly independent of the colour of their own hat, it follows that, given their knowledge of all the other hats in the line, the second piece of information must perfectly distinguish between the their two possible hat colours (again, if we are to guarantee saving nine out of ten). In other words, if the colour of any one of the front nine hats were to be changed, with all others remaining the same, then the decision for the person at the back over whether to say “magenta” or “puce”, must also change.

The only way that this is possible is if the person at the back says “magenta” if they can see an even number of magenta hats and “puce” otherwise (or vice versa). In this case, when each person speaks, they will know whether the person at the back can see an even or odd number of magenta hats, and they will also know how many magenta hats there are among the other eight. This is enough information to tell the colour of their own hat.

Solution:

• The person at the back speaks first, saying “magenta” if they can see an even number of magenta hats and “puce” otherwise.
• The person immediately in front of them can see eight hats and knows whether these eight, along with their own hat, include an even or odd number of magenta hats. This is enough information to deduce the colour of their own hat, so they say its colour.
• The person immediately in front of them can see seven hats and knows the colour of the hat immediately behind them. They also know whether these eight hats, along with their own, include an even or odd number of magenta hats. This is enough information to deduce the colour of their own hat, so they say its colour.
• The same logic allows us to proceed to the front of the line, with everyone saying the colour of their own hat. The front nine people are saved, and the person at the back may also be saved, if they are lucky.

Thomas Oléron Evans, 2015