# 8. Clone 1

The playing field for the game "Battleship" is a rectangle $1 \times 203$. Petya places single-cell detectors on this field, after which Vasya places a two-deck ship (rectangle $1 \times 2$). A detector triggers if the cell it is placed on is under the ship. What is the minimum number of detectors Petya should place to uniquely determine the position of Vasya's ship based on their readings?
# Answer: 134

## Solution

The solution to this problem consists of two parts: an estimate, where we will prove that it is impossible to get by with fewer detectors, and an example that shows that the given number of detectors is sufficient.

Estimate.

Remark 1. If next to a detector there are two free cells, then in the case where it triggers, it will not be possible to determine the position of the ship, as we will have two possible options for its location.

Remark 2. There can be no more than one interval of two adjacent cells free of detectors. Otherwise, in the situation where no detector triggers, the position of the ship cannot be uniquely determined. This, in particular, means that three cells in a row cannot be empty.

We will prove the estimate in the general case, let the rectangle have dimensions $1 \times 3k+2$ cells. We will divide the field into rectangles $1 \times 3$. In total, we will get $k$ rectangles and two cells will remain. We want to prove that there should be at least $2k$ detectors.

![](https://cdn.mathpix.com/cropped/2024_05_06_f1445201e81a69006a8ag-09.jpg?height=129&width=948&top_left_y=2037&top_left_x=608)

In each rectangle $1 \times 3$, there are 2 rectangles $1 \times 2$ that intersect at the central cell. Let's highlight on the field $2k+1$ rectangles $1 \times 2$ - two in each $1 \times 3$ and the last two cells.

Suppose there are no more than $2k-1$ detectors, then there are at least two empty rectangles $1 \times 2$, which is impossible according to Remark 2.

It should be noted that one detector can belong to 2 rectangles $1 \times 2$, but then it stands in the center of the rectangle $1 \times 3$, and such a placement, according to Remark 1, does not allow the position of the ship to be determined uniquely.

Thus, if we have $3k+2$ cells, then there should be at least $2k$ detectors.

Example.

Let the first two cells be empty, and then in each subsequent triplet of cells, place two detectors in a row, and leave the third cell empty. We will prove that in this case, we can determine the position of the ship. If no detector triggers, then the ship is on cells 1 and 2. If two detectors trigger, then the ship is on them. Let's call two detectors standing next to each other the left and right detectors. If the left or right detector triggers, then the ship is on it and the adjacent empty cell.

## Clone 2

The playing field for the game "Battleship" is a rectangle $1 \times 221$. Petya places single-cell detectors on this field, after which Vasya places a two-deck ship (rectangle $1 \times 2$). A detector triggers if the cell it is placed on is under the ship. What is the minimum number of detectors Petya should place to uniquely determine the position of Vasya's ship?

## Answer: 146

## Clone 3

The playing field for the game "Battleship" is a rectangle $1 \times 248$. Petya places single-cell detectors on this field, after which Vasya places a two-deck ship (rectangle $1 \times 2$). A detector triggers if the cell it is placed on is under the ship. What is the minimum number of detectors Petya should place to uniquely determine the position of Vasya's ship?

## Answer: 164

## Clone 4

The playing field for the game "Battleship" is a rectangle $1 \times 233$. Petya places single-cell detectors on this field, after which Vasya places a two-deck ship (rectangle $1 \times 2$). A detector triggers if the cell it is placed on is under the ship. What is the minimum number of detectors Petya should place to uniquely determine the position of Vasya's ship?

Answer: 154