Infinitely Many Hats and the Axiom of Choice
With infinitely many prisoners wearing hats and a clever pre-agreed strategy built from the axiom of choice, all but finitely many prisoners can guess their own hat color correctly — a genuinely surprising result once you see how the strategy works.
Take a countably infinite line of prisoners, each given a hat colored from some finite set, unable to see their own hat but able to see everyone else's. Each must guess their own hat color simultaneously, with no communication once hats are placed, but they may agree on a strategy in advance. The surprising claim: a strategy exists under which only finitely many prisoners guess wrong — no matter how the hats are assigned.
The trick uses the axiom of choice. Group all possible infinite hat-color sequences into equivalence classes, where two sequences are equivalent if they differ in only finitely many positions. The axiom of choice lets the prisoners pick, in advance, one representative sequence from each class — an act that is not constructive (nobody can actually write down the choices for uncountably many classes) but is guaranteed to exist. Each prisoner then compares what they see to the representative of the class it looks like it belongs to, and guesses as if the true sequence matches that representative exactly.
Because the true hat sequence differs from its class's chosen representative in only finitely many places, agreeing in advance on one representative per equivalence class guarantees only finitely many prisoners are wrong — even though no one can see their own hat.
The puzzle is a favorite in interviews for testing whether a candidate can hold two ideas at once: the strategy is mathematically valid, and it is also completely non-constructive, which is exactly the point the axiom of choice is famous for.
Practice in interviews
Further reading
- Hardin & Taylor, 'The Mathematics of Coordinated Inference'