Countably many people stand in a line indexed 1, 2, 3 and so on. Each wears a black or white hat and can see every hat except his own. All shout a guess at the same moment. Assuming the axiom of choice, what can they guarantee?

Countably many people stand in a line indexed 1, 2, 3 and so on. Each wears a black or white hat and can see every hat except his own. All shout a guess at the same moment. Assuming the axiom of choice, what can they guarantee?

Approach: Group hat sequences that differ in finitely many places into one class and agree on a single member of each class before the hats are placed.

All but finitely many guess correctly. Call two hat sequences equivalent when they differ in finitely many coordinates, which is an equivalence relation on {0,1}^N. Before the hats go on, the axiom of choice fixes one representative sequence in each class. Each person sees all hats except his own, and changing one coordinate never leaves the class, so he knows exactly which class the true sequence lies in. He announces the entry of that class representative at his own index. The true sequence and the representative differ in finitely many places, so only finitely many people are wrong. No individual beats 1/2 for himself, and the strategy is not constructive, since no explicit choice function on these classes exists.

Follow-up: If instead each person sees only the hats with larger index, how many can be guaranteed correct?

Key concepts: axiom of choice, equivalence classes, representative sequence.