A magician and her assistant perform the following trick with a
chess board and 64 pennies.

The assistant first blindfolds the magician, and then calls
for a volunteer from the audience.
He asks the volunteer to point at one square on the chessboard.
He notes the square that was selected, then gives the volunteer
the 64 pennies, and asks him to place one penny on each square
of the chessboard, each penny randomly showing heads or tails.

The assistant then flips exactly one penny,
and removes the magician's blindfold.
The magician then studies the board, and announces the square
that the volunteer picked.

For this problem, of course, the magician uses no information
other than the pattern of the pennies on the chessboard.
How is the trick performed?

Evidently, the assistant, in flipping one penny, must produce
a patter of heads and tails, from which the magician can deduce
the square that was selected.

Let's start by assigning 1 to heads and 0 to tails, so that the
board is an 8x8 array of binary digits.
From this array, the magician has to deduce the x and y coordinates
of the chosen square.
Number the rows and columns from 0 to 7.
Then let x and y be the coordinates of the selected square.
Write these using 3 digits binary digits (0 or 1) as
x_{2}x_{1}x_{0} for x and
y_{2}y_{1}y_{0} for y.

Now for a bit of notation to facilitate the exposition.
Let P(k) be the parity of the integer k, that is,
P(k) = 0 when k is even and P(k) = 1 when k is odd.
Let R_{i} be P(sum of entries in row i), that is, the parity
of the sum of all the 0's and 1's in row i.
Finally let C_{i} be P(sum of entries in column j), the parity
of the sum of all the 0's and 1's in the jth column.
Note that flipping one coin in row i changes the value of R_{i}
from 0 to 1 or from 1 to 0; a similar fact holds true for columns.

The plan is for the assistant to flip exactly one coin so that the magician
can read off the values x_{2}x_{1}x_{0} and
y_{2}y_{1}y_{0} from the board, using these
(magic!) formulas:

x_{2} = P(R_{4} + R_{5} + R_{6} + R_{7})

x_{1} = P(R_{2} + R_{3} + R_{6} + R_{7})

x_{0} = P(R_{1} + R_{3} + R_{5} + R_{7})

y_{2} = P(C_{4} + C_{5} + C_{6} + C_{7})

y_{1} = P(C_{2} + C_{3} + C_{6} + C_{7})

y_{0} = P(C_{1} + C_{3} + C_{5} + C_{7})

Having done that, the magician can then determine the numbers
x_{2}x_{1}x_{0} and
y_{2}y_{1}y_{0} in binary, which gives her
the coordinates of the selected square.

Now, how does the assistant arrange for it all to work out?
Let's deal with the rows first.
The assistant starts by calculating the x_{2}, x_{1}
and x_{0} values from the board after the volunteer has placed all the pennies.
These may already have the desired values, but it's more likely that
at least one of them will be incorrect.
He needs to flip exactly one coin to correct the values of all three binary digits.

Let's look at some cases.
First of all, suppose all the x values are incorrect.
In that case, the assistant can flip any penny in row 7; that will change the parity
of R_{7}, and will correct all three x values, since the formula
for each includes R_{7}.

Or suppose that x_{1} is initially correct, but the other two x
values are incorrect.
Then by flipping any coin in row 5, the other two x values can be
corrected, since R_{5} is included
in the defintion for x_{2} and x_{0}, but not
in the definition for x_{1}.

In fact, for any combination of x values, there's a row in which the
assistant can flip any coin to make all three x values correct!
You can check all the cases in the following table; the target row
is the one in which the assistant can flip any penny to make all
three x values correct.

x_{2} ok? |
x_{1} ok? |
x_{0} ok? |
target row |

yes | yes | yes | 0 |

yes | yes | no | 1 |

yes | no | yes | 2 |

yes | no | no | 3 |

no | yes | yes | 4 |

no | yes | no | 5 |

no | no | yes | 6 |

no | no | no | 7 |

Any penny in the indicated row can be flipped, since the
definitions are based on the parity of the sum of all the entries
in each row.

The assistant then repeats the process using the columns.
He can always find a column with the property that flipping any
coin in that column will correct the 3 y values.

So all the assistant has to do is flip the penny that is in the intersection
of the row and the column found by the above process!
This will correct ALL of the x and y values, so that they yield the binary
digits of the coordinates of the chosen square.
When the magician's blindfold is taken off, she just applies the same
formulas to read off the coordinates.

Admittedly, there's a fair bit of mental arithmetic needed, so the magician
and her assistant may need to practise the trick 2 or 3 times before
presenting it in public.