Harder hat problem

The Problem:

Setup: There are n prisoners standing in a circle so that everyone can see each other's hats but not their own. An executioner will use a fair coin toss to put a black or white hat on every prisoner. He will then proceed clockwise around the circle and ask each prisoner if they want to guess their hat color. Prisoners may guess or choose to pass, but at least one prisoner must guess. If ANY prisoner guesses their hat color wrong, everyone will be killed.

Question: What strategy can the prisoners use to maximize their chances of living?

The "Default" Solution

The default solution is to have everyone pass until the last prisoner who must guess. They have a 50% chance of being right. Not so hot.

Our First Attempt: 75% chance of getting saved

If the 1st prisoner says "pass", it means the 2nd prisoner's hat is black. They can guess correctly, and everyone else will pass.

Unfortunately, if the 2nd prisoner's hat is white, the 1st prisoner will have to guess his own hat color with 50% chance of success.

Therefore, there's a 75% chance overall that this strategy will be effective.

Our Final Solution

My wife came up with a solution that gives the prisoners a 1 - 1/2^n chance of being saved. Here it is:

Rule: If there are any black hats ahead of you in the questioning, pass. If there aren't, guess black.

This strategy will fail if everyone has a white hat. In that case, the first prisoner will incorrectly guess black and everyone dies. But it works for all the other possibilities. Here's why:

There's always going to be a "last" black hat in the questioning order (so long as there's a black hat at all). Using the strategy, everyone before this person will pass. Since this person is the last black hat, they can only see white hats ahead of them, so they will correctly guess "black".

With n people, there are 2^n possible assignments of hat color. Only one of these (all white hats) will fail with our strategy. Therefore, the chances of dying are 1/2^n. So the chances of living are 1 - 1/2^n.

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.