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?
Elementary Set Theory – Solving the Prisoners Problem Puzzle
elementary-set-theorypuzzlerecreational-mathematics
Related Solutions
After writing up this answer I found this paper that comes to the same conclusions and also generalizes the problem to $q$ hat colours. I'm posting the answer anyway to have it here on math.SE in self-contained form.
As described in the Wikipedia article Gerry linked to and this book it references, an optimal strategy concentrates the wrong guesses onto as few configurations as possible. Each individual player guesses incorrectly exactly half the time if she doesn't pass, and ideally these incorrect guesses should all be concentrated on configurations where everyone guesses incorrectly whereas the correct guesses should ideally be spread out one per configuration.
Let's denote the set $\def\red{\text{red}}\def\blue{\text{blue}}\def\pass{\text{pass}}\{\red,\blue\}$ of hat colours by $H$ and the set $\{\red,\blue,\pass\}$ of guesses by $G$. Then a strategy for $n$ prisoners is a function $H^n\to G^n$ such that the $k$-th entry of the value doesn't depend on the $k$-th entry of the argument.
Given a strategy, we're interested in the proportion of vectors of $H^n$ for which the strategy prescribes a value which is not the constant $\pass$ vector and in which all non-pass entries match the corresponding entries in the argument. Let's call such vectors good and the others bad.
Adjacent to every good vector $g\in H^n$ is at least one bad vector $b\in H^n$ that differs from $g$ only in the hat colour of one of the prisoners who guess correctly for $g$ (of which there is at least one). Conversely, given a subset $S\subseteq H^n$ of bad vectors such that every vector is adjacent to at least one bad vector in this sense, we can make all other vectors good by assigning an adjacent bad vector to each of them (arbitrarily if there's more than one) and letting only the prisoner in whose entry the two vectors differ guess.
Thus, an optimal strategy is defined by a minimal subset $S\subseteq H^n$ such that all vectors in $H^n$ are adjacent to at least one element of $S$. Such a minimal subset is called a binary optimal covering code of length $n$ and radius $1$, and the number of vectors in such a minimal subset is denoted by $K(n,1)$. This table (linked to from this page) gives the known bounds on $K(n,1)$ up to $n=33$.
For $n=2^k-1$ the Hamming codes described in the article and the book are optimal binary covering codes with $2^{n-k}$ vectors, with winning probability $1-2^{n-k}/2^n=1-2^{-k}=n/(n+1)$. For other values of $n$, the values of $K(n,1)$ are only known up to $n=9$, and for $n$ a power of $2$; the lower bound for $K(27,1)$ was improved only recently.
After working out a little bit of math, I suddenly remembered that this was asked, in some variation, on MathOverflow. Thankfully, Nate Eldredge posted an answer to this question which had just the right reference.
Hardin, Christopher S.; Taylor, Alan D. An introduction to infinite hat problems. Math. Intelligencer 30 (2008), no. 4, 20–25. MR2501394.
In this paper the authors show that it is consistent with $\sf ZF+DC+BP$ (where $\sf BP$ is the axiom stating that every set of reals has the Baire property) that there is no winning strategy. Of course this theory is equiconsistent with $\sf ZFC$ (as shown by Shelah), and follows from $\sf AD$ as well it holds in Solovay's model.
Additional information can surely be found in their book (mentioned in the comments of Nate's answer by Francois Dorais), whose subtitle is "A study of generalized hat problems"
Christopher S. Hardin and Alan D. Taylor, The mathematics of coordinated inference, ISBN: 978-3-319-01332-9; 978-3-319-01333-6.
This might also seem interesting,
Hardin, Christopher S.; Taylor, Alan D. Minimal predictors in hat problems. Fund. Math. 208 (2010), no. 3, 273–285. MR2650985.
Best Answer
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."