Rainbow Hats

Seven prisoners will be hatted tomorrow. The executioner puts a hat on each, every hat one of the seven rainbow colours, chosen however he likes. Each prisoner sees the other six hats but never his own, and no one may communicate. Each writes a single guess of his own colour. If at least one guess is right the whole room goes free, otherwise all are executed. They have tonight to agree on a plan.

Can they guarantee freedom?

Reveal solutionHide solution

#The shared invariant

Yes. Number the prisoners $0$ through $6$ , code the colours $0$ through $6$ , and let $x_i$ be prisoner $i$ 's colour. No two prisoners see the same thing, but they can all reason about one global quantity, the total

S = \sum_{j=0}^{6} x_j \pmod 7. \tag{1}

No one knows $S$ , since each prisoner is missing his own term. The plan covers every possible value of $S$ at once. Prisoner $i$ bets that the total is $i$ .

#The guess

Prisoner $i$ sums the six hats he sees and names the colour that would make the total equal to his own index,

g_i = \Bigl(i - \sum_{j \neq i} x_j\Bigr) \bmod 7. \tag{2}

This uses only the six hats he can see, so it is a legal move.

#Why one guess always lands

Prisoner $i$ is right exactly when $g_i = x_i$ , which rearranges to

i - \sum_{j \neq i} x_j \equiv x_i \pmod 7, \qquad\text{that is}\qquad i \equiv \sum_{j=0}^{6} x_j \equiv S \pmod 7. \tag{3}

The total $S$ is one definite value in $\{0, \dots, 6\}$ , so exactly one index matches it. Whatever the executioner chooses, prisoner $S$ names his own colour and the room goes free. The seven bets tile the seven residues with no overlap and no gap, so the number of correct guesses is always exactly one.

#Checking every assignment

Seven colours on seven heads is only $7^7$ cases, small enough to settle by exhaustion.

from itertools import product

N = 7

def guesses_right(hats: tuple[int, ...], i: int) -> bool:
    others = sum(h for j, h in enumerate(hats) if j != i) % N
    return (i - others) % N == hats[i]

def correct_count(hats: tuple[int, ...]) -> int:
    return sum(guesses_right(hats, i) for i in range(N))

print({correct_count(h) for h in product(range(N), repeat=N)})  # -> {1}

Every one of the $823{,}543$ assignments yields exactly one correct guess, never zero.

#Wider view

Nothing here is special to seven. With $n$ prisoners and $n$ colours the same sum modulo $n$ gives exactly one correct guess on every assignment, and that is the most they can force. Across all $n^n$ assignments the correct guesses total $n \cdot n^{n-1} = n^n$ , an average of one per assignment, and this strategy meets that average on the nose every time.