# Prisoners in a line wear red or blue hats; each must identify his color to live. What strategy maximizes the number of survivors?

I found an interesting word problem:

A7: a) Ten prisoners are in a bad situation. Tomorrow, the prison warden will randomly arrange them in a line, facing towards one end of the line, and put a red or blue hat on each. Each will see the hats of those in front, but not of those behind or on his own head. One by one, starting at the back of the line and moving forward, the warden will ask each the color of his own hat. Each prisoner must answer, and if he will live if and only if he answers correctly.

Tomorrow the prisoners may not talk to each other, though they will hear the answers to the warden’s questions. But tonight they can discuss and devise a strategy to maximize the number of people who will live tomorrow. What is the best strategy and how many will it save?

b) Now suppose there are N colors for the hats and answer the same question.

I have been working on it and have reached the following conclusion: Say the color of the person who is in front of you. Say the color of the person in front of you. Whether your wrong or right, at least the person in front of you will know what color his is. Then he can say what his color is although it may not be the same as the one in front. Therefore, $5$ are sure to be saved. The other $5$ have a $50$% chance of being saved. How does this answer sound?

• This is a classic. With $N$ prisoners, there is a strategy that will guarantee the survival of at least $N-1$ of them. In fact, the same is true even when hats of any number of colors are allowed. – Jared Apr 24 '13 at 4:56
• Really? So your saying in this case, I can always save 9? – Richard Carpenter Apr 24 '13 at 5:10
• Check out this link... Sorry but no. Please make your question self-contained. – Did Apr 24 '13 at 15:40
• Question is now self-contained, over 5 years later =D – MBorg Sep 12 '18 at 10:24

The first task is easy. The first prisoner says "Blue" if he sees odd number of blue hats and "Red" otherwise. He survives with probability of $\frac 1 2$. Next prisoner does already know his hat color, because he sees also all another prisoners and heard, how many blue hats MOD $2$ should there be. He says his olor correctly. Then next prisoner know his color etc. $N-1$ of them survive, one survives with the probability of $\frac 1 2$.
The problem becomes not harder if there are $N$ colors. This is just a common case. Let the colors be $\{0,~1,~...,~N-1\}$. The first man says then the sum of colors he sees MOD $N$. As previously, he survives with probability of $\frac 1 N$, and the next prisoner knows already his hat color. Again: $N-1$ of them survive, one survives with the probability of $\frac 1 N$.
• Quick question. For the case of $N$ colors, what does the first man say? Suppose their are $4$ colors. – Richard Carpenter Apr 24 '13 at 5:46