The Countably Infinite Prisoners Problem

There are countably infinitely many prisoners in a prison.A guard tells them that they will play a game the next day. If they win the game, all prisoners will be set free.

[The Game] The guard brings all the prisoners to a big field. Each prisoner will get a hat — either red or white. Each prisoner can see all the other prisoners’ hat colors, but cannot see their own hat color. Then, at the same time, all prisoners must guess their own hat color. They can only answer once, and they must all answer together.

[The winning rule:] If only finitely many prisoners guess incorrectly, the prisoners win. If infinitely many prisoners guess wrong, they lose.

Before the game starts, the prisoners can talk and make a strategy together. But once the game begins, no communication is allowed.

[Problem:] Show that there is a strategy that always lets the prisoners win. You may assume the Axiom of Choice.

Comment

There is a page on wikipedia about this puzzle.

In the game description, you can change: “If only finitely many prisoners guess wrong, they win” to: “If only finitely many prisoners guess correctly, they win” This version of the problem does not require the Axiom of Choice. Why is that? (The answer is explained in Peter Winkler’s book “Mathematical Puzzles”. This solution is so simple.)