10 prisoners are lined up single file, facing forward. Each prisoner has either a red or blue hat randomly placed on their head. No one can see their own hat or any hats behind them, but prisoners can see all hats in front of them.

Starting from the back of the line, each prisoner can guess the color of their hat out loud (“red” or “blue”). Prisoners guess correctly are freed. Everyone can hear every guess.

The prisoners can strategize beforehand, but are not allowed to communicate once it’s started. What strategy would save the most prisoners, and how many are saved on average?


Solution

9 prisoners are guaranteed to go free, and the last prisoner has a 50% chance.

The last prisoner counts the red hats in front of them. If the number is odd, guess “red,” otherwise guess “blue.”

The 2nd last prisoner now knows whether there’s an odd or even number of red hats left, including theirs. They can also count the red hats in front of them, so they can work out with certainty what color their own hat is.

Every other prisoner knows whether the original 9 had an odd or even number of red hats, and has heard every other prisoner’s correct guess, so they can also work out with certainty what color their own hat is.

E.g., the last prisoner guesses “red” (odd). The next prisoner sees 4 red hats in front of them (an even number), so their own hat must be red.

This is the best possible solution, because the last prisoner can get no information on the color of their own hat, so their guess is at best 50%.

Leave a Reply

Your email address will not be published. Required fields are marked *