The chessboard puzzle - solution

The week before last we presented you a puzzle and asked if you could solve it.

Congratulations to all those who managed to solve it themselves!

Here you will find the correct solution:

Solution Step 1

Let's start small: with a "chessboard" of two squares. The same rules, but much clearer.

Computer scientists like it binary, so head is now 1 and number 0. Two fields are two bits. We agree on the following: The second bit specifies which field is the "key field". If it is the first (for computer scientists: 0-th) field, we turn the coin of the second field to number (=0); if it is the second (for computer scientists: 1-th) field, we turn the coin of the second field to heads (=1). If this coin was already pointing right side up, we simply flip the coin on the first field, because we have to flip exactly one coin.

How big (in bits) is the information we have to transmit here? Exactly: 1 bit, because with it we can say after previous agreement which coin is on the key field. For one bit, two coins are enough, because you have to flip one.

The whole solution

OK, that was easy. You can now show by induction that for n bits of information you always need 2 to the power of n coins. (And also that it only works if the total number of squares is 2 to the power of anything). In our case, we need 6 bits and for that 2 to the power of 6 = 64 coins.

But we don't continue mathematically inductively, but concretely.

Let's count all squares on the chessboard from 0 to 63 (0 top left, 63 bottom right).

We name the columns from left to right as usual for chessboards from "a" to "h" and the rows from bottom to top (!) with "1" to "8".

Now we look at the individual bits of the numbers 0 to 63 one after the other.

All numbers where the first bit (000001) is set (i.e. the odd ones: 1, 3, 5...) are on the chessboard in the columns "b", "d", "f" and "h" as colored below. The other columns contain the numbers where this bit is not set (i.e. the even numbers).

All numbers where the second bit (000010) is set (2, 3, 6, 7 etc.) are in the columns "c", "d" as well as "g", "h".

And so it goes on: All numbers where the third bit (000100) is set (4, 5, 6, 7, 12, 13...) are in the right half (columns e, f, g, h) of the chessboard, those where the bit is not set are in the left half.

At the fourth bit (001000), we switch from columns to rows, because all numbers where this bit is set are in the rows "1", "3", "5" and "7" (counting from bottom to top).

If the fifth bit (010000) is set, this describes on the chessboard all squares of the rows "1", "2" as well as "5" and "6".

If the sixth bit (100000) is set, this describes on the chessboard the lower half (rows 1-4) of the chessboard.

You - the first prisoner - know which is the key square. You now count all the coins on the squares belonging to "bit 1" (i.e. columns "b", "d", "f" and "h"). If this number is even, then the result is 0, otherwise 1. You write down this "bit 1 result" of the chessboard.

Now you count all the coins on the squares marked by bit 2 and showing "heads" and get your "bit 2 result" of the checkerboard. So it goes on until you have all 6 results. This is a 6-bit number, between 0 and 63. We call it the "6-bit state" of the checkerboard.

So we can assign a number between 0 and 63 to each of the 18 trillion ways the coins can lie.

What does this do for us? How can you now rotate a coin so that the current "6-bit state" becomes the state that indicates the key field?!

If you know how to do it, it's quite easy. We have to apply the bit operation "XOR" (exclusive OR). Thereby a result is calculated from two bits: Only if both bits are different, "1" comes out, if they are equal, then "0".

Let's assume the key field is field 7 (000111) and the current 6-bit state according to the above counting method is 43 (101011), then we apply XOR to the bit sequence 000111 and 101011 in turn, so we set the different bits to 1 and get 101100 (44) and flip the coin to field 44. If our crony determines the "6-bit state" again according to the above counting method, he gets 7 out, the key field!!!

Special case on the side: Also here it can happen as in the example with two fields of course that the 6-bit state of the chessboard is already correct. You have to flip a coin even then, what to do? The same as above: You then apply XOR to the same number in the "6-bit state" of the checkerboard. Since then no bit deviates, you get 0 out. That means, you can turn the field 0 as you like, it has no effect on the result.

For those who would like to understand this in more detail, there are these detailed explanations, which are well worth reading and seeing:

https://www.youtube.com/watch?v=as7Gkm7Y7h4

https://datagenetics.com/blog/december12014/index.html.

We hope you enjoyed the puzzle as much as we did!

Your Faktor Zehn team