Infinitely many prisoners, only finitely many die

Question

An infinite line of prisoners stands numbered 1, 2, 3, ... Each wears a red or blue hat. Prisoner n can see the hats of every prisoner with a larger number (all of them, infinitely many) but not their own or anyone behind. At a signal, everyone guesses their own hat colour at the same moment. There is no communication of any kind once the hats are on. The prisoners may agree on a strategy beforehand, and they are allowed to assume the axiom of choice. Show that there is a strategy under which only finitely many prisoners guess wrongly, no matter how the hats are assigned. This is genuinely su…

Accepted Answer

The strategy. 1. Group the possible hat sequences into families. Say two sequences of colours are in the same family if they differ in only finitely many positions. Being in the same family is an equivalence relation: every sequence is in its own family, and if X differs from Y in finitely many places and Y from Z in finitely many places, then X differs from Z in finitely many places too. 2. Choose a representative for every family. Before the hats go on, the prisoners agree, for each family, on one particular sequence from that family to call "the representative". There are uncountably many …

Infinitely many prisoners, only finitely many die

Your answer

Discussion

Learn the concepts

Related questions