Many hat puzzles have only two colors: white or black. But the deep idea in this problem does not depend on having just two options. Even with infinitely many possible colors, a collective strategy can control almost all errors.
The Hats with Infinitely Many Colors
Riddle statement
There are infinitely many prisoners standing in a line, numbered:
Each prisoner wears a hat of some color. There may be infinitely many possible colors.
Each prisoner can see all the hats of the prisoners in front of them, but cannot see their own hat or the hats behind them.
Before the hats are placed, they may agree on a strategy.
Then all prisoners, simultaneously, must announce the color of their own hat.
Can they guarantee that only finitely many prisoners are wrong, no matter what happens?
Show solution
Solution
Yes, they can.
The idea is the same as in the black-and-white version, but more surprising: it does not matter how many possible colors there are.
Call two infinite hat configurations equivalent if they differ in only finitely many positions.
For example, even if there are many possible colors, two rows are in the same class if from some point onward they always match, except perhaps at a few isolated places.
Before the game begins, the prisoners choose one representative for each equivalence class.
When a prisoner looks forward, they see all hats except for finitely many: their own hat and the hats behind them.
Therefore, from what they see, they can determine which equivalence class the real configuration belongs to.
They then announce the color that the chosen representative has in their position.
Since the real configuration and the representative are in the same class, they differ in only finitely many positions.
The prisoners at those positions may be wrong. Everyone else is correct.
Answer: yes. Even with infinitely many colors, they can guarantee that only finitely many prisoners are wrong.