Hat Puzzle

Sequential: n - 1 guaranteed. Simultaneous (Hamming): n/(n+1).

The idea

In the hat puzzle, prisoners standing in a line must each guess the color of their own hat while seeing only the hats in front of them, and one well-chosen announcement lets every prisoner but one guess correctly.

The tool is parity. The parity of a group of bits is their XOR: $1$ when an odd number of them are $1$, and $0$ otherwise. Announcing the parity of a group constrains the whole group at once. A listener who hears that parity and can see every bit of the group except their own recovers their own immediately: XOR the announced parity with everything they can see, and what remains is the bit they cannot see. This works because XOR is its own inverse, so any value that enters the calculation twice cancels.

The mechanism composes. If the listeners speak in turn and each announcement is itself correct, then a later listener knows the original parity and everything the earlier speakers deduced. The set of bits they can neither see nor infer shrinks by one at every turn, so a single broadcast serves the whole line.

The announcer sacrifices their own guess. Their announcement is a statement about other people's bits, so it carries no information about their own: nothing they can see determines it, and an adversary choosing the hats can always make it wrong.

Ways to work on it

• Walkthrough. n in a line. Back person broadcasts parity; everyone else deduces their hat.
• Practice. Three in a circle guess simultaneously — find how often the clever strategy wins.
• Hardest. A single culminating question on a random hat-puzzle setup — the line or the circle.

Not sure where to start? Take the ten-question placement test.