4. On a game board of size $9 \times 9$ squares, there is a ship consisting of eight squares around the perimeter of a $3 \times 3$ square (the ship is colored in the image).

a) How many squares do we need to shoot at to be certain that we will hit the ship at least in two different places? We do not learn about the first hit.

b) Would the same number of shots suffice for a game board of size $11 \times 9$? (Tomáš Bárta)

![](https://cdn.mathpix.com/cropped/2024_04_17_748dea0366bf9998ba58g-6.jpg?height=163&width=168&top_left_y=301&top_left_x=1658)
SOLUTION. a) A $9 \times 9$ square can be divided into 9 smaller $3 \times 3$ squares. We must shoot at least twice into each of these smaller squares, meaning we need at least 18 shots in total. The example in the figure shows that 18 shots are sufficient.

|  |  |  |  |  |  |
| :---: | :---: | :---: | :---: | :---: | :---: |
|  |  |  |  |  |  |
|  | $x$ |  |  | $x$ |  |
| $x$ |  | $X$ | $x$ |  | $x$ |
|  | $x$ |  |  | $x$ |  |
|  |  | $X$ | $x$ |  |  |
|  | $x$ |  |  | $x$ |  |
| $x$ |  | $x$ | $x$ |  | $x$ |
|  | $x$ |  |  | $x$ |  |
|  |  |  |  |  |  |

b) Now assume we have 18 shots available for a $11 \times 9$ game board consisting of 11 rows and 9 columns. Label the rows with numbers 1 to 11.

In any three consecutive rows, three non-overlapping ships can fit, so we need at least 6 shots for these rows. Therefore, we need 6 shots for rows 6, 7, and 8, and also 6 shots for rows 9, 10, and 11. This leaves at most 6 shots for the first five rows. However, rows 1, 2, and 3 must have at least 6 hits, as must rows 3, 4, and 5. This implies that all 6 hits in the first five rows must be in row 3. Therefore, some cell in row 3 will always remain unhit. Place a ship in rows 2, 3, and 4 such that it passes through the selected unhit cell in row 3. The ship will then be hit at most once (since we have excluded hits in rows 2 and 4), as shown in the figure. This proves that 18 shots are insufficient for the $11 \times 9$ game board.

![](https://cdn.mathpix.com/cropped/2024_04_17_748dea0366bf9998ba58g-6.jpg?height=243&width=516&top_left_y=1940&top_left_x=770)