Hats in a line when nobody can hear

Question

A hundred prisoners stand in a line. Each wears a red or blue hat, chosen by the warden. Each prisoner can see every hat in front of them, but not their own and not the ones behind. Starting from the back, each prisoner whispers a guess of their own hat colour to a guard. Nobody can hear anyone else's guess, and the guard gives no reaction.

The prisoners may agree a strategy beforehand. The warden knows the strategy and chooses the hats.

What is the largest number of prisoners that any strategy can guarantee to save? Then: if instead the hats are assigned by fair coin flips, how many survive on average?

Accepted Answer

Zero can be guaranteed. With random hats, 50 survive on average, whatever the strategy. Why nothing can be guaranteed. Any strategy tells each prisoner what to say as a function of what they can see: the hats in front of them. Nothing else reaches them, since they hear no answers. Now let the warden assign hats from the front of the line to the back. She starts with the frontmost prisoner, who sees nothing, so his guess is fixed in advance; she gives him the opposite colour. Next she considers the second prisoner from the front, whose guess depends only on the frontmost hat, which is already …

Hats in a line when nobody can hear

Your answer

Discussion

Learn the concepts

Related questions