# Task 10.5

The field is a $41 \times 41$ grid, in one of the cells of which a tank is hidden. The fighter aircraft shoots one cell per shot. If a hit occurs, the tank moves to an adjacent cell along a side; if not, it remains in place. After each shot, the pilot does not know whether a hit occurred. To destroy the tank, it must be hit twice. What is the minimum number of shots required to guarantee that the tank is destroyed?

## Points 7

#
# Answer:

2521 shots

## Solution

## Example.

Let's color the cells in a checkerboard pattern so that the corner cells are black. Suppose the pilot first shoots at all the white cells, then at all the black ones, and then again at all the white ones. If the tank was on a white cell, the pilot will destroy it in the first and second series; if it was on a black cell, then in the second and third series. In this case, the pilot will make no more than $41^{2}+$ $1 / 2\left(41^{2}-1\right)=1 / 2\left(3 \cdot 41^{2}-1\right)=2521$ shots.

## Estimation.

Suppose the pilot has a sequence of shots after which the tank will be guaranteed to be destroyed. Clearly, he must shoot at least once at any cell (otherwise, the tank in that cell would not be destroyed). Assume there are two adjacent cells $A$ and $B$, at which he shot exactly once, and the shot at $B$ occurred later. Then, if the tank was initially in $B$, it could have moved to $A$ after the shot at $B$, and the second hit would not have occurred. Therefore, such pairs of cells do not exist. We can divide the entire board into $1 / 2\left(41^{2}-1\right)$ dominoes $1 \times 2$ and one cell. The pilot must make at least three shots into each domino and at least one shot into the remaining cell. In total, he made no fewer than $1 / 23 \cdot\left(41^{2}-1\right)+1=1 / 2\left(3 \cdot 41^{2}-1\right)$ shots.