Prisoners Problem

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?

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."

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...