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

My friend noticed that P is simply the bitwise-XOR of the labels of the cells with heads-up coins. This makes the solution easier to understand: prisoner A computes the initial value of P, compares it to the desired message (i.e. the label of the jailor's cell) to determine which bits of P he needs to change, and flips the coin whose label has a 1 in exactly those bits.

We also proved that there's no winning strategy if the number of cells is not a power of two:

With N cells, there are 2^N possible coin configurations. Each configuration is adjacent to (i.e. one coin flip away from) exactly N other configurations.

Suppose K_1 configurations denote "choose cell 1" to prisoner B. There are at most K_1*N adjacent configurations from which prisoner A could send this message; in a winning strategy, this must include all 2^N possible initial configurations, so K_1*N >= 2^N, i.e. K_1 >= 2^N/N. This applies to every possible message, so we have (K_1 + ... + K_N) >= N*2^N/N, i.e. 2^N >= 2^N. The strict inequality case is a contradiction, so we must have K_1=2^N/N, so N evenly divides a power of 2.