$20$ hats problem

Question

I've seen this tricky problem, where $20$ prisoners are told that the next day they will be lined up, and a red or black hat will be place on each persons head. The prisoners will have to guess the hat color they are wearing, if they get it right the go free. The person in the back can see every hat in front of him, and guesses first, followed by the person in front of him, etc. etc. The prisoners have the night to think of the optimal method for escape.

This method ends up allowing $19$ prisoners to always escape. The person in the back counts the number of red hats, and if its even, says red, if its odd, says black. This allows the people in front to notice if its changed, and can determine their hat color, allowing the person in front to keep track as well.

What I'm wondering is what is the equivalent solution for $3$ or more people, and how many people will go free. If possible, a general solution would be nice.

Answer 1

Suppose there are $n$ prisoners, with hats of $m$ different colors. Assign to each color a number from $0$ to $m-1$, agreed upon beforehand by all prisoners. Working mod $m$, each prisoner adds up the value of all the colors he sees when standing in line. Let $a_i$ be the value calculated by the $i$th prisoner.

Begin by having the first prisoner say the color associated to $a_1$. Now, for $i\ge 2$, having heard the first $i-1$ colors, prisoner $i$ can correctly guess the color of his hat to be the color associated to the residue of $a_1-a_2-\ldots-a_i$ modulo $m$. Why will this be a correct guess?

Answer 2

To solve the problem with $n$ prisoners and $k$ colours, do as follows: Wlog. the colors are the elements of $\mathbb Z/k\mathbb Z$.

If $c_i$ is the colour of th ehat of the $i$th prisoner, then the $i$th prisoner can easiliy compute $s_i:=\sum_{j<i}c_j$. Let the $n$th prisoner announce $s_n$. Then the $(n-1)$st prisoner can compute $c_{n-1}=s_n-s_{n-1}$ and correctly announce it. All subsequent prisoners $n-2, \ldots , 1$ can do the bookkeeping and announce their own colur accordingly.