1. Monsters and Hats I
Setup
100 prisoners stand in a row, all facing forward.
Each wears a Red or Black hat.
Each can see all hats ahead, but not their own or those behind.
Rules
- Prisoners agree on a strategy beforehand
- Each says only one word: "Red" or "Black"
- Speaking starts from the back and proceeds forward
Question
What is the maximum number guaranteed to guess correctly?
Answer format
Enter a whole number.
Your Answer
Need help?
Hint 1
The last monster in line (who speaks first) can see all 99 hats in front of them.
Hint 2
Think about using parity (odd/even) to encode information.
Hint 3
If the first speaker announces a color based on whether they see an odd or even count of that color, how can others use this?