Posted on: March 7th, 2014 by
5

A and B are prisoners. The jailer have them play a game. He places one coin on each cell of an 8x8 chessboard. Some are tails up and others are heads up. B cannot yet see the board. The jailer shows the board to A and selects a cell. He will allow A to flip exactly one coin on the board. Then B arrives. He is asked to inspect the board and then guess the cell selected by the jailer. If B guesses the correct cell among 64 options, A and B are set free. Otherwise, they are both executed. Is there a winning strategy for A and B? (They can co-operate and discuss a strategy before the game starts).

- via Algorithmic puzzles

Since 64=2^6, each cell is identified by a 6-bit label. For a given configuration of coins on the board, let P be the 6-bit integer whose bit in position i is the parity of the number of heads among all cells whose labels have a 1 in position i.

Prisoner A computes the initial value of P and the label X of the jailor's selected cell, and flips over the coin whose label is P XOR X. The effect of this is to flip a bit in P exactly when it differs from the corresponding bit of X, so that the new value of P is equal to X; prisoner B can simply read this off.

Would you please give an example for

a) a 2 by 2 grid?
b) Does solution hold if jailer rotates board?

a) The cells are labeled 00,01,10,11. Suppose cells 01 and 11 have heads-up coins, so P = xor(01, 11) = 10. The jailor selects cell 00, so prisoner A flips coin 10, which changes P to xor(01, 10, 11) = 00.

b) No, but that's an interesting modification. Hmm