113. Colored Hats
A warden lines up a group of 30 prisoners so they can see everybody in front of them and nobody behind them, then places either a red or a blue hat on each of their heads, randomly. He then goes from the back of the line to the front, telling each prisoner to guess the color of their own hat. Each who guesses correctly is freed. The prisoners cannot see the color of their own hat, and cannot communicate with each other, but can hear each others' guesses and can strategize beforehand. What strategy saves the greatest number of prisoners?
Submitted by tartle · Added 29 August 2016
Solution:
The prisoners can use the parity of the number of red hats they see in front of them to communicate. The last prisoner in line counts the number of red hats in front of him and announces 'red' if the count is odd and 'blue' if it is even. Each subsequent prisoner can then deduce their own hat color based on the previous guesses and the number of red hats they see, allowing at least 29 prisoners to be freed with certainty.
Comments (0)
No comments yet. Be the first!
Add a Comment or Suggest an Answer