The Chessboard Coin-Flip Prisoner Puzzle

A jailer places a coin heads-up or tails-up on each of the 64 squares of a chessboard, in a pattern of the jailer's choosing. The jailer then secretly picks one square and tells only the accomplice which one. The accomplice's job: flip the coin on exactly one square of their choosing (any square, not necessarily the secret one), and then leave. The prisoner enters, sees the entire board, and must name the secret square — with only the sight of the board, and knowing the accomplice flipped exactly one coin somewhere, to go on. No other communication is allowed. How can the accomplice guarantee the prisoner always identifies the correct square?

The core idea: 64 squares need exactly 6 bits, and one flip is exactly one bit

There are 64 possible secret squares, and $64 = 2^6$, so identifying one out of 64 needs exactly 6 bits of information. The accomplice can only perform one action — flipping one coin — which sounds like nowhere near enough. But a coin flip isn't "one unit of information" in a vacuum; it's a change to a specific bit of a pre-agreed 6-bit encoding scheme, chosen by the accomplice to correct whichever one of the six parity bits is currently wrong for the target square. One flip, aimed precisely, is exactly enough to fix exactly one bit of a 6-bit mismatch.

Working the scheme

Agree in advance: label the 64 squares $0$ through $63$ in binary, using 6 bits. Partition the squares into six overlapping groups, $G_1$ through $G_6$, where $G_i$ is the set of all squares whose binary label has a 1 in bit position $i$ (this is the same style of grouping used in the poisoned-wine binary-encoding puzzle). For any current arrangement of heads/tails on the board, define $p_i$ as the parity (even = 0, odd = 1) of the number of heads-up coins in group $G_i$. Read $(p_1, \dots, p_6)$ as a 6-bit number — call it the board's current "checksum."

If the checksum already equals the secret square's label, the accomplice flips any coin outside all the groups whose bit differs... but actually the accomplice's job is simpler: compare the current checksum to the target label bit by bit. They differ in exactly one bit position, or in several — but flipping a single coin in a well-chosen square changes the parity of every group that square belongs to simultaneously. Since each square's own binary label tells you exactly which groups it's a member of, the accomplice computes the bitwise difference between the current checksum and the target label (an XOR of the two 6-bit numbers), treats that difference itself as a square's binary address, and flips the coin on that square. Flipping it toggles the parity of precisely the groups corresponding to the 1-bits of the difference — which, by construction, changes the checksum from its old value to exactly the target value, since XOR-ing a number with the difference between two values recovers the other value.

The prisoner, on entering, recomputes the six group parities from the visible board, reads them off as a 6-bit number, and that number is exactly the secret square's label.

What this means in practice

This puzzle is a compact, hands-on demonstration of how error-correcting codes and single-bit-flip syndromes work — the same XOR-of-parity-groups trick underlies real checksum and parity-based data-integrity schemes used to detect and even correct single-bit corruption in transmitted data. For an interview, it also tests whether a candidate can generalize the parity-encoding idea from earlier hat and coin puzzles to a genuinely different setup (an action rather than a passive observation carrying the signal), which is the deeper transferable skill.