Prisoners Hats Puzzle Answer: 99 Survive [Solved]

Prisoners hats puzzle answer: 99 of 100 prisoners survive for sure, and the first speaker is the only one at risk. The first speaker does not guess his own hat colour. He uses his one word to announce whether the number of red hats he can see is odd or even. Every prisoner after him then works out their own hat colour from that single fact, plus the hats they can see and the true colours already named behind them.

Prisoners Hats Puzzle Answer, Stated Exactly

One hundred prisoners stand in a line, all facing forward, each wearing a red hat or a blue hat. Each prisoner can see every hat in front of them, but not their own hat or any hat behind them. The guard starts at the back and works forward. Each prisoner, in turn, must say exactly one word: “red” or “blue”. A matching word sets that prisoner free. Everyone hears every word spoken.

The night before, the prisoners agree on a plan built on parity, a plain word for whether a count is odd or even. The puzzle is widely listed as a Google interview puzzle. The first speaker counts the red hats he can see. If that count is even, he says “blue”. If it is odd, he says “red”. That is the whole code. His word is not a guess at his own hat. It is a message about the hats in front of him.

How the Prisoners Hats Puzzle Answer Works, Step by Step

The first speaker sends the code

Call the first speaker, at the back, Prisoner 100. He sees 99 hats, counts the red hats among them, and speaks the code word: “red” for an odd count, “blue” for an even count. From that moment, everyone knows the parity of the red hats among those 99 prisoners. Prisoner 100 himself may or may not survive, because his word was chosen by the code, not by his own hat colour, so he has only a 50 percent chance that it matches his hat.

The second speaker decodes it

Now take the second speaker, Prisoner 99. She knows the announced parity for the 99 prisoners in front of Prisoner 100, a group that includes herself. She counts the red hats she can see and compares. If they already have the announced parity, her own hat must be blue, because adding a blue hat changes nothing. If they have the opposite parity, her own hat must be red, because adding a red hat flips the parity. She says her true colour, and she goes free.

Everyone after follows the same rule

Every later prisoner follows the same rule, with one extra fact. They know the announced parity, see the hats in front, and know the true colours already named behind them, because every speaker after Prisoner 100 named their true colour. So they count red hats in two groups: hats seen in front, and hats named truly behind them. If that combined count already has the announced parity, their own hat is blue. If it has the opposite parity, their own hat is red. They say their true colour and go free, all the way to the front of the line.

One detail decides whether the chain works, so state it in the interview. Later prisoners must not count Prisoner 100’s word as his hat colour. His word was a code word, not his colour, and the announced parity already covers the 99 prisoners in front of him.

A Five Prisoner Example, Worked in Full

Five prisoners are easier to follow than one hundred, and the logic is identical. Suppose the hats, back to front, are: Prisoner 5 blue, Prisoner 4 red, Prisoner 3 blue, Prisoner 2 red, Prisoner 1 red.

Speaker	What they know	What they say	Result
Prisoner 5 (first)	Sees 3 red hats ahead, an odd count, so the code word is “red”	“red”	Does not survive, because his own hat is blue
Prisoner 4	Announced parity is odd. Sees 2 red hats ahead, an even count, so her hat must flip it to odd	“red”	Survives
Prisoner 3	Announced parity is odd. Sees 2 red hats ahead and 1 red hat named truly behind her, 3 in total, already odd	“blue”	Survives
Prisoner 2	Announced parity is odd. Sees 1 red hat ahead and 1 red hat named truly behind him, 2 in total, even, so his hat must flip it to odd	“red”	Survives
Prisoner 1	Announced parity is odd. Sees no hats ahead and 2 red hats named truly behind him, 2 in total, even, so his hat must flip it to odd	“red”	Survives

Four of the five survive, and the only loss is the first speaker, as promised. Scale the same table to one hundred prisoners and the result is 99 survivors. Compare the weaker plans. If every prisoner simply guessed, about half would survive on average and nothing could be guaranteed. In pairs, with the back prisoner naming the front prisoner’s colour, only 50 survivors would be guaranteed. The parity plan beats both, because one word protects all 99 prisoners behind the message, not just one partner.

The Traps That Catch Good Candidates

The first trap is letting the first speaker guess his own hat. That wastes the one word on a 50 percent guess and leaves the other 99 prisoners with no shared fact to work from. The word must carry information about the group, not a guess about one person.

The second trap is counting the first speaker’s word as his hat colour in later steps. His word means “the red hats ahead are odd” or “the red hats ahead are even”. It does not mean “my hat is red” or “my hat is blue”. Later prisoners count only hats they can see and colours named truly by speakers after the first.

The third trap is claiming that all 100 prisoners can be guaranteed. No plan can do that, and the next section shows why. The fourth trap is skipping the small case: if a plan fails for 2 or 3 prisoners, it will fail for 100.

Why All 100 Cannot Be Guaranteed

Here is the proof, in plain words. The first speaker’s word depends only on the hats he can see, because he cannot see his own hat. Imagine two handouts that are identical in front of him but differ only in his own hat colour: red in one, blue in the other. He sees the same hats in both cases, so any fixed plan makes him say the same word in both cases, and that word can match his hat in at most one of them. So no fixed plan can guarantee his survival. The best any plan can do is guarantee the other 99, and the parity plan reaches that best result.

One word has only two values, so it can carry only one binary fact. The plan spends that fact on the whole group, worth 99 guaranteed survivors, instead of on one guess.

What the Interviewer Is Testing in the Prisoners Hats Puzzle Answer

The interviewer is testing whether you can turn a single word into shared information. They watch whether you start with the smallest case instead of jumping to 100, whether you state the code clearly before you use it, and whether you track exactly what each prisoner knows at their turn. They also watch whether you are honest about the limit: a strong candidate says plainly that the first speaker cannot be guaranteed, and proves why.

Practice Variations Before the Interview

Test the method on smaller lines first. With 2 prisoners, the first speaker announces the parity of the 1 hat he sees, and the second prisoner deduces their own hat at once. With 3 prisoners, the same steps guarantee 2 survivors. If the code is flipped, so even means “red” and odd means “blue”, the plan still works, as long as everyone agrees on the code in advance.

Can the first prisoner survive too?

Sometimes, by luck. If the code word happens to match his own hat, he goes free too, and all 100 survive in that handout. But no plan can guarantee it. The honest answer is 99 guaranteed, 100 possible.

What if the first speaker miscounts?

Then the announced parity is wrong, and every later deduction inherits the error. The plan needs perfect counting and a code agreed in advance.

Does the plan work if prisoners cannot hear each other?

No. Every word must be heard by everyone still waiting, or the chain breaks.

One More Puzzle to Try

If you liked reasoning about what each person knows, try the Blue Eyed Islanders Puzzle: Answer [Solved], where a public sentence starts a 100 night countdown. Or test your weighing logic with the 12 Balls Puzzle Answer: Find the Odd Ball in 3 Weighings [Solved]. For a probability twist, try the Ants Triangle Puzzle Answer: 1 in 4 [Solved].