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?

Since, I don't have the permission to comment yet, so I am adding here... we should label the k colours with number from 0 to k-1 : {0,1,2,3,....k-1} and then use the concept of modular arithmetic.
