Solution
The Coin Board and the Key
Show the problem again
Two prisoners, Ann and Bob, may plan together once. A warden then lays out a board with N squares, each carrying a coin whose side (heads or tails) is chosen arbitrarily by the warden. The warden hides a key under one square and shows Ann the whole board and the key's square. Ann must flip exactly one coin, and then leaves. Bob enters, sees the board in its new state (but not the original), and must name the key's square. They go free if Bob is right. For how many values of N in the range 1 ≤ N ≤ 100 does a strategy exist that always works, whatever the warden chooses?
Worked solution
The answer is 7: exactly the powers of two, N = 1, 2, 4, 8, 16, 32, 64. Bob's answer is a function f of the board he sees. Whatever the starting board c and key k, Ann can flip one of N coins, reaching one of the N neighbours of c, and she needs a neighbour whose f-value is k. As k ranges over all N squares, she needs different neighbours for different k, so the N neighbours of every board must carry all N values exactly once each. Fix a value k: every board then has exactly one neighbour with f = k, which makes the set {f = k} a perfect code in the N-cube; these sets partition the 2^N boards into N classes of equal size 2^N/N, which must be an integer. Hence N divides 2^N, so N is a power of two. Conversely, if N = 2^m, number the squares 0 to N − 1 and let f(board) be the XOR of the numbers of the squares showing heads. Flipping square j changes f by j, so Ann flips square (current f) XOR (key) and Bob reads the key from f. Among 1 to 100 the powers of two are 1, 2, 4, 8, 16, 32, 64: seven values. (Checked by exhaustive search for N ≤ 6 and by verifying the XOR scheme for N = 1, 2, 4, 8.)
Source: Generalisation of the classic 64-square chessboard-and-coins prisoner puzzle in wide circulation; no traceable original source. Statement written for AxiomIQ.