Encoding Information With Parity in Hat Puzzles

A huge family of interview brainteasers — prisoners guessing hat colours, prisoners flipping coins on a table, groups signalling with a single visible action — are solved by the same trick: someone sacrifices their own certainty to broadcast the parity (odd or even count) of something everyone else can partly see. Once you recognize a puzzle as "one person needs to send exactly one bit, and everyone else needs to combine that bit with what they can already see," the solution almost writes itself.

Why parity specifically

A parity bit — is a count odd or even — is the cheapest possible summary of a large set of observations, because it doesn't require agreeing on which specific hats are black, only how many. This makes it robust: any single observer, seeing only part of the full set, can still combine "the parity of the whole" with "the parity of the part I can see" to recover the parity — and hence the exact value — of the one piece they're missing. That's the entire mechanism in nearly every hat puzzle: total parity, known parity, missing piece.

Working example: $n$ people in a circle, black/white hats

Everyone stands in a circle, sees every hat except their own, and must simultaneously write down a guess for their own hat colour on a piece of paper. There's no speaking order to exploit this time — everyone guesses at once. With no broadcast possible, can parity still help? Yes, if the group agrees on a convention rather than a live broadcast: each person assumes the total number of black hats in the room is even, and guesses their own colour accordingly — counting the black hats they can see, and guessing "black" for themselves if that count is odd (making the true total even) or "white" if it's already even.

If the true total number of black hats is even, exactly the people wearing white hats guess correctly (since they see the true, even count of black hats and correctly conclude "white" for themselves), while everyone wearing black sees one fewer black hat than the true count — an odd number — and guesses "black" for themselves, which is also correct! In fact, in this case, everyone guesses right. If the true total is odd, the logic flips and everyone guesses wrong. So this exact strategy is win-everything-or-lose-everything, useful when the puzzle rewards a guaranteed floor across many independent trials rather than a per-person guarantee — the parity convention turns an $n$-way independent guessing problem into a single global coin flip.

Contrast this with the sequential line version (see prisoners-in-a-line-hat-guessing): there, one person's spoken parity is literally heard by everyone after them, so it acts as a live broadcast and guarantees $n-1$ correct guesses deterministically. In the simultaneous circle version, there's no channel to broadcast on, so the best a pre-agreed parity convention can do is convert independent 50/50 guesses into one all-or-nothing collective coin flip.

What this means in practice

Recognizing "this is a parity-coding puzzle" is a pattern-matching skill interviewers specifically probe for, because the same move — compress a large state into a small, cheaply-verified summary — is exactly how checksums, hash-based reconciliation, and error-detection in trade and position data work in practice: you don't re-transmit the whole position blotter to check for a break, you compare a compact summary and only investigate further if it disagrees.