64 Coins - Futility Closet

A puzzle from the site Riddle of the Day:

A warden offers a challenge to two prisoners. The first prisoner will enter a room that contains a chessboard. On each of the board’s 64 squares is a coin that’s either heads up or tails up. The guard will identify one square as the “target.”

The first prisoner must turn over exactly one coin and then leave the room. The second prisoner must then enter and, solely by viewing the board, determine which square is the target.

If they succeed, both prisoners will go free. They can confer beforehand on a strategy, but they may not communicate after that. Can they establish a plan that will always work?

	Select Click for Answer
Surprisingly, the answer is yes. Number the squares 0 to 63 and express these numbers in 6-bit binary (000000 to 111111). List the numbers of the squares that bear coins that are heads-up. Below each column in that list, write a 1 if the column contains an odd number of 1s or a 0 if it contains an even number of 1s. For example, suppose that the only heads-up coins are on squares 17, 21, 38, 44, and 55. Listing these in binary and condensing the list as described, we’d get: 010001 010101 100110 101100 110111 ------ 111001 111001 is 57 in decimal. Call that the encoded square; the second prisoner, on just viewing the board, could conduct the same calculations and identify this square independently. Now how can we communicate the identity of the target square? It turns out that, by flipping a single coin, we can move the encoded square to any square we choose. Suppose the target square is square 11. List this below the number of the encoded square, both in binary: 111001 001011 Below each column, write a 0 if the two numbers match and a 1 if they don’t (this is an application of the binary logical operator XOR, “exclusive OR”): 111001 001011 ------ 110010 This result, 110010, is 50 in decimal. This tells us that flipping the coin on square 50 will move the encoded square from square 57 to square 11, the target square. Now we can leave the room, and prisoner 2 can enter and, following the steps above, independently calculate the encoded square, which we’ve now arranged to coincide with the target square. So we both go free. The whole principle is summarized concisely here: (Thanks, Gabriel. Somewhat similar: The Fifth Card.)

Click for Answer

Surprisingly, the answer is yes. Number the squares 0 to 63 and express these numbers in 6-bit binary (000000 to 111111). List the numbers of the squares that bear coins that are heads-up. Below each column in that list, write a 1 if the column contains an odd number of 1s or a 0 if it contains an even number of 1s. For example, suppose that the only heads-up coins are on squares 17, 21, 38, 44, and 55. Listing these in binary and condensing the list as described, we’d get:

111001 is 57 in decimal. Call that the encoded square; the second prisoner, on just viewing the board, could conduct the same calculations and identify this square independently.

Now how can we communicate the identity of the target square? It turns out that, by flipping a single coin, we can move the encoded square to any square we choose.

Suppose the target square is square 11. List this below the number of the encoded square, both in binary:

111001
001011

Below each column, write a 0 if the two numbers match and a 1 if they don’t (this is an application of the binary logical operator XOR, “exclusive OR”):

111001
001011
------
110010

This result, 110010, is 50 in decimal. This tells us that flipping the coin on square 50 will move the encoded square from square 57 to square 11, the target square. Now we can leave the room, and prisoner 2 can enter and, following the steps above, independently calculate the encoded square, which we’ve now arranged to coincide with the target square. So we both go free.

The whole principle is summarized concisely here:

(Thanks, Gabriel. Somewhat similar: The Fifth Card.)