There are $n$ prisoners and $n$ hats. Each hat is colored with one of $k$ given colors. Each prisoner is assigned a random hat, but the number of each color hat is not known to the prisoners. The prisoners will be lined up single file where each can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be one of the $k$ given colors. If the word matches their hat color they are released, if not, they are killed on the spot. They can set up a strategy before the test, so they choose a strategy that maximizes the number of definitely released prisoners (that number is called the number of the strategy. What is that number?
[Math] Variant of “prisoners and hats” puzzle with more than two colors
puzzlerecreational-mathematics
Related Solutions
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."
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
Label the colors $\{1,2,3\dots k\}$. The first one says the sum of the hats in front of him $\bmod k$ (the last $n-1$ persons). After this the second one can deduce which number corresponds to the color of his hat (by subtracting the sum that he can see minus the sum previously said).
The third person, having heard all of this, can now deduce the sum of the last $n-2$ people, and by substracting this from the sum of the hats he sees (last $n-3$) he can deduce which hat he has.
This process continues on to the last person. All of them are saved except for the first one, which survives with probability $\frac{1}{k}$. It is clear that no matter which strategy we follow, the probability the first person survives is $\frac{1}{k}$. So this strategy is optimal.
The maximum strategy number is hence $n-1$.