The One-Coin Chessboard Message, math that surprises you lesson

A coin lies on each of the 64 squares of a chessboard, heads or tails in any pattern. One partner learns a secret square and may flip exactly one coin, and then the other partner, who sees only the final board, must name the square. One flip looks far too small a change to pick out one of 64 squares, especially since nobody controls how the coins started. This page gives a method that always works, built from binary labels and XOR, and shows why it needs the number of squares to be a power of 2.

Key terms

Chessboard coin puzzle

Definition The chessboard coin puzzle, in the version on this page, has the following rules. There are two partners and a chessboard of 64 squares with one coin on each square. First the partners agree on a method, including a numbering of the squares that both will read the same way, for example by fixing which corner holds square 0 and how the numbers run. After that they cannot communicate. The coins are then set heads or tails in any arrangement, which the partners do not choose and which may even be picked by someone who knows their method. The first partner sees this board and is shown a target square, which can be any of the 64. The first partner must flip exactly one coin, any coin they like, and may change nothing else. The second partner then sees only the final board, not the starting board and not which coin was flipped, and must name the target. The puzzle asks for a method that names the target correctly for every starting board and every target. If the second partner could see the starting board, flipping the target’s own coin would be enough, so the whole difficulty lies in a start that is arbitrary and hidden. The resolution is to number the squares 0 to 63, write these numbers as six-digit binary labels, and let each board stand for the XOR of the labels of the squares that show heads, with a board of all tails standing for 0. Call this value $C$ for the starting board, and let $T$ be the label of the target. The first partner flips the coin on the square labeled $C \oplus T$ , the new board then stands for $T$ , and the second partner reads it off. The same method works on any board of $2^k$ squares with $k$ -digit labels. For any other number of squares no method of any kind works, as the third question below shows.

In plain words The second partner never tries to find the flipped coin. Every possible board stands for one square, and the first partner chooses the one flip that changes what the board stands for into the target.

Example Take a board of four squares numbered 0, 1, 2 and 3, with the two-digit labels 00, 01, 10 and 11. Suppose squares 1 and 2 show heads and squares 0 and 3 show tails. The board stands for $01 \oplus 10 = 11$ , which is square 3. If the target is square 2, with label 10, the first partner flips the coin on the square labeled $11 \oplus 10 = 01$ , which is square 1. That coin turns to tails, only square 2 still shows heads, and the board now stands for 10, square 2. If the target is square 3 instead, the board already stands for it, and the rule gives $11 \oplus 11 = 00$ , so the first partner flips the coin on square 0. Its label adds nothing to any XOR, so the board still stands for 11 whether that coin turns to heads or to tails, and the rule of exactly one flip is kept.

XOR

Definition XOR, short for exclusive or, is an operation on binary digits. The XOR of two digits $a$ and $b$ , written $a \oplus b$ , is 1 when exactly one of them is 1 and 0 otherwise,

\begin{gathered} 0 \oplus 0 = 0, \quad 0 \oplus 1 = 1, \\[0.4em] 1 \oplus 0 = 1, \quad 1 \oplus 1 = 0, \end{gathered}

so $a \oplus b$ is the parity of $a + b$ . Two binary labels of the same length are combined digit by digit, with no carrying between positions, and the XOR of two numbers means the XOR of their labels, read back as a number. XOR can be applied to the labels of a list in any order and with any grouping, and each digit of the result is 1 exactly when an odd number of the labels have a 1 in that position. For every label $x$ ,

\begin{gathered} x \oplus 0 = x, \\[0.4em] x \oplus x = 0, \end{gathered}

where $0$ stands for the label made of zeros only. Therefore $(x \oplus y) \oplus y = x$ for all labels $x$ and $y$ of the same length.

In plain words XOR is addition of digits in which 1 plus 1 gives 0 and nothing is carried. Each position keeps its own record of odd or even, and combining with the same label twice cancels it.

Example Line up the labels of 13 and 42 and combine each column.

Number	Six-digit label
$13$	001101
$42$	101010
$13 \oplus 42 = 39$	100111

Each column with exactly one 1 gives 1. The second column from the left has no 1s and the third has two, so both give 0. Combining the result with 13 again undoes the first step, since $39 \oplus 13 = 42$ .

Binary labels

Definition Binary labels with $k$ digits write the numbers $0, 1, \ldots, 2^k - 1$ in base 2, padded with zeros on the left to exactly $k$ digits. From left to right the positions are worth $2^{k-1}, \ldots, 4, 2, 1$ , and a label stands for the sum of the worths of the positions that hold a 1. There are $2^k$ strings of $k$ digits, and each is the label of exactly one of the numbers from $0$ to $2^k - 1$ . So when $2^k$ squares receive these labels, every $k$ -digit string, including any XOR of labels, names exactly one square. A chessboard has $64 = 2^6$ squares and needs six digits. Both partners must use the same labeling. For example, the square in row $r$ and column $c$ , each counted from 0 to 7 starting at an agreed corner, can get the number $8r + c$ , whose six-digit label is the three-digit label of $r$ followed by that of $c$ .

In plain words Every square gets a name made of six 0s and 1s, and every possible name belongs to exactly one square. Whatever six-digit string a calculation produces, there is a square with that label and a coin on it to flip.

Example Since $42 = 32 + 8 + 2$ , the label of 42 is 101010, and since $13 = 8 + 4 + 1$ , the label of 13 is 001101. In the row and column numbering, $42 = 8 \cdot 5 + 2$ is the square in row 5 and column 2, and its label splits as 101 for row 5 and 010 for column 2.

Parity check

Definition A parity check on a list of binary digits asks whether a chosen set of positions holds an even or an odd number of 1s, and records 0 for even and 1 for odd. In the chessboard method each digit of the value a board stands for is a parity check on the coins. Digit position $j$ of the XOR of the labels of the heads is 1 exactly when an odd number of heads lie on squares whose labels have a 1 in position $j$ . With six-digit labels there are six such checks, and each one watches the 32 squares whose labels have a 1 in its position. Flipping one coin changes the number of heads on its square by one, from 0 to 1 or from 1 to 0, so it switches exactly the checks that watch that square, which are the positions where its label has a 1, and leaves the other checks alone. Hence flipping the coin on square $g$ changes the value of the board from $C$ to $C \oplus g$ , whether that coin showed heads or tails before. Every choice of positions to switch is the set of 1s of exactly one label, and the flip on square $C \oplus T$ switches exactly the positions where $C$ and $T$ differ, so the new value is

C \oplus (C \oplus T) = T.

In plain words Each of the six digits of the board’s value watches its own half of the board and reports odd or even. One flip can change any chosen selection of those six reports, and the label of the flipped square says which selection.

Example Suppose the only heads are on squares 3, 10 and 36. Write their labels in rows under the worths of the positions.

Square	32	8	4	2	1
3	0	0	0	1	1
10	0	1	0	1	0
36	1	0	1	0	0
Parity of the column	1	1	1	0	1

The board stands for 101101, which is $32 + 8 + 4 + 1 = 45$ . To send the target 13, with label 001101, the first partner compares 101101 with 001101. They differ only in the leftmost position, so exactly that check must switch, and the one square watched by that check alone is 100000, square 32. Its coin shows tails, so the flip adds a fourth head, and the board then stands for $45 \oplus 32 = 13$ , as required.

Check yourself

On the four-square board, squares 0, 1 and 3 show heads and square 2 shows tails. The target is square 1. Which coin does the first partner flip, and what does the second partner read?

Show the answer

The board stands for

00 \oplus 01 \oplus 11 = 10,

which is square 2. The first partner flips the coin on the square labeled $10 \oplus 01 = 11$ , square 3. Its coin turns from heads to tails, so heads remain on squares 0 and 1, and the second partner computes $00 \oplus 01 = 01$ , square 1. The head on square 0 never matters, because the label 00 changes no XOR.

On the full chessboard the heads currently stand for 50, and the target is square 7. Which coin should be flipped? A partner suggests simply flipping the coin on square 7. What would that do?

Show the answer

The labels are 110010 for 50 and 000111 for 7, and their XOR, column by column, is

\begin{array}{r} 110010 \\ \oplus \ 000111 \\ \hline 110101 \end{array}

which is $32 + 16 + 4 + 1 = 53$ . So the coin on square 53 is the one to flip. After the flip the board stands for $50 \oplus 53 = 7$ , the target. Flipping the coin on square 7 instead would change the value to $50 \oplus 7 = 53$ , so the second partner would name square 53. Flipping the target’s own coin works only when the board starts out standing for 0, and the partners cannot count on that.

Change the number of squares. Show that on a board of three squares no method can always work, whatever rule the second partner uses to read a board.

Show the answer

Suppose some method works. Its second partner reads each of the $2^3 = 8$ boards as one of the squares 0, 1 and 2. From any starting board the first partner can reach exactly three boards, one for each coin, and since each of the three squares can be the target, those three boards must be read as three different squares. So every board is one flip away from exactly one board that is read as square 0.

Now count the pairs made of a board and a board one flip away from it that is read as square 0. Each of the 8 boards starts exactly one such pair, so there are 8 pairs. Counted from the other end, each board read as square 0 is one flip away from exactly 3 boards, so the number of pairs is 3 times the number of boards read as square 0. But 8 is not a multiple of 3, so no such method exists.

The same count on a board of $n$ squares shows that $n$ times the number of boards read as square 0 equals $2^n$ , so $n$ must divide $2^n$ . The only numbers that divide a power of 2 are powers of 2. So the puzzle can be solved exactly when the number of squares is a power of 2, and the XOR method solves every such case. A board of $64 = 2^6$ squares works, while boards of 3, 5, 6 or 100 squares do not.