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

He calls Alice into his office and seats her at a table containing two 8 × 8 boards, with a coin on each of the 128 squares, each coin showing a head or tail as he chooses.

He tells Alice which coin is made of gold. Alice can then turn at most 4 coins upside down, replacing them on their squares, but her inversions must all be on the first row of the left-hand board. She then leaves the room.

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

Find a strategy that allows Bob to always take the gold coin.

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

(In reply to re: one possible strategy by Dej Mar)

Actually I was content with armando's ingenious method, but perhaps one change is needed.

The possible binary representations with 7 bits range from 0000000 to 1111111 i.e. 0 to 127. So the first square should perhaps be numbered 0, and the 115th square 114, or 01110010.

Otherwise it seems to work fine, e.g. if the desired number is 8, counting as explained above, and the first row reads 86, then

1 0 1 0 1 1 0  86
        
0 0 0 1 0 0 0  8
        
X 0 X X X X 0   5 changes required, so we try (127-8)
        
0 X 0 0 0 0 X  119 and only 2 bits need to be changed.

For the reason given by armando, if 3+n bits of the 'ordinary' representation needs to be changed, then by definition, 4-n of the 'inverse' representation do.

 

Edited on March 31, 2018, 3:05 am

Posted by broll on 2018-03-31 02:53:21