In the yard of the prison field 16x16. Some of the cells are stones, some are not. The jailer removes 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 cage indicated by the jailer to the first (in this case, they are released otherwise they face execution).

Prisoners can specify a strategy in advance, but after the start of the "game" they do not "communicate" in any way. The state of the field, both prisoners do not see before the "game".

How to win?

  • 9
    Long live the fairest court in the world! - Vfvtnjd

2 answers 2

You can do the following:

  1. We number all the stones according to their position. Ie, for example, a stone in the cell 0x0 will have a position 0, and a stone in a cell 16x16 will have a position 255
  2. For all positions of stones on the field, we apply XOR (exclusive OR) and at the output we get some arbitrary number from 0 to 255.
  3. If the number from p. 2 coincides with the position indicated by the jailer, then go to p. 5
  4. Otherwise, once again apply XOR for the number obtained in paragraph 2 and the position to which the jailer indicated. The resulting number will be the position of the cell in which we will change the state:
    • If a stone is already in the cage, then remove it.
    • Otherwise, add a stone.
  5. Now, when the second prisoner arrives, after completing Clause 1 and Clause 2, he will unambiguously receive the position of the cell to which the jailer has indicated.
  • one
    Explain p.2. The first argument of the XOR operation is the N-th position of the stone from 0 to 255, and the second argument? - Mikola
  • 3
    @Mikola, look, for example, if we have stones in positions 1, 100 and 237, then the result of item 2 for the first prisoner will be the expression: 1 XOR 100 XOR 237 = 136 If the jailer points to position 42 , then putting a stone in position: 136 XOR 42 = 162 , the second jailer, following paragraph 2, will receive 1 XOR 100 XOR 237 XOR 162 = 42 That is, desired position. - Ilya Pirogov
  • 2
    In my opinion, perfect. - Specter
  • 3
    @jmu, you did not understand anything. We are not looking for a changed field, we are looking for the cell indicated by the jailer. The information we need is the cell number, its address. This information - a number from 0 to 255 - fits in one byte. The second prisoner cannot find out what the field looked like before the first one changed the state of a single cell or what cell he changed, but he can calculate the checksum of the addresses of the stones he sees using the bitwise xor. He will receive a number from 0 to 255. The first prisoner must make sure that the second one gets the address of the indicated cell. - sercxjo
  • 3
    @Ilya Pirogov, somehow you have a lot of text) x - positions of initial stones y - positions of the resulting stones xor () - xor elements of the array e - position of the variable cell f - position of the specified cell xor (y) = xor (xor (x) , e) = fe = xor (xor (x), f) f = xor (y) - timka_s

I propose such an algorithm (consider the probability of winning yourself).

The first player must make sure that the number of stones on the horizontal and vertical lines passing through the specified glue is odd.

If both numbers are even, then the state of the indicated cell must be changed.

If one of the numbers is odd, for example for the horizontal, the state of the other cell on this line must be changed, while it is advisable to select a cell whose sum is vertically odd.

If both numbers of the indicated cell are odd, then we need to find two other verticals and horizontals with an odd number of stones and change the state of the cell at their intersection; if there is no such cell, do nothing.

The second player must find the horizontal and vertical with an odd number of stones. Of course, he may be mistaken, the first player only reduces the likelihood of this error.

Modification: the parity / oddness criterion is selected for the vertical and horizontal separately from which lines are smaller. Those. if it is less than even, we take the parity criterion, etc. The first player reduces the number of these lines by 1.

  • The biggest problem is if the number of cells at the intersection of the lines with an odd number of stones is more than 3. - Specter
  • @Spectre, it is not clear, explain in more detail - sercxjo
  • And, I understand, you mean that there are cells that can be mistakenly chosen by the second player. Yes, if there are 2 such cells, you can neutralize them with one stone, and if there are more, the problem will remain. - sercxjo
  • Yes it is. - Specter