6. On a grid of size $12 \times 12$ squares, there is a ship consisting of eight cells along the perimeter of a $3 \times 3$ square (it is marked in gray in the figure). What is the minimum number of cells that need to be shot at to ensure that the ship is hit at least once?

(Jozef Rajník)

![](https://cdn.mathpix.com/cropped/2024_04_17_cf50a0f208e239784a13g-13.jpg?height=260&width=274&top_left_y=241&top_left_x=1551)
SOLUTION. In the first part of the solution, we will explain why in every $4 \times 4$ square, which is part of the given $12 \times 12$ grid, at least two cells must be hit by a shot.

Consider any such $4 \times 4$ square. Placing a ship as shown in the left upper corner of the square in Fig. 1, a shot at any of the eight cells marked with a dot on the figure will not endanger the ship.

![](https://cdn.mathpix.com/cropped/2024_04_17_cf50a0f208e239784a13g-13.jpg?height=217&width=217&top_left_y=825&top_left_x=925)

Fig. 1

Repeating this reasoning for ships placed in the remaining three corners of the given $4 \times 4$ square, the dot marking will clearly cover all 16 cells of the square. (This can be achieved by rotating Fig. 1 by $90^{\circ}$, $180^{\circ}$, and $270^{\circ}$.)

The statement in the first sentence of our solution is thus proven. We will supplement it (just for interest) with the obvious observation that two well-chosen shots in a $4 \times 4$ square will hit any ship placed in it at least once.

Now we will focus on the entire $12 \times 12$ square. We will divide it into 9 non-overlapping $4 \times 4$ squares in a straightforward manner. As we know, we must shoot at least two cells in each of them, so in the entire $12 \times 12$ square, we must shoot at least $9 \cdot 2 = 18$ cells. Even though we know that two shots are enough for each $4 \times 4$ square, the previous reasoning does not yet prove that 18 shots are enough for the entire $12 \times 12$ square! A ship can be placed such that it does not lie entirely within any of the nine constructed $4 \times 4$ squares.

The mentioned hypothesis about the sufficient number of 18 shots needs to be justified, easiest (by one) example of a suitable choice of 18 hit cells, which can be found by "trial and error." There are many such examples - three of them are given in Fig. 2, which are also somewhat interesting.
![](https://cdn.mathpix.com/cropped/2024_04_17_cf50a0f208e239784a13g-13.jpg?height=490&width=1588&top_left_y=2004&top_left_x=240)

Fig. 2

The shots in the first example are symmetric with respect to both diagonals, in the second and third with respect to the center of the entire square. Additionally, in the first two examples, half of the rows and half of the columns are not hit. In the third example, no two hit cells share a side. Conversely, an example where the hit cells form nine pairs sharing a side can be obtained by a simple modification of the middle figure: the "disturbing" pair of hits in the central $2 \times 2$ square is placed one below the other.

Remark. Let's describe a method to construct a suitable choice of 18 shots relatively easily and how to verify its correctness without having to test the entire $12 \times 12$ grid with a ship.

Call the central cell of a (placed) ship the cell that lies in the center of the $3 \times 3$ square in which the ship is located. It is clear that