Yesterday my game theory professor gave us a new story. If you have read my previous post on guessing hats, you will find this similar but in a sequential setting. The story goes like this:

There are n criminals in the prison. One night, the inspector comes into the prison and offers them a chance to save themselves on the next day. The inspector says:”Tomorrow I will make you guys stand in a line. I will put a hat, either black or white, on each of you. You can make a guess of the color of your hat. If your guess is correct, congratulations! You are saved. If your guess is wrong, however, you will be executed. Note that there is at least one white hat.” The prisoners gather together and cook up a scheme where the most of them will be saved on the next day. What is this scheme? How many people will be saved?

I discussed with my classmate Eric Wang in the canteen today and we found it great fun. Here is our thinking:

First of all, we number the n prisoners from 1 to n, with 1 being the last one in the queue (i.e. the first one to guess the color of the hat) and n being the prisoner at the very front. Prisoner 1 observes the hat color of everyone ahead of him, and he is the first one to guess. So his reaction will provide important information for the rest of the prisoners.

It’s obvious that the only case in which prisoner 1 can be saved is when he is the only one wearing a white hat. If this is the case, he will observe everyone ahead of him wearing a black hat and guess himself to be wearing white since there’s at least one white hat. Prisoner 2 sees everyone ahead of him wearing black hats and he knows that at least one person between himself and prisoner 1 must be wearing a white hat. Having heard prisoner 1’s guess, he knows that he must be wearing black hat. For prisoner 3, having heard prisoner 2 guessing black means the prisoner with the white hat (prisoner 1 in this case) has already showed up and it’s safe for him to guess black. By the same logic, prisoners from 4 to n also guess black. All the prisoners are saved.

A more realistic case would be (supposing the inspector don’t want all the prisoners to be released) that prisoner 1 observes prisoner k (k>1) ahead of him is wearing a white hat ( for simplicity assume this is the only white hat he can see), he cannot deduce the color of his hat. Because a wrong guess leads to execution, he will keep silent. By the same logic, prisoners 2 to (k-1) will also remain silent because they all can see prisoner k wearing a white hat. When it comes to prisoner k, he sees all black hats in front of him, and he also hears prisoner (k-1) saying “I don’t wanna guess” which suggests prisoner (k-1) sees at least one white hat in front of him. Prisoner k can therefore conclude that he must be the one wearing the white hat and he is saved. Prisoners (k+1) to n are all saved because the prisoner k’s guessing white assures them that they are all wearing black hats.

If prisoner 1 observes more than one white hat in front of him, he will give up the chance of saving himself for the same reason stated above. For each of the following prisoner, a guess will not be made as long as the prisoner sees at least one white hat in front of him. Suppose the last person with a white hat is prisoner m. Prisoner m will guess his hat to be white because he heard prisoner (m-1) saying “I don’t know” and he sees all the people ahead of him wearing black hat. Everyone thereafter is saved.

In conclusion, the number of prisoners saved is (n-m), where m is the last person who is wearing a white hat.

Update: the professor said “That was a good try, but not what I was looking for.” He further pointed out two of my assumptions are wrong –prisoners cannot remain silent and there’s no information on the number of hats of each type. The professor revealed the answer in class today.

Every prisoner should guess “white” if he sees an odd number of white hats in front of him, and “black” otherwise. Prisoner 1 has 50% chance of survival while the others will all be saved. It’s easy to check. In the absence of information about hat colors, they have to rely on the fundamental properties of numbers to send messages to each other.