Problem of the Week 1244

Going for Gold

Charlie has 64 identical-looking gold-colored coins; all are counterfeit except one.

He calls Alice into his office and seats her at a table containing an 8 × 8 chessboard. He places the coins on the board, one to a square, with each coin showing either a head or tail as he chooses. He tells Alice which coin is made of gold. Alice can then turn any one of the coins upside down, replacing it on its square, or do nothing if she wishes. She then leaves the room.

Bob enters and is seated in the same position, facing the board. He may take one of the coins.

Find a joint strategy that allows Bob to select the gold coin.

As usual, Alice and Bob know the protocol in advance and can plan a strategy, but cannot communicate after Alice enters the room.

Extension: The problem above shows that C(1) ≥ 64, meaning that if Alice can turn one coin, then she can communicate any one of 64 numbers. Of course, C(64) = 2⁶⁴, since she can arrange the board to display the bits of any of 2⁶⁴ integers.

How large is C(2)? That is, still with the 8 × 8 board, how much can Alice communicate if she can turn 2 coins?

Source: Heard from Paul Cuff, though this is probably an old folklore problem.

Source: Dan Velleman (Amherst College)