The Hat Puzzle, or How Logic Saves Lives

Prologue

In a dim room, 100 prisoners sat in various poses, wracking their brains. Everyone looked desperate, except for one prisoner who was strangely excited by the situation: the logician.¹

“We should use logic—” someone began.

“No, that’s useless!” another interrupted.

The logician considered this. “Well, not always.”

They were scheduled to be executed the next morning. The method was well known. That was why they were gathered here, trying to save themselves or, in the worst case, as many lives as possible.

The Rules

The execution proceeds as follows.

All 100 prisoners stand in a line on a staircase, each wearing either a black or a white hat. The distribution of hats is arbitrary: it could be all black, all white or any combination in between. The prisoners do not know it in advance.

Each prisoner can see the hats of all prisoners in front of them, but not their own hat or the hats behind them. Let us count the prisoners from the top of the staircase, as mathematicians often do, starting from 0. Thus, prisoner 0 can see 99 hats, prisoner 1 can see 98 hats, and so on, until prisoner 99, who can see no hats at all.

Starting with prisoner 0, they must each guess the color of their own hat aloud, one by one. A prisoner survives if their guess is correct; a wrong answer costs their life. Everyone can hear the guesses that have already been made, but no one hears the judge’s verdicts. In other words, prisoner 23 knows what prisoners 0 through 22 said, but not whether any of them survived.

The prisoners are not allowed to communicate any extra information once the execution begins. They may say only “black” or “white” on their own turn. However, before the hats are placed on their heads, they may agree on a strategy that gives special meaning to those words. The judge does not know or care about such a convention; the judge only checks whether the spoken word matches the speaker’s own hat.

The prisoners are seeking the best possible strategy. A strategy is better if it guarantees more survivors in the worst case.

At first sight, the situation looks hopeless. Without any strategy, each prisoner can only guess randomly. In the worst case, no one may survive. Can we do better?

Try to think about the puzzle before reading on. You are in the same position as the logician, although perhaps with a more comfortable chair.

A First Try

A simple strategy improves the situation: every other prisoner sacrifices themselves by announcing the color of the next prisoner’s hat.

Here is how it works. Prisoner 0 can see prisoner 1’s hat, so prisoner 0 says that color aloud. Prisoner 1 hears this and repeats it, thereby saving themselves. Similarly, prisoner 2 saves prisoner 3, and so on. With this strategy, prisoners 1, 3, 5, …, 99 all survive. The others may or may not. In the worst case, at least 50 prisoners survive.

“Not bad,” the logician thought, “but can we do better than this?”

The weakness of this strategy is that it keeps starting over. Prisoner 0 gives useful information to prisoner 1, but prisoner 1’s answer adds nothing new for prisoner 2, even though prisoner 2 can hear it. So prisoner 2 has to begin again by sacrificing themselves to save prisoner 3, and the same pattern repeats.

To improve the strategy, we should ask for more from each answer. Ideally, prisoner 1’s answer should both save prisoner 1 and help prisoner 2. This suggests the following question:

What information can prisoner 0 give so that prisoner 1 can determine their own hat color, and prisoner 2 can also determine their own hat color by combining prisoner 0’s message with prisoner 1’s answer?

Again, it is worth pausing here before reading the next section.

A Better Idea

The key is that prisoner 0 does not need to tell prisoner 1’s hat color directly. Instead, prisoner 0 can describe the relationship between prisoner 1’s hat and prisoner 2’s hat.

Suppose prisoner 0 says “black” to mean “prisoners 1 and 2 have the same hat color”, and says “white” to mean “prisoners 1 and 2 have different hat colors”. This is allowed: prisoner 0 is still only saying one of the two permitted words.

Now prisoner 1 can survive. Prisoner 1 sees prisoner 2’s hat. If prisoner 0 said that the two hats are the same, prisoner 1 says the color they see on prisoner 2. If prisoner 0 said that the two hats are different, prisoner 1 says the opposite color.

Prisoner 2 can also survive. Prisoner 2 cannot see prisoner 1’s hat, but prisoner 2 can hear prisoner 1’s correct answer. Together with prisoner 0’s message, this tells prisoner 2 their own hat color.

This gives a strategy for groups of three. Prisoner 0 encodes whether prisoners 1 and 2 are the same or different; prisoner 3 does the same for prisoners 4 and 5; and so on. The prisoners can guarantee two survivors in each block of three. Since 99 is left over at the end, this guarantees at least 66 survivors.

This is a significant improvement over 50. However, the logician was still not satisfied.

“We saved 16 more lives,” they thought, “but who wants to be prisoner 0, 3, 6, …, or 96?”

The issues of the previous strategy are reduced but still remain. Prisoner 0 can see the hats of prisoners 1 through 99, but the strategy uses only the relation between prisoners 1 and 2. All the information about prisoners 3 through 99 is thrown away. Moreover, the information flow stops after prisoner 2, so prisoner 3 must start a new little scheme.

What we want is a single stream of information running all the way down the staircase. Prisoner 0 should give one piece of information about the whole line. Prisoner 1 should use it to survive, and then prisoner 1’s answer should help prisoner 2. Prisoner 2 should do the same for prisoner 3, and so on.

At this moment, an excellent and terrifying idea struck the logician. It took them a while to be brave enough to share it with the other prisoners.

This is the final warning: the next section gives the best strategy.

The Perfect Solution, Except for the Selfless Hero

The logician’s idea is to use the parity of the number of black hats. Instead of describing many hats separately, prisoner 0 says whether the total number of black hats in front of them is even or odd.

Here is the agreed strategy:

• If prisoner 0 sees an even number of black hats among prisoners 1 through 99, prisoner 0 says “black”.
• If prisoner 0 sees an odd number of black hats among prisoners 1 through 99, prisoner 0 says “white”.

The words “black” and “white” could be swapped. The important point is that the first answer encodes one bit of information: even or odd. Prisoner 0’s own survival is not guaranteed, but everyone else can use this initial parity information.

Let us see how prisoner 1 uses it. Suppose prisoner 0 said “black”, meaning that among prisoners 1 through 99 there is an even number of black hats. Prisoner 1 counts the black hats they see among prisoners 2 through 99. If prisoner 1 sees an even number, their own hat must be white; if prisoner 1 sees an odd number, their own hat must be black. Thus prisoner 1 can determine their own hat color exactly.

The same reasoning works if prisoner 0 said “white”, except that the target parity is odd rather than even.

Now consider prisoner 2. Prisoner 2 heard prisoner 0’s parity announcement and prisoner 1’s correct answer. Combining these, prisoner 2 can calculate what the parity must be among prisoners 2 through 99. Then prisoner 2 counts the black hats they can see among prisoners 3 through 99. The difference tells prisoner 2 whether their own hat is black or white.

This procedure continues down the entire staircase. Each prisoner knows the original parity, hears all previous answers, and sees all later hats. Therefore, on their turn, each prisoner from 1 through 99 can determine whether their own hat is the missing contribution needed to make the parity come out right.

Even prisoner 99, who sees no hats, is saved by the accumulated information. By the final turn, all other hats from 1 through 98 are known, and the original parity tells prisoner 99 whether their own hat must be black or white.

Thus, the prisoners can guarantee that at least 99 of them survive, no matter how the hats are arranged. Only prisoner 0 remains at risk.

This is optimal. Prisoner 0 has no information about their own hat color. If prisoner 0 would say “black” in a given situation, the judge could have placed a white hat on prisoner 0 without changing anything prisoner 0 can see or hear before speaking; similarly for the other color. So no strategy can guarantee prisoner 0’s survival. At most 99 prisoners can be guaranteed, and the parity strategy achieves this bound.

One obvious problem remained, and the logician had an obvious solution.

“Not many logicians have contributed to the real world,” said the logician. “I will stand at the top of the staircase.”

Epilogue, and More Prisoners

This closes our story. The strategy generalizes to any finite number of prisoners. If there are $m$ prisoners for $m \geq 1$, the same parity argument guarantees that at least $m-1$ survive in the worst case, which is optimal.

“But wait,” says a mathematician. “What if there are infinitely many prisoners?”