7.5. Pasha is playing a computer game. The game takes place on an infinite grid. Each cell contains either a treasure or a natural number. The number indicates the distance to the nearest treasure in cells (if it takes $A$ steps vertically and $B$ steps horizontally to reach the treasure, the cell contains the number $A+B$). In one move, Pasha can reveal the contents of one cell. The goal of the game is to find at least one treasure.

a) Pasha revealed three cells in a row horizontally. Each of them contained the number 5. What is the minimum number of additional moves Pasha needs to make to definitely find a treasure?

(2 points)

b) Pasha revealed some three cells, and they contained numbers. Could it be that from this information, Pasha can definitely find a treasure with the next move?

(3 points)

c) Pasha knows that each number on the field does not exceed some fixed $K \geqslant 3$. Can Pasha definitely find a treasure by making no more than $K+3$ moves?

2) Pasha knows that each number on the field does not exceed 2023. Will 20 moves be enough for Pasha to definitely find a treasure?
Solution. a) Note that if Pasha finds a certain number $K$ in a cell, then at least one treasure must be located in the cells along the perimeter of a square rotated by $45^{\circ}$ relative to the grid lines, where the side of the square is exactly $K+1$ cells. At the same time, there cannot be any treasures inside such a square. Let's construct such squares around the fives found by Pasha. The treasure related to the central five can only be located above or below it at a distance of 5 cells, as the other cells on the perimeter will be covered by other squares. But one of these cells may not contain a treasure, so Pasha will need more than one move to guarantee finding it. For other fives or cells outside the squares, it is also impossible to determine the exact location of the treasure. Therefore, Pasha needs at least two moves (these moves are marked with a star in the figure).

![](https://cdn.mathpix.com/cropped/2024_05_06_214715549e9b39285e0cg-3.jpg?height=458&width=534&top_left_y=1148&top_left_x=340)

To the solution of problem $7.5 \mathrm{a}$

![](https://cdn.mathpix.com/cropped/2024_05_06_214715549e9b39285e0cg-3.jpg?height=452&width=331&top_left_y=1151&top_left_x=1469)

To the solution of problem $7.5 \mathrm{b}$

b) The figure shows one of the possible situations where the position of the treasure can be determined unambiguously. The treasure is located in the cell marked with a star, as the other cells of the square around the one are covered by the inner cells of the squares around the twos.

c) Suppose Pasha checks two adjacent cells horizontally with his first two moves. The numbers in these cells are either equal or differ by 1 (if, of course, a treasure is found, then Pasha has completed the task). In both cases, the squares around these two numbers will overlap such that the treasure related to the smaller number (or any of the equal numbers) will be located in cells forming only two sides of the square. Let the smaller number be $N \leqslant K$, and, without loss of generality, the specified sides will be to the left of it. The situation is shown in the figure (the sizes of the square are shown schematically).

With the next moves, Pasha will check the cells from left to right, from 1 to a maximum of $N-1$—until the number in the cell matches the number of this cell. If 1 matches, then the treasure should be searched in the three cells around it, and if it does not match, then there is definitely no treasure in these three cells. If 2 matches, the treasure should be searched two cells above or below, and if it does not match, then there is definitely no treasure in these two cells, and so on. If, as a result of such actions, no number matches in any cell, including the number $N-1$, then the treasure should be searched in the last two cells—above or below the number $N$.

Thus, to find the treasure, Pasha will spend: 2 initial moves, no more than $K-1$ moves horizontally, 2 moves to find the treasure above or below the number (3 moves if he gets lucky on the first cell). In total, $2+(K-1)+2=K+3$ moves. Or $2+1+3=6$ moves, but $6 \leqslant K+3$ by the condition.

d) The first two moves will be made in the same way as in part c). For the remaining corner of two sides of the square around the number $N$, we will make three more moves—to its ends and the central cell. If the treasure is still not found, then the suspicious cells will remain in two diagonal segments, containing $N-1 \leqslant 2022$ cells.

Now let's describe the next operation. If in such a segment we select $M+1$ consecutive cells, then there exists a square for which the selected cells form a side. At the same time, all other cells of the square lie strictly inside the square with side $N$ obtained by the first two moves, and therefore definitely do not contain the treasure. Then Pasha can check the central cell of the square—if it turns out to be the number $M$, then among the selected $M+1$ cells there is a treasure, and if not $M$—then there is no treasure. For convenience, this operation will be performed for any $M \geqslant 0$, and for $M=0$ the square together with the boundary is just one cell.

Using the described operation, Pasha will first leave one of the two segments. Then we will divide the segment in half—selecting half of the cells from one of the edges (if the number of cells is odd—half of all, not counting the central one). Then even in the worst case, he will need no more than 12 moves, since $2^{11}>2022$. Indeed, the number of unverified options in 11 moves will not exceed 1011, 506, 253, 127, 64, 32, 16, 8, 4, 2, 1 cells, respectively. In total, Pasha will spend no more than $2+3+1+12=18$ moves, which is even less than the proposed twenty.

Answer. a) 2 moves b) It could.