Coins on a Chessboard
There is a room with a chessboard inside. On each of its 64 squares, there is placed a coin, either heads up or heads down. You enter the room and a person inside points towards one special square on the chessboard and gives you the chance to flip one of the coins (whichever you choose). Then you leave the room, your friend enters and has to guess which was the special square on the chessboard. If you two could devise a plan before entering the room, how would you make sure your friend always guesses correctly which is the special square?
First, you must enumerate the coins with numbers from 1 to 64, locate the mystery coin, and calculate the binary representation of its number, padded with zeros on the left to 6 digits length. For example, if the mystery coin is the 5th one on the 4th row, its number would be 29 and will have a binary representation 011101. Then, consider the following sets of coins:
A1 = {row 1, row 2, row 3, row 4}
A2 = {row 1, row 2, row 5, row 6}
A3 = {row 1, row 3, row 5, row 7}
A4 = {column 1, column 2, column 3, column 4}
A5 = {column 1, column 2, column 5, column 6}
A6 = {column 1, column 3, column 5, column 7}
Now, the strategy is to flip the coin which makes the parity of heads in set Ai odd if and only if the i-th digit in the binary representation of the mystery coin is 1. It is easy to check that this is always a possible thing to do.
We do not know where this puzzle originated from. If you have any information, please let us know via email.