Question:
In the courtyard of the prison, the field is 16×16. Some of the cells contain stones, some do not. The jailer displays the first prisoner and points to a random cell, after which the prisoner can change the state of any one cell – remove or add a stone (or change nothing). After that, the prisoner is taken away and another is brought in, who must guess the cell that the jailer pointed to first (in this case, they are released, otherwise they face execution).
The prisoners may agree on a strategy beforehand, but once the "game" has begun, they do not "communicate" in any way. Both prisoners do not see the state of the field until the start of the "game".
How to win?
Answer:
You can do the following:
- We number all the stones in accordance with their position. That is, for example, a stone in cell 0x0 will have position 0, and a stone in cell 16×16 will have position 255
- For all positions of the stones on the field, we apply XOR (exclusive OR) and get some arbitrary number from 0 to 255 at the output.
- If the number from item 2 matches the position indicated by the jailer, then go to item 5
- Otherwise, we once again apply XOR for the number obtained in step 2 and the position indicated by the jailer. The resulting number will be the position of the cell in which we will change the state:
- If there is already a stone in the cage, then remove it.
- Otherwise, add a stone.
- Now, when the second prisoner arrives, having done steps 1 and 2, he will definitely receive the position of the cage indicated by the jailer.