The problem of 64 coins, two prisoners and one chessboard
- Transfer
Translator's note : I replaced the original designations of the sides of the head / tail coin with obverse / reverse so as not to confuse the Russian-speaking heads / tails. In the illustration above, on the left is an obverse (head), on the right is a reverse (tail).
Salvation is impossible?
This is one of those typical puzzles about prisoners in which you are sentenced to death and can be saved only if you prove your mental abilities to the jailer. You and your friend were imprisoned. Your jailer offers you a test. If you follow it, both of you will be freed.
Rules:
- The jailer takes you to a separate cell. In the chamber are a chessboard and a can with 64 coins.
- The jailer takes the coins one at a time and puts them on each square of the board. He places the coins randomly - some will be turned upside down, some will be reversed (or all will be obverse or reverse, you have no idea, everything is at the discretion of the jailer). If you try to intervene in the process of laying out coins, this will result in immediate death. If you try to coerce, advise, or convince the jailer in any way, immediate death. You can only watch.
- When all the coins are laid out, the jailer will point to one of the cells and say: “This!” The indicated cell - “magic” - is your key to freedom.
- The jailer will allow you to flip one coin on the board. Only one, but it can be any coin of your choice. This is the only change that you are allowed to make in the layout of the jailer.
- Then you will be taken out of the room. If you try to leave any messages or tips for your friend ... yes, you guessed it, immediate death!
- The jailer will bring your friend into the room.
- Your friend will have to inspect the board (it is forbidden to touch) and decide where, in his opinion, the “magic” cell is located.
- He has only one attempt. Based on the location of the coins, he must point to the cell and say: “This!”
- If he indicates correctly, you will both be pardoned and immediately released. If it’s wrong, both of you will be executed.
- The jailer explains these rules to both of you in advance and gives time to confer to develop a strategy.
Is it possible to develop a strategy?
At first glance, this problem cannot be solved. We cannot influence the jailer, the layout of coins can be any, and we have no idea which cell the jailer will point to (in fact, he himself probably does not know which cell he will choose).
64 cells to which he can point. 2 6 possible answers. We need 6 bits of information to accurately identify the cell. If you flip a coin, this is one bit of information. Since we cannot convey the state of the board “before”, our friend does not have the opportunity to indicate which coins were turned upside down. Think, if a friend enters the room and sees 63 obverse and 1 reverse, he cannot know that the only reverse is the coin that you turned over, or there was a board in front of you with 62 obverse and 2 reverse, and you turned over one reverse!
Is it possible to transmit 6 bits of information by flipping one coin?
There is a strategy that allows you to be saved with 100% probability, regardless of the layout of the coins and the position of the "magic" cell. The solution does not imply any fraud or tricks, it is purely mathematical.
Start
The problem can be solved, because in fact we have more information than one bit transmitted between you and your friend. The location of the remaining coins stores information, and we can use it. In fact, we have a sufficient number (six) of controlled bits in the coin layout, with which we can identify any cell on the board.
Two cells
Imagine that we have a board with only two cells. There are 4 possible options for the location of coins (A - obverse, P - reverse): PP, AA, RA, AR.
The jailer can choose as the "magic" as the first cell, and the second.
In advance, we agree on one rule - if the jailer points to the first cell (white), then it is necessary to make sure that the obverse is on the first cell. Possible options:
If the layout was PP, I can flip the first coin with an obverse, if AA - I will flip the second coin, since the first one is already turned with an obverse (according to our rule, this will not change anything, but I have to flip the coin).
In all cases above, the obverse was on the first cell. According to our rule, this means that the jailer chose the first cell.
Similarly, if the jailer points to the second cell, I will make it so that there is NOT an obverse on the first cell. This is a hint to my friend that the “magic” cell is not the first.
In all cases, there is no obverse on the first cell. According to our rule, this means that the jailer chose the second cell.
The problem is solved!
Induction
Mathematicians (and some programmers) will tell you that this is all we need to prove that a solution to the problem is possible. If we can encode one bit of information using two cells, then using mathematical induction we can confirm that it is possible to encode 2 bits in 4 cells, 3 in 8 ... 6 bits in 64 cells.
Binary representation
If we mark cells from 0 (upper left) to 63 (lower right) in binary representation, we can display which part of each nested set each cell is a part of.
The original article contains an interactive image of the board. The number in the lower left corner displays the cell number in binary notation. Each digit represents the set to which the cell belongs. A unit in any position indicates that the cell is in one half of the set, zero in the other. By definition, each cell is unique and has an individual set of bits.
Parity
Instead of using two cells as in the simple example above, we divide the board into various combinations of the two sets. We apply the same labeling rule to these two regions / sets as with single cells - we will denote if there is a “magic” cell in the first or second region.
Since regions are collections of cells, we cannot simply rotate all the coins in the region with an obverse. Instead, we flip one coin. We can calculate the number of obverse in the region - if their number is odd, we will take it as one, if even - zero. Turning over one coin in a region will change the number of obverse from odd to even, and vice versa (adding / subtracting a unit to any number inverts its evenness / oddness).
This is the concept of parity. Switching from one state to another by adding or subtracting one bit is widely used in computers.
To change the parity of a region, we just need to flip one coin in it.
Using masks of powers of two, we can divide the board into regions in several ways. Below are various ways of dividing the board, based on the state of the bits (power of two) in the cell number. The combination of these filters allows you to define one cell that can be turned over to change the parity of any / all bits.
2 0 is equivalent to a logical “AND” (AND) with 000001, 2 1 - 000010 ... 2 5 - 100000.
By definition, each cell has a unique set of bits. We can flip one coin to change the parity of any combination of these filters.
The layout created by the jailer has its own (natural) parity. Coins are arranged randomly, and we can calculate the parity (number of obverse) in each region. The combination of these parity bits will give us a random six-bit number.
To identify the “magic” cell, we need just six bits, and we can encode them using parity. We know that we can turn any onecoin, and this will lead to a change in one / several bits of the number. All we need is to find the right coin, turning it over will change the combination of parity bits so that we get the required number (binary notation of the number of the “magic” cell).
Together
Here I again send readers to the interactive model in the original article .
On the left board, you can select the location of the "magic" cell. At the bottom right is the number of the selected cell (Target = ...), on the left is its binary representation.
The board on the right shows the layout of the coins. Only obverse is depicted (for reasons of clarity), the reverse is indicated by empty cells. The “Random” button fills the board with a new random set of coins. The “Clear” button flips all the coins in reverse.
Under the right board, the gray color on the left indicates the parity of the board itself, green on the right is the number of the coin to be turned over. On the left, under its own parity, the same number is written in binary form.
Where do these values come from?
We already know where the number came from under the left board. This is just a binary description of the cell, each bit of the number indicates whether or not this coin is present in the power filters of the two shown above.
The gray number under the right board indicates the parity of the board itself. For each filter, we find an even or odd number of obverse located in this region. A unit in any digit indicates that the region has an odd number of obverse.
The green number indicates the number of the cell whose state you want to change (flip a coin) so that the parity of the board matches the desired number of the "magic" cell. It is calculated by performing a bitwise operation that excludes “OR” (XOR) over the board's own parity and the desired value.
Exclusive OR
The XOR operator is widely used in programming. It has several interesting properties. If the exclusive "OR" is applied twice with the same value, it will return to its original state:
(A XOR B) XOR B = A
Also, if we apply XOR to any number and a complete set of bits (a number consisting of one units ), all bits of the original number will be inverted. Applying XOR to a number and some set of (set) bits inverts these bits in the original number and saves the state of the rest.
That is why we used the XOR operator to calculate the position of the coin. For each parity bit, regardless of whether it already contains the correct value, we want to save it (XOR c 0), or we want to switch it (XOR c 1).
Example:
If the number of the “magic” cell is 101001 (41) and the parity is 010101 proper, then we need to flip the coin in cell 111100 (60):
You can also use XOR to quickly calculate your own parity. To do this, once go around the entire board and carry out this operation on each value (serial number) of the cell with an obverse.