A Binary Parity Puzzle in Information Theory
You and your friend are prisoners. The jailer offers you freedom through this challenge:
Your task: Click the square your friend should guess after seeing the board state.
Explore how the puzzle works. Click the left board to select the magic square, then see which coin you need to flip to encode this information.
Board Parity: For each of the 6 bit positions (2⁰ through 2⁵), count the number of heads in squares where that bit is set. If odd, that bit is 1; if even, it's 0.
XOR Operation: To change the board parity to match the target square, flip the coin at the position given by: Target XOR Parity
This works because XOR identifies which bits need to flip. Each square changes specific parity bits when flipped.
The chessboard has 64 squares, which requires exactly 6 bits to encode (2⁶ = 64). Each square can be uniquely identified by a 6-bit binary number from 000000 (square 0) to 111111 (square 63).
We divide the board into 6 different overlapping patterns based on each bit position:
Alternating columns
2-column pattern
4-column pattern
Alternating rows
2-row pattern
4-row pattern
For each bit pattern, count the number of heads in the highlighted squares:
10This gives us a 6-bit number that describes the board's "parity state".
To encode the magic square:
flip_square = magic_square XOR board_parityflip_squareWhy this works: When you flip a coin at position N, you toggle the parity of all bit patterns that include position N. The XOR operation tells you exactly which square will transform the current parity into the target parity.
Use the Interactive Demo mode to see this in action!
This puzzle demonstrates fundamental concepts in information theory and error correction that underpin modern digital communications:
The puzzle uses the concept that any two board configurations differ by at least one coin flip. This relates to Hamming distance in coding theory - the minimum number of bit changes needed to transform one codeword to another.
The solution is essentially a (64,6) error-correcting code. We're encoding 6 bits of information (the magic square) into a 64-bit string (the coin configuration) such that any single bit flip can be detected and interpreted.
Each of our 6 bit patterns acts as a parity bit for a subset of the board. This is the same principle used in RAID storage systems, where XOR-based parity enables data recovery from disk failures.
The XOR operation is self-inverse: (A ⊕ B) ⊕ B = A. This property makes it perfect for encoding/decoding and is used extensively in cryptography and data transmission.
Claude Shannon's channel capacity theorem tells us the maximum rate of reliable communication. This puzzle achieves log₂(64) = 6 bits of information transmitted with a single bit change - optimal for this constraint.
The board parity acts as a "syndrome" in coding theory. Your friend decodes by computing the syndrome of the received configuration, which directly reveals the encoded message.
Water Resources Engineering: Similar parity-based encoding is used in telemetry systems for remote monitoring of reservoir levels, flow rates, and sensor networks where data reliability is critical.
SCADA Systems: Industrial control systems use error detection codes to ensure reliable transmission of control signals across noisy channels.
Satellite Communications: Reed-Solomon codes (a generalization of these principles) enable reliable data transmission from spacecraft despite cosmic ray interference.
Computer Memory: ECC (Error-Correcting Code) memory uses these principles to detect and correct bit flips caused by radiation or electrical interference.
The puzzle leverages vector spaces over GF(2) (the Galois field with 2 elements). Each board configuration is a 64-dimensional vector, and parity checking is a linear transformation that projects this onto a 6-dimensional subspace.
The coin flip operation spans the entire space efficiently because the bit patterns form a basis. This ensures that from any starting configuration, we can reach any target parity state with exactly one flip.