Wise men, no hats
A sultan decides to check how wise his two wise men are. The sultan chooses a cell on a chessboard and shows it to the first wise man. In addition, each cell on the chessboard either contains a rock or is empty. The first wise man has to decide whether to remove one rock or to add one rock to an empty cell. Next, the second wise man must look at the board and guess which cell was chosen by the sultan. The two wise men are permitted to agree on the strategy beforehand. What strategy can they find to ensure that the second wise man will always guess the chosen cell?
Problem source: Leonid Makar-Limanov via Tanya Khovanova’s Math Blog.
March 9th, 2010 at 1:35 am
Clearly the second wise man didn’t see the board before the first one altered it (otherwise, the first one could just change the state of the square the sultan chose).
So the first wise man must pick a square whose state to change, to identify the square to the second wise man even though the algorithm used by the former must be able to cope with /any/ arrangement of rocks, and the latter sees only the changed arrangement.
There are 2^64 possible states before the first wise man acts. By careful choice of square, he can put the board into his choice of any one of 64 sets of states, and the choice of set identifies the chosen square.
How about: Number the squares thus:
00 01 02 03 04 05 06 07
08 …
…
56 57 58 59 60 61 62 63
Add the squares that have rocks on them, working modulo 64 the whole time. The first wise man tries to arrange matters so that the answer will be the number of the chosen square.
He finds out what the answer is right now. If, for example, it is too high by 1, he either removes a rock from square 1 or adds one to square 63. (But what if square 1 was empty and square 63 already has a rock?)
Second try. The wise men agree to number the squares as before, but exclusive-or the squares that have rocks on them. The first wise man hears the sultan choose square C. The result of exoring the rocks is, say, A. The first wise man thus changes the state of square (C xor A).
For example, the sultan chose square 3 = 000011 (binary). The first wise man exors the rocks and finds that the result is 5 = 000101 (binary). He changes the state of square 6 = 000110 (binary) so that now when the second wise man exors the rocks he will find that the result is 3 = 000011 (binary).
October 8th, 2010 at 1:38 pm
The wise men agree to number the squares as before, but exclusive-or the squares that have rocks on them. The first thomas sabo
wise man hears the sultan choose square C. The result of exoring the rocks is, say, A. The first wise man thus changes the state of square