11.4. There is a grid board $2015 \times 2015$. Dima places a detector in $k$ cells. Then Kolya places a grid ship in the shape of a square $1500 \times 1500$ on the board. The detector in a cell reports to Dima whether this cell is covered by the ship or not. For what smallest $k$ can Dima place the detectors in such a way as to guarantee the reconstruction of the ship's position?

(O. Dmitriev, R. Zhendarov)
Answer. $k=2(2015-1500)=1030$.

Solution. We will show that 1030 detectors are enough for Dima. Let him place 515 detectors in the 515 leftmost cells of the middle row of the square, and the remaining 515 detectors in the 515 top cells of the middle column. Note that for any position of the ship, its left column lies in one of the 516 leftmost columns of the board. If this column is one of the 515 farthest left, then the ship will cover a detector from this column, lying in the middle row; otherwise, it will not cover any detector from this row. Therefore, the columns in which the ship lies can be determined from the readings of the detectors in this row. Similarly, the rows in which it is located can be determined from the readings of the detectors in the middle column.

Now consider an arbitrary arrangement of $k$ detectors that meet the requirements. Consider two positions of the ship, differing by a horizontal shift of 1. The readings of some detector will differ for them only if this detector lies in the far left column of the left ship or in the far right column of the right ship. This means that in any two vertical rectangles $1500 \times 1$, differing by a horizontal shift of 1500, there is at least one detector. Similarly, in any two horizontal rectangles $1 \times 1500$, differing by a vertical shift of 1500, there is at least one detector. Let's call such pairs of rectangles vertical and horizontal, respectively.

Highlight all vertical pairs lying in the lower 1500 and upper 1500 rows of the board (there are $2 \cdot 515=1030$ such pairs). Similarly, highlight all 1030 horizontal pairs lying in the left 1500 and right 1500 columns. Divide the board into 9 rectangular areas as shown in Fig. 3. The highlighted pairs do not cover cells in $E$; each cell in the other areas is covered by two highlighted pairs (in $D$ and $F$ - by two vertical pairs, in $B$ and $H$ - by two horizontal pairs, and in areas $A, C, G$, and $I$ - by one horizontal and one vertical pair). Thus, each detector lies in no more than two highlighted pairs; therefore, to have at least one detector in each highlighted pair, at least $2 \cdot 1030 / 2=1030$ detectors are required.

Remark. There are many other examples of placing 1030 detectors that meet the requirements.

Comment. An example of placing 1030 detectors that meet the requirements is given - 1 point.

Only proved that $k \geqslant 1030-$ 5 points.

![](https://cdn.mathpix.com/cropped/2024_05_06_cb4ef974dfe09c8ba0f5g-4.jpg?height=365&width=363&top_left_y=566&top_left_x=920)

Fig. 5

If, in an otherwise correct reasoning, there is one or more errors of one unit in the count of detectors in the example or in the estimate (for example, it is claimed that the number of highlighted vertical pairs in the lower rows is 516, not 515) - 1 point is deducted.