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.
Consider the first row of the board Alice can change as a number of 8 bits.
To indicate a number between 1 and 128 in this binary system only seven bits are required. For ex. if the golden coin is in square 115 Alice has to "write" in his first row the number the number 115 in binary 01110011.
The first bit (0 in the example) is free, so she can use it to inform Bob if she is using the normal reading (115) or the inverse reading
10001100 (12 in decimal). This inverted system is needed because she has only three other moves to compose the number.
So, she looks how are disposed the coins on the first row. Then decide what system will use (normal or inverse) and put the first coin in position (if needed) to inform Bob.
To decide the system, she has to count the number of coins to turn in the normal system and the number of coins to turn in the inverse system. Their sum will be 7. (For ex. in normal 5 and in inverse 2, or 4+3, or 6+1). So she always can get her goal with a maximum of three other coins turned.
Last caveat: once Bob "read" the number and the system, he should count the squares from 0 (or from 255 in the inverse system) and in the order they have previously plan to do.
Edited on March 30, 2018, 2:29 pm
|
|
Posted by armando
on 2018-03-30 09:48:37 |
one possible strategy
