xv. Prisoners and Hats

Problem. $n$ prisoners stand in a line, each wearing a hat of one of $k$ colours. Each sees all hats in front of them (not their own, not those behind). Starting from the back, each says one colour aloud, heard by everyone. How many can be guaranteed to guess their own colour?

Answer: $n-1$. The last person (who sees everyone else) announces the sum of all visible hats modulo $k$; everyone else subtracts what they see and what they heard to get their own colour.

vector<int> hatGuesses(const vector<int>& hats, int k) {   // person i sees hats[i+1..]; hear earlier guesses; colours 0..k-1
    int n = sz(hats); vector<int> g(n);
    int seen = 0; for (int j = 1; j < n; j++) seen = (seen + hats[j]) % k;
    g[0] = seen;                                    // announce the sum of all visible hats mod k
    int known = 0;                                  // sum of hats determined so far (persons 1..i-1)
    for (int i = 1; i < n; i++) {
        int s = 0; for (int j = i + 1; j < n; j++) s = (s + hats[j]) % k;
        g[i] = ((g[0] - s - known) % k + 2 * k) % k;
        known = (known + g[i]) % k;
    }
    return g;
}

Proof: n − 1 is optimal

Strategy works. Let $S={\sum }_{j\ge 1}{h}_j\mathrm{mod}k$, announced by person $0$. When person $i$ speaks, they know $S$, the hats $h_{i+1},\dots$ they see, and the hats $h_1,\dots ,h_{i-1}$ already guessed correctly (by induction), so $h_i=S-{\sum }_{j<i}{h}_j-{\sum }_{j>i}{h}_j(\mathrm{mod}k)$. Optimal. Person $0$ sees nothing about their own hat and has heard nothing, so for any strategy, an adversary can choose $h_0$ different from their guess. Tested on random lines with up to 10 people and up to 6 colours.

Variant	Result
simultaneous guessing, each sees all others, maximize the chance that everyone is right	$1/k$ (all assume the total sum is $0$)
simultaneous, maximize guaranteed correct guesses (two colours)	$\lfloor n/2\rfloor$ by pairing opposite strategies
countably many prisoners	all but finitely many (axiom of choice); outside CP
hat colours as numbers $\mathrm{0..}k-1$, see all others, at least one correct	person $i$ assumes the total is $\equiv i(\mathrm{mod}k)$ ($n=k$)