The Infinite Hat Puzzle

Prologue¹

“Not bad” the judge murmured reluctantly. He was annoyed by the logician’s triumph, but a sinister grin suddenly spread accross his face. “Maybe, poor logician, there are more lives for you to save yet”

The judge opened the dungeon and revealed a silent line of infinitely many prisoners with panic written on their faces

“Let’s see if luck is on your side this time.”

The Rule

The execution proceeds as follows.

Prisoners stand in a line on the staircase as in the last time, but this time, there are infinitely many of them, and they are ordered as the natural numbers, each wearing either a black or a white hat. The distribution of hats is arbitrary.

Each prisoner can see the hats of all prisoners in front of them, but not their own hat or the hats behind them. For instance, prisoner 0 can see all the hats but their own; prisoner 1 can see all hats but her hat and the hat on prisoner 0’s head, etc. As before, starting with prisoner 0, they must each guess the color of their own hat aloud, one by one. They are allowed to agree on a strategy before the execution begins.

At first sight, the situation looks dire. The strategy which the prisoners developed for the finite case ceases to work, for this time it may be the case that infinitely many prisoners are wearing black and infinitely many prisoners are wearing white. Anouncing the parity of the number of black hats simply does not make sense.

But our logician has secret weapons in his tool box. He decides to open his toolbox and take out one of his most powerful secret weapon:

Axiom of Choice

For a collection $(X_i)_{i\in I}$ of non-empty sets, there is a function $F:\{X_i\mid i\in I\} \to \bigcup_{i\in I}X_i$ s.t. $F(X_i)\in X_i$ for all $i\in I$. This function is known as the choice function.

“With the help of the Axiom of Choice, I might work out something.”

We invite you to think about the puzzle before reading on.

Help from the Axiom of Choice

Let us be a little bit more formal here. We may model a distribution of the black and white hats as a function from the natural numbers to $\{0,1\}$. Let $f:\mathbb{N}\to \{0,1\}$, $f(n) = 0$ means that the n-th prisoner is wearing a white hat, and $f(n)=1$ if his hat is black.

The idea is to define an equivalence relation $E_0$ on the collection of functions: we say for $f,g: \mathbb{N}\to \{0,1\}$, let $fE_0g$ iff they are different on finitely many natural numbers. i.e. $\{n\in \mathbb{N}\mid f(n)\neq g(n)\}$ is finite. Check for yourself that this is indeed an equivalence relation! We are viewing two distributions of hats as $E_0$ equivalent if all but finitely many prisoners agree on the colour of their hats in the two distributions.

Let $[f] = \{g:\mathbb{N}\to \{0,1\}\mid fE_0g\}$ be the equivalence class of $f$. Thus, we may use the Axiom of Choice to obtain a choice function $F$ that chooses an element from each equivalence class. i.e. $F([f])\in [f]$, in particular, this means that $F([f])E_0 f$.

Now we are ready to describe a strategy such that when carried out, only finitely many prisoners would guess wrong. First, let’s observe a nice fact: based on what they see, each prisoner is able to decide which equivalence class the entire distribution of hats is in. Say the distribution is $f$, then our prisoner n knows all but the first n values of $f$. Thus he is able to determine the unique equivalence class, namely $[f]$, such that for any $g\in [f]$, $g$ and $f$ are different only on finitely many natural numbers beyond n.

Let the prisoners agree on a choice function $F$ that chooses an element from each equivalence class in advance. Having decided on their own which equivalence class the distribution of hats is in, say it’s $[f]$, prisoner n makes the guess $F([f])(n)$.

This is a strategy that guarrantees finitely many mistakes! Why? Let’s say the distribution of hats is $f$. For prisoner n, he does not know that the distribution is $f$, for he lacks the information of the first n many hats, but what he does know is which equivalence class the distribution is in. Thus, the collective guesses of the prisoners is modeled by $F([f])$, i.e. the n-th prisoner guesses $F([f])(n)$. Now as $F$ is a choice function, $F([f])\in [f]$ and thus $F([f])$ and $f$ are different only on finitely many natural numbers. meaning that all but finitely many prisoners got their guess right. This is what we wanted.

In case this strategy looks bizzare to you, you are not alone. It involves a blatant application of the Axiom of Choice, which is known for producing weird objects. We will discuss the role of Choice in the last section. But before that, the logician did manage to find a strategy that gurantees finitely many errors, this is of course an achievement. But can we do better? A hint: combine the idea developed here with the optimal strategy from the finite case.

This is the final warning: the next section gives the best strategy.

The Perfect Solution, Except for the Selfless Hero

The idea is to let the first prisoner announce the parity of the number of difference between what he sees and what $F([f])$ is. i.e. if $\{n\mid n>0 \text{ and } f(n)\neq F([f])\}$ is odd, he announces white and otherwise he announces black.

This is a brilliant combination of the ideas. With this information, all prisoners except for the first one are able to reason inductively based on what they heard to make the correct guess of the hat. Look back on Tenyo’s article and convince yourself that this is truly the case.

What if we have no Choice?

Surprisiningly, the logician managed to find a strategy that guarantees at most one error, even in the infinite case. However, the logician’s solution used the Axiom of Choice in a significant way.

Is there a strategy without using the Axiom of Choice that guarantees at most one error? Unfortunately, Geschke, Lubarsky and Rahn showed that this is not the case(Lubarsky 2015; Hardin and Taylor 2008). They found a set theoretic universe where the Axiom of Choice fails, and there is no strategy for the prisoners that guarantees at most one error. In other words, in a Choiceless world, it may well be the case that no strategy guarantees at most one mistake.

Still, interesting questions remain. Is there a strategy without using the Axiom of Choice that guarantees at most k (k>1) errors? To further loosen the requirement, is there a strategy without using the Axiom of Choice that guarantees finitely many errors, i.e. a strategy such that when carried out, only finitely many prisoners get it wrong? It is clear that our optimal strategy satisfies the requirement, but the interesting question is whether such strategies exist without Choice. If the excecutioner deprives us of the right of using Axiom of Choice, what would be the optimal strategy? Personally, I do not know an answer to these two questions. These are for you, the illogicans, to figure out!²

Bibliography

Hardin, Christopher S., and Alan D. Taylor. 2008. “An Introduction to Infinite Hat Problems.” The Mathematical Intelligencer 30 (4): 20–25.

Lubarsky, Robert S. 2015. “Choice and the Hat Game.” Mathematical Logic Quarterly 61 (1-2): 68–80.