6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Well, the description of the strategy for $20$ people readily generalizes to $n$ people and allows $n-1$ to survive. Just replace $20$ and $19$ in your text with $n$ and $n-1$, respectively. $\endgroup$ Jul 16, 2013 at 21:02
  • 1
    $\begingroup$ I think he meant 3 different color hats. But in that case, the answer is the same... you can always ensure that $n-1$ people escape. In fact, you can do that for any number of different colored hats, so long as the number of different colored hats is finite. $\endgroup$ Jul 16, 2013 at 21:08

2 Answers 2

4
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I am curious: how can the last prisoner, the one who sees no one, guess his color? $\endgroup$
    – wjmolina
    Jul 16, 2013 at 21:50
  • $\begingroup$ For the two color scenario, the first prisoner to go tells every other prisoner the parity of the red hats. Then, the prisoner at the front of the line can listen as every other prisoner states the color of the hat they are wearing. For example, if the first to go says "red" then there are an even number of red hats before him. Then if by the time the last prisoner goes an odd number of red hats have been called then they know theirs must be red, and likewise it is black if an even number have been called out. $\endgroup$
    – Patrick
    Jul 17, 2013 at 1:52

Not the answer you're looking for? Browse other questions tagged .