Prisoners with k-colors of hat

The Problem:

Setup: This is exactly the same setup as the prisoners-with-hats problem, only now there are more than 2 possible hat colors.

Here (again) is the setup: There are n prisoners standing in a line, facing front. The executioner starts at the back of the line and randomly gives each prisoner one of k colors of hat to put on. No one can see their own hat color or the hat colors of anyone behind them, but they can see all the hats of the people in front of them. The executioner will walk down the line starting from the back and ask each prisoner to guess their own hat color. Each prisoner can only say one of the possible hat colors. If they guess right, they will be set free at the end. If they guess wrong, they will be killed at the end. The prisoners realize that they can try to use their guesses to communicate information to the prisoners in front of them that might help the others guess their own hat colors right.

Question: What strategy can the prisoners use to save as many of themselves as possible? How many can we expect to save?

Solution

Surprisingly, it doesn't matter how many colors of hat there are. It's still possible to guarantee that all the prisoners but the first get saved. The solution is a clean (though maybe not obvious) generalization of the solution to the 2-color hat problem.

First, number your colors 0 to (k-1).

The 1st prisoner will figure out what (p2 + p3 + ... + pn) mod k is. Since it's guaranteed to be a number between 0 and k-1, he can use his guess to communicate this number to the other prisoners.

Now prisoner 2 can figure out his own hat color as follows. He can calculate (p3 + p4 + ... + pn) mod k from what he sees. The difference between this number and what prisoner 1 told him must be the value of his own hat color, allowing him to guess correctly.

Prisoner 3 can assume prisoner 2 was correct in his guess, and can apply similar reasoning.