by Venanzio on November 19, 2012.
Tagged as: Lunches, Puzzles.
There is a jail containing a countably infinite number of inmates. Because of budget cuts, the government is closing it down. The prisoners will either be all released or all executed. The decision depends on whether they pass a certain test.
On the fatal day, the inmates are allowed to agree a common strategy beforehand, but they can't communicate during the test itself. They will be put in a (very) long line and coloured hats, either black or red, will be put on their heads. A prisoner cannot see the colour of his own hat, but he can see the hats of all the infinite people in front of him. Afterwards, each of them is taken to a separate room and must guess his own hat's colour.
If only a finite number of them guess wrongly, then they pass the test and they all go free. But if they make an infinite number of wrong guesses, then they will all be executed.
Now: do you think that the inmates can agree on a strategy that will guarantee their success?
Note: These prisoners have very good eyesight: they can see an infinite sequence of hats in front of them. They also can compute everything that exists in classical mathematics, even if it's not computable by finite means. They have a very very large memory. In other words, each of them has the mind of God.
Here is how the prisoners can agree on a winning strategy beforehand. Let's define an equivalence relation on the infinite sequences of hat colours: Two sequences are equivalent if they differ only on a finite number of positions. It is easy to verify that this is an equivalence relation. Therefore it partitions the set of all sequences into equivalence classes. The prisoners agree on a choice of a specific representative for each equivalence class. At the time of the test, each prisoner can see the the whole sequence except the initial positions up to his own. This is enough to determine the equivalence class. Then the prisoner will give as answer the colour given to its position by the chosen representative in that class. This ensures that they all choose according to the same representative sequence, and this sequence is equivalent to the actual sequence of hat colours. These will then differ only on a finite number of positions, that is, there will be only a finite number of mistakes.
This solution is so clever that it's not measurable by human standards. In fact, here is a proof by Christian that there cannot be a measurable strategy.
Let \(C = 2^{\mathbb{N}}\) denote the hat configuration space. Let there be a fixed strategy \(s : C \to C\) with non-negative probability of winning with the constraint that each prisoner cannot see their own and previous hats, i.e. \(s\ c\ n = s\ d\ n\) if \(c\ m = d\ m\) for all \(m > n\) (1). Abbreviate \[A = \{ c : C \mid \{ n : \mathbb{N} \mid c\ n = \operatorname{false} \}\ \text{finite}\ \},\] \[B_n = \{ c : C \mid c\ m = \operatorname{true}\ \text{forall}\ m \geq n \}.\] Since \(A = \bigcup_{n : \mathbb{N}} B_n\), the probability of the prisoners winning is given by \[\mathbb{P}(s(X) \operatorname{eq} X \in A) = \lim_n \mathbb{P}(s(X) \operatorname{eq} X \in B_n),\] where \(X\) is a random variable denoting the hat configuration, and \(\operatorname{eq}\) is the equality operator on booleans (or hat colours). Formally, \(\mathbb{P}(X \in D)\) is defined to mean \(\mu(D)\), where \(\mu : \sigma(C) \to [0, 1]\) is the measure generated by \(\mu(S_n) = \frac{1}{2}\) and \(\sigma(C)\) is the \(\sigma\)-algebra generated by \(S_n\) where \(S_n := \{d\in C \mid d\ n = \operatorname{true}\}\) for \(n : \mathbb{N}\). Here, in talking about \(\mathbb{P}(s(X) \operatorname{eq} X \in B_n)\), we have crucially assumed that \(s\) is a measurable function.
Fix \(n : \mathbb{N}\) such that \(\epsilon := \mathbb{P}(s(X) \operatorname{eq} X \in B_n) > 0\) and abbreviate \(t\ c = s\ c \operatorname{eq} c\). For \(m > n\), let \(E_m\) denote \(t^{-1}(B_n)\) with all its elements flipped at hat \(m\).
The \(E_m\) are all disjoint: Suppose \(E_{m_1}\) and \(E_{m_1}\) have a common element. This means that there are two sequences \(c_1, c_2 \in t^{-1}(B_n)\) whose only differences on indices larger that \(n\) are at positions \(m_1\) and \(m_2\). The last difference between them is at \(n' = \max(m_1,m_2) > n\), so \(c_1\ k = c_2\ k\) for \(k>m\). By (1) this implies that \(s\ c_1\ n' = s\ c_2\ n'\). We also know (because \(n'>n\)) that \(t\ c_1\ n' = t\ c_2\ n' = \operatorname{true}\), that is, \(c_1\ n' = s\ c_1\ n' = s\ c_2\ n' = c_2\ n'\). This contradict the assumption that \(c_1\) and \(c_2\) differ at position \(n'\).
But then \[1 \geq \sum_{m > n} \mu(E_m) = \sum_{m > n} \mu(t^{-1}(B_n)) = \infty \cdot \epsilon = \infty,\] a contradiction.
Hence, the strategy must not be measurable. This suggests a Banach-Tarski-like solution.
--Christian