9.6. The field is a square grid of $41 \times 41$ cells, one of which conceals a tank. The fighter aircraft shoots at 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?

(S. Berlov, A. Magazinov)
Answer. $\frac{3 \cdot 41^{2}-1}{2}=2521$ shots.

Solution. Color the cells in a checkerboard pattern so that the corners of the field are black. Suppose the pilot first shoots at all the white cells, then at all the black cells, and then again at all the white cells. 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 $41^{2}+\frac{41^{2}-1}{2}=\frac{3 \cdot 41^{2}-1}{2}$ shots.

It remains to show that fewer shots will not suffice. 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 will 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. This is impossible; hence, such pairs of cells do not exist.

Now, divide the entire board into $\frac{41^{2}-1}{2}$ rectangles of $1 \times 2$ and one cell. By the proven fact, the fighter must make at least three shots in each rectangle, and at least one shot in the remaining cell. In total, he made no fewer than $3 \cdot \frac{41^{2}-1}{2}+1=\frac{3 \cdot 41^{2}-1}{2}$ shots.