Wise Men Without Hats
I am so used to wise-men puzzles about hats, that I was pleasantly surprised when Leonid Makar-Limanov gave me a wise-men puzzle that didn’t include them.
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?
If you are stuck, there are many approaches to try. You can attempt to solve the puzzle for a board of size 1 by 2, or for a board of size 1 by 3. Some might find it easier to solve a version in which you are allowed to have a multiple number of rocks on a cell, and the first wise man is permitted to add a rock to a cell that already contains rocks.
Share:
Bill:
Great problem! I believe this will work…
Assign each of the cells of the chessboard a number from 0-63. The number of the cell chosen by the sultan will be called X.
The first wise man should add up the total of the numbers of the cells that have a rock, and subtract the numbers of the cells that do not have a rock. The result will be an even number. Take the absolute value of this number and divide by 128. Take half of the remainder of that division and call it Y.
The first wise man now has the task of altering the chessboard so that the Y-value of the new configuration equals X. Subtract the current Y from X and take the absolute value. That is the number of the cell that the first wise man should perform his action on.
The second wise man now may look at the board, derive the Y-value, and identify the sultan’s cell. The sultan will then return their hats, as promised.
19 February 2010, 7:12 pmBill:
By the way, I used your suggestions for getting started. I was able to do the task on a 1×2 board, but not a 1×3 board. When I tried to solve for a 1×4 board, I was able to come up with a way to solve it. Perhaps it only works for even numbers, or powers of 2.
I believe I can prove that it is impossible to come up with a strategy for three squares. Let’s suppose for the moment that the wise men, wiser than I am, have developed a strategy for three squares.
And let’s say our sultan has the wise men, to minimize the chance of lucky guesses, perform the feat three times. Any strategy that works must work for all three cases.
The first time, the sultan presents the first wise man with an empty board. The first wise man has three possible squares to alter, leading to three possible conditions in which to leave the board. He must communicate one of three distinct squares with his move, so each of the three possible conditions – according to their pre-arranged strategy – must map to one of the three squares. Let’s say that a single rock on the first square indicates the sultan has chosen square A, a single rock on the second square indicates that the sultan has chosen square B, and a single rock on the third square indicates that the sultan has chosen square C.
I use letters instead of numbers because I am not privy to the wise men’s strategy, and I do not presume to understand their code. But the first man has only three options to communicate one of three pieces of information, and so a one-to-one correspondence is necessary.
For the second trial, the sultan presents the first wise man with a three-square chessboard that has rocks on the first two squares, and the third empty. Now, the first wise man may leave the chessboard with a single rock on the second square, which we already know will lead the second wise man to indicate the sultan has chosen square B. The first wise man may also leave a single rock on the first square, telling the second wise man to choose square A. The third and only remaining option open to the third wise man is to fill all three squares. This is the only way to signal the second wise man to choose C, and so it must be so in their strategy.
For the third trial, the sultan places rocks on the first and third squares, and leaves the second empty. The sultan chooses square B. How can the first wise man communicate this? The three options open to him are 1) a single rock on the third square (which already stands for square C, as established in the first trial), 2) all three squares filled (which already stands for square C, as established in the second trial), and 3) a single rock on the first square (which already stands for square A, as established in both trials).
There is no way for the first wise man to communicate this, regardless of what strategy they agreed upon beforehand. Therefore, there is no strategy that can work in all cases using a three-square board.
Using a two-square board works. If there are no rocks, the second wise man should choose the first square. If there are two rocks, the second wise man should choose the second square. If there is one rock, the second wise man should choose the square with the rock. It is a simple matter for the first wise man to indicate the chosen square regardless of initial configuration using this method.
19 February 2010, 7:40 pmBill:
I’m now thinking that my original answer made an inappropriate use of absolute value. Twice. I amend my solution here:
Assign each of the cells of the chessboard a number from 0-63. The number of the cell chosen by the sultan will be called X.
The first wise man should add up the total of the numbers of the cells that have a rock, and subtract the numbers of the cells that do not have a rock. The result will be an even number. If this number is negative, add any multiple of 128 that will make it positive. Now divide by 128. Take half of the remainder of that division and call it Y.
The first wise man now has the task of altering the chessboard so that the Y-value of the new configuration equals X. If X is larger than the current Y, then Y=Y+64. Subtract X from Y. This is the number of the cell that the first wise man should perform his action on.
The second wise man now may look at the board, derive the Y-value, and identify the sultan’s cell. The sultan will then give them 100 gold coins to be divided by whatever intricate system they wish to devise.
19 February 2010, 9:04 pmAustin:
Here’s another proof that there is no strategy for a 1×3 board:
Imagine that the wise men DO come up with a strategy. However complicated it is, we can depict it in a chart like so:
1. Fold a piece of paper to make two columns. Label them BEFORE and AFTER.
2. There are 8 possible configurations of pebbles. Draw each of them once in the BEFORE column. Do the same in the AFTER column.
3. For each BEFORE configuration, draw a red line connecting it to the AFTER configuration which the first wise man will select if the sultan has pointed to the first square. Similarly, draw green and blue lines to show what the first wise man will do if the sultan points to the second or third square, respectively.
When the chart is complete, there should be 24 lines in all, including 8 of each color. Coming out of each BEFORE configuration are one red, one green, and one blue line. A BEFORE and AFTER pair are only linked if they differ by the addition or removal of exactly one pebble, so there must be exactly 3 lines coming into each AFTER configuration as well.
The second wise man only sees an AFTER configuration. The chart indicates whether he has enough information to decode the sultan’s choice. If all the lines coming into that AFTER configuration are the same color, then he knows the sultan’s choice; otherwise, he can’t be sure. So, the strategy is only successful if every AFTER configuration is “monochromatic,” which would imply that the total number of red (or green, or blue) lines is a multiple of 3. That contradicts what we already know, namely, that there are 8 lines of each color. Therefore, no strategy can be successful all the time.
The logic of this proof should hold up whenever the number of squares isn’t a power of 2. Bill, that backs up a guess you made in your second comment, but it also makes me doubt your solution to the original puzzle. There are some details I wasn’t able to fill in… but assuming the solution works, it must somehow rely on 64 being a power of 2, and I can’t see how it does. However… what if instead of using 0-63, we use 6-bit binary codes for all the squares, and do all the arithmetic without carries? Then I think your solution works. The nice thing about binary arithmetic is that +1 = -1 (so adding a pebble becomes equivalent to removing a pebble).
19 February 2010, 9:41 pmPratik Poddar:
Nice problem. Solved it some time back.
If A xor B xor C xor Answer = K, then A xor B xor C xor K = Answer. This is a fairly obvious theorem, noting that X xor X is 0. And 0 xor X is X. So, if you take the first statement, and do C xor B xor A xor on both sides, we get the second statement.
Here, we number the squares of 8×8 from 0 to 63 in the obvious manner like the above proof, from 000000 to 111111. Now look at all those squares with a H and write them down (each is a 6 digit number). Also write down the secret square. Xor them all. We are essentially doing A xor B xor C xor Answer. We’ll get a K, some 6 digit number implying a square. Flip that square. Now, the next guy comes in. Looks at all those squares with a H and writes them down. Xors them all. He is essentially doing A xor B xor C xor K. He will get the answer.
Just in case people have qualms, note that flipping a coin is equivalent to taking a Xor. If the coin was a T and it became a H, it is obvious, the second guy will do A xor B xor C xor K. But if it was a H, and became a T, that square will not be part of the second list, and the second guy will be doing just A xor C, which you must note is the same as A xor K xor C xor K.
20 February 2010, 2:25 amBill:
There are times when I am able to compensate for my admittedly limited mathematical background with unbridled enthusiasm and a can-do spirit. This was not one of those times. I worked through the solutions you presented, and found the experience very educational. So I’d like to thank both of the wise men who posted here, hats or no.
And it seems to me that you are both advocating the same solution, the “xor” function having the same effect as binary addition without carrying, yes?
The solution as I now understand it makes perfect sense, but then I wondered why it wouldn’t work for any number of squares. So I went back and applied it to our three-square chessboard, which we know won’t work. And I see that if the sultan presents our first wise man with a three-square chessboard (00, 01, 10) with a single rock on the second square, and then chooses the third square, then the first wise man will have no way of turning the 01 into a 10 by moving only one rock. But if a fourth square were added (11), then the first wise man could put a rock on it, and the second wise man would know that the third square had been chosen.
So the reason that this solution can only work for a power-of-two chessboard is that only powers of two will give the first wise man the full range of options to switch the binary digits needed to change any number into any other. And the light breaks through the clouds!
Thanks again to you both, and to our wise host for posing the problem and providing this forum.
20 February 2010, 10:32 pmElla Rogers:
I think you guys will like this:
My students are totally engaged when I include online math games within a lesson or as homework. The repetition and association that games = fun really helps them capture the subjects. My class really enjoys https://www.mangahigh.com/en_gb/ a new site with Algebra, Geometry, Quizzes, etc.
24 February 2010, 7:03 amStefan:
I’m sorry, Bill, but I am convinced that a 3-square chessboard *does* present a solution.
The rocks on the board presented to the second wise man encode a binary string (such as 010 for a rock on only the second square). There are 8 such strings; to each we must assign a colour (by which I mean Square A, B, or C) such that
* At most one move is needed to get to any other colour
Then, by puzzling a little, the following colouring works:
000 a
001 b
010 c
011 c
100 c
101 c
110 b
111 a
Example: the first wise man is presented with rock combination 001 and square c. He adds a rock to make 011. Etc. In fact, in my construction I didn’t need the combination 100, as it is already connected to all other colours. I did not build this table in any systematic way, but I am sure it can be done.
8 March 2010, 1:18 pmBill:
I suppose it depends on how you interpret the following statement from the original problem:
“The first wise man has to decide whether to remove one rock or to add one rock to an empty cell.”
If the first wise man must choose between these two options, as we have been assuming, then there is no 3-square solution. If the first wise man has the option of leaving the board as it is, your solution seems to work.
10 March 2010, 4:20 amTanya Khovanova’s Math Blog » Blog Archive » Rainbow Graphs:
[…] gave you the Wise Men Without Hats puzzle in one of my previous posts: A sultan decides to check how wise his two wise men are. The […]
29 April 2010, 11:27 amTanya Khovanova’s Math Blog » Blog Archive » From a Puzzle to a Magic Trick:
[…] year ago I posted a chessboard puzzle. Recently I stumbled on a September 2008 issue of “Math Horizons” where it was […]
6 January 2011, 4:52 pmDaniel:
Add all the rocks on the chessboard
The first two spots on the board will be:
4 November 2013, 6:04 pm00 01 10 11
if the sum is even change these as follows:
10 11 00 01
if the sum is odd:
01 00 11 10
The next guy will come in and pick the second square if there are an even number of rocks, and the first if odd.