alice, bob and the coins

alice comes into a room in which there are laid out on a table two chessboards.
one chess board has a single pawn on it in a random position. the other one has an identical coin on each square. the coins show heads and tails at random.

alice looks at the chessboard with the pawn on it, then removes it from the chess board. then she turns over a single coin on the other board.

then alice goes into the soundproof room.

then bob comes in. he looks at the chess board with the coins on it, thinks long and hard, then removes a pawn from his pocket and puts it down on the other board in the same spot that alice removed it from!

how did they do it?

Okay, I give up. How do they do it?

--Mike Sheffler
... turning to the 3-D map, we see an unmistakable cone of ignorance
they memorized the order of the coins, which one was heads and which was tails, and when she took the pawn, she flipped over the coin that was on the same point on that chessboard than the one with the pawn, so then bob knew where to put it.
to clarify:

alice and bob are working together, ie they have worked out a plan together in advance

but before they come into the room neither of them know how the chessboards will be set up.
Can we get an answer, please?
alice and bob associate each square of a chessboard with an different ordered octuple (±1, ±1, ±1, ±1, ±1, ±1, ±1, ±1)
there are obviously 64 of these, so each one is associated with exactly one sq.
furthermore, we can multiply these together as follows:
we multiply the first element of A and B to get the first element of the A*B, the second elements of A and B to get the second element of A*B, etc.
Clearly the product of two ±1-octuples is another such octuple.

alice goes into the room and looks at the chessboard with the coins on.
she multiplies together all the octuples associated with each sq of the chessboard that has a head on it. (order of multiplication is unimportant)
the result is another such octuple, call it C.
she wants to change the octuple product of all the heads to the octuple associated with the sq with the pawn on it, call it D, by turning over one coin.
she just has to turn over the coin on the sq with the following octuple: the nth element is 1 if the nth elements of C and D are equal, -1 otherwise.

Bob goes in, looks at the coins, multiplies together the octuples for every square that has a head on it, gets an octuple, and this (hopefully) tells him which sq of the other board to put the pawn on.
Coins are my passion. I love to look at them and hold. I think about the history of the coin in hand. Who used it at one time? Where has it been? Did this Morgan dollar actually participate in a poker game in the old west? Did someone get shot for cheating? Its fascinating when you consider this type question. So much history in a litle piece of metal.
Thanks for your comment.
The physical nature of the coins isn't really central here.
Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?