There are 100 prisoners, each lined up in a row, and each prisoner is wearing a hat that is either red or blue. The prisoners can see everyone’s hat except their own.
The warden will start at the back of the line (prisoner #100) and ask each prisoner to guess the color of their own hat. If they guess correctly, they are freed; if they guess incorrectly, they are executed. The prisoners can only communicate beforehand and have no further opportunity to communicate after the guessing begins.
What strategy can they use to guarantee that at least 99 prisoners survive?
The Prisoners and Hats Riddle
Hint:
The key is to use parity (odd or even number of hats of a certain color) to communicate information without directly saying anything. The prisoners can use the first prisoner’s guess as a reference for all others.
The first prisoner (at the back of the line) will announce the color of their own hat based on the parity of the red hats they see in front of them. From that, each subsequent prisoner can figure out their own hat color.
The Strategy: Use Parity (Odd or Even) of Red Hats
Before the guessing begins, the prisoners agree on a strategy:
The First Prisoner’s Role (at the back): The first prisoner (prisoner #100) will say “red” or “blue” based on the parity of red hats they see in front of them. This means:
If the first prisoner sees an odd number of red hats in front of them, they will say “red”.
If the first prisoner sees an even number of red hats in front of them, they will say “blue”.
The first prisoner’s guess may be incorrect, but it provides vital information for the rest of the prisoners.
Subsequent Prisoners’ Strategy (starting from prisoner #99): Each following prisoner knows the color of all the hats in front of them and can count how many red hats they see. They also know the first prisoner’s statement about the parity of the red hats.
The second prisoner (prisoner #99) listens to the first prisoner’s guess and counts the red hats they can see. If the first prisoner said “red” (meaning an odd number of red hats), the second prisoner knows that they need to adjust their count if their own hat is red (since adding their own red hat would flip the parity). If the first prisoner said “blue” (meaning an even number of red hats), the second prisoner checks if their hat would make the number of red hats odd or even.
Each subsequent prisoner (prisoner #98, #97, etc.) follows this pattern, adjusting their own guess based on the number of red hats they see and the parity communicated by the first prisoner. They compare the actual parity with what the first prisoner’s statement suggested.
The Result:
The first prisoner has a 50% chance of guessing correctly since their guess is based purely on parity.
The remaining 99 prisoners will always guess correctly, because they have enough information from the previous guesses and the hats they can see.
How Many Survive?
99 prisoners will always survive, and the first prisoner has a 50% chance of survival, so at least 99 prisoners will be freed.
