100 prisoners guessing hat colors in a line

Question

100 prisoners stand in a line. Each wears a hat that is red or blue (assigned adversarially). Each prisoner sees the hats of everyone in front of them but not their own or those behind. Starting from the back (who sees the other 99), each prisoner in turn calls out a single guess, "red" or "blue", loud enough for all to hear. A prisoner survives if their guess matches their own hat. The prisoners agree on a strategy beforehand. They cannot pass or say anything but a color. How many prisoners can be guaranteed to survive, and how?

Accepted Answer

99 prisoners can be guaranteed to survive; the back one has a 50/50 shot. The strategy, parity. Agree that "red = 1, blue = 0." The back prisoner counts the parity (even/odd) of the number of red hats among the 99 hats in front of them and announces: - "red" if that count is odd, - "blue" if that count is even. This guess may or may not match the back prisoner's own hat, they're sacrificing themselves to broadcast one bit: the parity of the front-99 reds. Everyone else now deduces their hat. Consider prisoner 99 (second from back). They see the 98 hats in front of them and heard the announced…

100 prisoners guessing hat colors in a line

Your answer

More Brainteasers questions