Problem
The Problem
100 prisoners wear hats, each hat a color from a set of 100 colors (each color used at least once, possibly with repeats). Each prisoner can see all other prisoners' hats but not their own. They simultaneously write down a guess for their own hat color.
If at least one prisoner guesses correctly, all are freed. They can strategize beforehand but cannot communicate during the guessing phase.
What's the strategy that guarantees success?