This is what I’ve told my two mathematician friends:
“Imagine a 64-square chessboard with a coin on each square.
Each of the coins has either head or tails facing up, chosen at random.
I check the board and decide which coin will be my favorite one.
One of you (say A) will be with me, see the chessboard and I will reveal to him (only to him) which coin is my favorite. He then must flip over exactly one of the coins on the chessboard, while the other mathematician (B) is in another room not looking.
Once the coin is flipped over, the uninformed mathematician (B) is summoned into the room and must deduce which coin is my favorite only by examining the coins on the chessboard.
To secure absence of any other hints A is escorted out of the room.
Clearly, prior to the procedure, you are free to discuss the problem between the two of you and establish its solving strategy. You have no time limit, you are free to use any kind of calculator, but any communication between you two is strictly prohibited”
What strategy can the two mathematicians devise to ensure that my favorite coin can always be correctly identified?
(In reply to
re(2): The egg of ColuMbus + SOLUTION by Ady TZIDON)
1. A will agree with his friend B that they map the board from top-left to bottom-right from 0 to 63.
2.Heads count as 1's in the 6-digit binary representations corresponding to their locations, tails as zeros.
3. A will XoR all the Heads "addresses" and get one 6-bit binary number as a result, say string RES.
4. After being told by the challenger a particular ("favorite") square, which has an address as defined above, say FAV, A will evaluate RES XOR FAV, to get another string, NEW, and flip the coin on the corresponding square (the one with that address).
5. A exits, B enters and evaluates the total XOR of heads (i.e., their binary numbers)
6. The result is FAV - non related number, since RES XOR FAV = NEW, but when this is flipped, the result will be a new value of the XOR'ed heads addresses that matches the chosen "favorite" number.
Example:
Let’s say that there are heads only on 3,7,20,61 and the "chosen" square is 8: binary XOR on HEADS{3,7,20,61} will be:
000011
000111
010100
111101
------
101101 (DEC 45)
101101 (DEC 45) XOR 001000 (DEC 8) =100101 (DEC 37)
Flipping the coin on the 37 square (which is now an additional heads) creates a new result for B:
000011
000111
010100
111101
100101
------
001000 (DEC 8)
when B XORs the heads - he gets the secret number: position 8, which square he points out.
|
|
Posted by Charlie
on 2016-02-03 22:53:36 |
Suggested wording for solution.
