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)
Bob and Alice before the beginning establish that h means 1 and t means 0.
They also accord that if the first square on the left has an "t" he will begin the count of squares from 0 (first square on the left) going left-right to the square 127. Otherwise (if the first square has "h") he will count from 127 down to 0.
The game begin and Charlie decide this disposition for the first row: hhthhtht (h=head, t=tail) and inform Alice in what square is the golden coin. Alice counts left-right the squares from 0 and see that the coin is in the square 115.
She now watch the disposition of the first row and translate mentally (h=1 t=0 in the number 11011010)
She needs Bob to read there 01110011. So she need to change bites 3, 5, 8 from the initial 11011010 in the first row. But if she leaves like that, as the first left square has 1, Bob is going to begin the count as a count down from 127 to 0. So she also change the first bit from 1 to 0.
Now she can leave the boards. Bob enters an find the first row thhhtthh. The beginning t informs him that the reading goes from 0 to 127. The other seven bits informs him that the golden coin is in square number 115.
It seems possible to me.
Edited on March 31, 2018, 5:53 am
|
|
Posted by armando
on 2018-03-31 03:26:21 |
re(2): one possible strategy
