7
$\begingroup$

We have an infinite number of prisoners enumerated $\{1, 2, \dots\}$, and on each prisoner there is a hat of either blue or red color. The $n$th prisoner sees the hats of prisoners $\{n+1, n+2, \dots\}$. A warden asks each prisoner in succession, starting with prisoner $n=1$, "What is the color of your hat?" If any prisoner fails, then the warden executes that prisoner. Prisoners can not communicate. What strategy should the prisoners use (they discussed it before the moment that hats are put on them) to end up with a finite number of executions?

$\endgroup$
  • $\begingroup$ To execute a finite number of prisoners, a strategy must be construed in such a way that after the execution of prisoner $m$, all successive prisoners guess the color of their hats correctly. $\endgroup$ – wjm Nov 21 '14 at 20:56
  • $\begingroup$ @JosuéMolina: But notice that $m$ may depend on the distribution of hats. $\endgroup$ – Henning Makholm Nov 21 '14 at 20:57
  • $\begingroup$ Hm, this begins to smell of set theory anyways. I'll add (elementary-set-theory) back in. $\endgroup$ – Henning Makholm Nov 21 '14 at 21:01
  • $\begingroup$ This seems impossible. How can random distribution of infinitely number of hats contain within a finite information? $\endgroup$ – Alistair Nov 21 '14 at 21:02
  • $\begingroup$ Do the prisoners know whether the earlier prisoners were executed or not? $\endgroup$ – mjqxxxx Nov 21 '14 at 21:09
5
$\begingroup$

This is a classic riddle, whose solution surprisingly requires the axiom of choice as discussed here.

The solution, however, is short and clever. Encode the colors into $0$ and $1$, and define the equivalence relation on $2^\Bbb N$, $\langle x_i\rangle\sim\langle y_i\rangle$ if and only if there is some $k$ such that for all $n\geq k$, $x_n=y_n$. Using the axiom of choice the prisoners pick a representative from each equivalence class.

In his turn, then $n$-th prisoner looks for the representative class fitting the string of hats he sees ahead, assuming that all hats up to him are blue. Since all the prisoners follow the same representative to guess their own color, it is guaranteed that after finitely many deaths, the representative and the fashionable selection of hats by the warden will agree, and everyone else will survive.

-- "The needs of the many, outweigh the needs of the few."

$\endgroup$
  • 4
    $\begingroup$ Nice -- this even works if the prisoners cannot hear earlier answers. (If they can, the standard parity trick from the finite case, relative to the representative hat distribution, will save everyone except perhaps prisoner 1). $\endgroup$ – Henning Makholm Nov 21 '14 at 21:15
  • $\begingroup$ What's the point of the "assuming that all hats up to him are blue"? Doesn't it work without that? In fact, doesn't the assumption that all hats behind him are blue ruin the strategy, in the case that the unique representative that matches what he sees does not color all the hats behind him blue? $\endgroup$ – Don Hatch May 30 at 11:19
2
$\begingroup$

We can save all but one prisoner. The answer is slightly less elegant than Asaf's, but I value human life over mathematical elegance.

In particular, define the symmetric sum operation $$A\oplus B=(A\cup B)-(A\cap B)$$ which essentially says $x\in (A\oplus B)$ if it is in exactly one of $A$ or $B$. Under this, the powerset of $\mathbb{N}$ is a vector space over $\mathbb{F}_2$ of infinite dimension. Since the set of singletons $S=\{\{n\}:n\in \mathbb{N}\}$ is linearly independent, there must be some basis $\mathscr B$ containing $S$ (Oh, hello axiom of choice). Thus, we can choose some linear function $f:\mathscr P(\mathbb N)\rightarrow \mathbb{F}_2$ where $f(s)=1$ for any $s\in S$. Then the first prisoner says $f(R)$ where $R$ is the subset of the prisoners in front of him wearing red hats (numbered $1$ to infinity - he doesn't count himself, because he can't be saved anyways). The next person has two hypothesis - either he is wearing a red hat or not. If he is wearing a red hat, then define $R_2$ as the set of prisoners he can see with red hats, excluding himself, and $R_2'$ as the same set including himself. Since $R_2 \oplus \{2\} = R_2'$, clearly $f(R_2)\neq f(R_2')$. Therefore, the second prisoner figures out his own hat color as whichever of $f(R_2)$ or $f(R_2')$ matches the first prisoner's computation of $f(R)$. Each prisoner beyond that knows the hat color of every other prisoner expect himself and can proceed accordingly. This works for any (not necessarily finite) number of hat colors.

This is the same as the solution when there are only finitely many prisoners, but the axiom of choice would not be needed since, under the same sum, $P(\{1,\ldots,n\})$ has $\{\{1\},\{2\},\ldots,\{n\}\}$ as a basis, and hence there is a unique linear function taking each of those elements to $1$ (which happens to be computing the parity).

Of course if even one prisoner screws up their calculation...

$\endgroup$
  • 3
    $\begingroup$ "Prisoners can not communicate", sorta puts a damp on the strategy. And it's not that I don't value human life, I just prefer to think about it as finite. And finite things are negligible! :-) $\endgroup$ – Asaf Karagila Nov 21 '14 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.