Using your Head is Permitted

September 2015 solution

Let each position on the chess board correspond to a unique 6-bit string, and let the value of the board (initially, v) be the XOR of all the strings associated with places that show "heads".

Furthermore, let u be the string associated with the position where the piece of paper is hidden.

By flipping the coin at position u XOR v, Prisoner A can switch to a new board configuration whose value is u. At this point, Prisoner B can simply read this value off the board and determine where the piece of paper is hidden, thus guaranteeing the pair's release.

Back to riddle

Back to main page