Variant of "prisoners and hats" puzzle with more than two colors 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?

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