Each prisoner is missing exactly one piece of information: their own hat. Pairing them turns two uncertainties into one guaranteed correct answer.
The Hats and the Even Sum
Riddle statement
There are 100 prisoners.
Each prisoner is given either a white or a black hat.
Each prisoner can see the other 99 hats, but cannot see their own.
All prisoners must simultaneously announce the color of their own hat.
Beforehand, they may agree on a strategy.
Can they guarantee that at least 50 of them are correct, no matter what happens?
Show solution
Solution
Yes. They can guarantee exactly 50 correct answers.
Divide them into 50 pairs $(A_i,B_i)$.
In each pair they agree on this rule:
- $A_i$ will say that their hat has the same color as $B_i$'s hat;
- $B_i$ will say that their hat has the opposite color from $A_i$'s hat.
Each prisoner can apply the rule because they can see their partner's hat.
If the two hats in the pair have the same color, $A_i$ is correct and $B_i$ is wrong.
If they have different colors, $A_i$ is wrong and $B_i$ is correct.
In every pair exactly one person is correct. Since there are 50 pairs, exactly 50 prisoners are correct.
Answer: yes. Pairing them with complementary rules guarantees exactly 50 correct answers.