Seven Prisoners, Seven Rainbow Colours: Guarantee One Correct Guess
Seven prisoners are given a chance at freedom. Each will be given a hat in one of the seven colours of the rainbow (red, orange, yellow, green, blue, indigo, violet). The colours are chosen by the warden, who may use any assignment he likes: colours can repeat, and he will choose adversarially after learning the prisoners' strategy. Each prisoner can see the hats of the other six but not his own. There is no communication of any kind once the hats are on.
At a signal, every prisoner simultaneously writes down a guess for the colour of his own hat. If at least one prisoner guesses correctly, all seven are freed; otherwise none are. The prisoners may agree on a strategy beforehand.
(a) Is there a strategy that guarantees freedom no matter how the warden assigns the colours? If so, describe it and prove it works.
(b) Show that no strategy can guarantee two or more correct guesses.
Hints
- Number the colours $0, 1, \ldots, 6$ and number the prisoners $0, 1, \ldots, 6$. Think about the sum of all seven hat colours modulo $7$.
- The total $S = h_0 + h_1 + \cdots + h_6 \bmod 7$ is one of seven values. Let prisoner $i$ act as if $S \equiv i \pmod 7$.
- Prisoner $i$ sees all hats except his own, so he can compute the guess $g_i \equiv i - \sum_{j \ne i} h_j \pmod 7$. Exactly one prisoner (the one whose index equals the true $S$) is correct.
Worked Solution
How to Think About It: Against an adversary, no prisoner can improve his own odds above $1/7$: whatever he sees, his hat can be any colour. So the strategy must make the prisoners' errors perfectly anti-correlated, ensuring that in every possible assignment someone is right. The colour sum modulo $7$ partitions all assignments into $7$ classes, and there are exactly $7$ prisoners to cover them.
Approach: Assign each prisoner one residue class of the colour sum modulo $7$; a counting argument gives the upper bound.
Formal Solution:
Part (a): A winning strategy.
*Step 1 -- Encode.* Label the colours $0, 1, \ldots, 6$ and the prisoners $0, 1, \ldots, 6$. Let $h_j$ be the colour of prisoner $j$'s hat and let $S = \sum_{j=0}^{6} h_j \bmod 7$.
*Step 2 -- The rule.* Prisoner $i$ assumes that $S \equiv i \pmod 7$. He can see every hat but his own, so he computes the sum of the six visible hats and guesses $$g_i \equiv i - \sum_{j \ne i} h_j \pmod 7 .$$
*Step 3 -- Exactly one is correct.* The true total $S$ is some value $s \in \{0, \ldots, 6\}$. For prisoner $s$, $g_s \equiv s - \sum_{j \ne s} h_j \equiv S - \sum_{j \ne s} h_j = h_s \pmod 7$, so prisoner $s$ guesses correctly. For any other prisoner $i \ne s$, $g_i - h_i \equiv i - S \not\equiv 0 \pmod 7$, so prisoner $i$ is wrong. Thus in every one of the $7^7$ possible assignments exactly one prisoner is right, and the group is always freed. (A brute-force check over all $7^7 = 823{,}543$ assignments confirms exactly one correct guess in each.)
Part (b): No strategy guarantees two correct guesses.
*Step 4 -- Counting.* Fix any deterministic strategy: prisoner $i$'s guess is a function $g_i$ of the six hats he sees. For each prisoner $i$ and each fixed choice of the other six hats, exactly one of the $7$ possible values of $h_i$ makes $g_i$ correct. So prisoner $i$ is correct in exactly $7^6$ of the $7^7$ assignments, i.e. a fraction $1/7$. Summing over the seven prisoners, the total number of correct guesses across all assignments is $7 \times 7^6 = 7^7$: on average exactly one correct guess per assignment.
*Step 5 -- Conclusion.* If some strategy guaranteed at least $2$ correct guesses in every assignment, the total would be at least $2 \times 7^7$, contradicting Step 4. Hence the modular strategy, which achieves exactly one correct guess in every assignment, is the best possible. (Randomised strategies do no better in the worst case, since the warden chooses adversarially after learning the strategy.)
Answer: (a) Yes. Number colours and prisoners $0$ to $6$; prisoner $i$ guesses the colour that would make the sum of all seven hats congruent to $i$ modulo $7$, i.e. $g_i \equiv i - \sum_{j \ne i} h_j \pmod 7$. The true sum is congruent to exactly one index, so exactly one prisoner is always correct. (b) Any prisoner is correct in exactly $1/7$ of all assignments, so the average number of correct guesses is $1$ for every strategy; no strategy can guarantee two.
Intuition
Each prisoner individually has only a $1/7$ chance against an adversary, so the trick is to make the seven guesses cover the seven possible worlds without overlap: prisoner $i$ bets that the total colour sum is $i$ modulo $7$. Exactly one of those bets is true, so exactly one prisoner is right in every assignment. The second part follows from counting: for any strategy, each prisoner is right in exactly $1/7$ of all assignments, so the average number of correct guesses is $1$, and a strategy that always got two right would average at least $2$. Partitioning the hypothesis space so that guesses are jointly exhaustive and mutually exclusive is the general lesson.