| easy | strategy |
One hundred prisoners are lined up, facing one direction and assigned a random hat, either red or blue. Each prisoner can see the hats in front of them but not behind. Starting with the prisoner at the back of the line and moving forward, they must each, in turn, say only one word which must be "red" or "blue". If the word matches their hat color they are released, if not, they are kept imprisoned. They can hear each others' answers, no matter how far they are on the line, but they do not hear the verdict (whether the answer was correct). A friendly guard warns them one night before, giving them enough time to come up with a strategy. How many prisoners can be freed using the best strategy?
Assume that there is an unknown number of red & blue hats.
The prisoner at the back can count the number of each color and convey some information to the next.
99 of the 100 prisoners can be freed, and 1 has a 50:50 chance of freedom.
We can number prisoners from 100 to 1, with 100 being the last person in the line. Prisoners agree that if the person will say "red" if there are an even number of "red" hats visible on the prisoners 1 to 99, and blue otherwise. This way, prisoner number 99 can look ahead and count the red hats. if they add up to an even number and the number 100 said “red”, then 99 must be wearing a blue hat. if they add up to an even number and number 100 said “blue”, signaling an odd number of red hats, number 99 must also be wearing a red hat.
Similarly, number 98 knows that 99 said the correct hat, and so uses that information along with the 97 hats in the front to figure out their own hat's color. This can continue till the first prisoner.
This strategy will free 99 prisoners. But the prisoner has to rely on luck and has a 50:50 chance of being right.
Notes:
-
If a prisoner decides to give an incorrect answer on purpose, then all the successive prisoners end up giving an incorrect answer. Unless there is another corrupt prisoner who inverts the parity.
-
In an alternative universe, the friendly guard informs the prisoners that both colors are even. All one hundred prisoners can be freed.