Problem:
In a variant of the game of Battleship, Anna places an aircraft carrier (which we can think of as a rectangle) on a grid, either vertically or horizontally, without showing it to Jacopo. Jacopo tries to hit the aircraft carrier, giving each time the coordinates of a square within the grid. If the square he has chosen is among those covered by the aircraft carrier, it is hit, otherwise it is missed. How many shots must Jacopo fire at minimum to be sure of hitting it at least once?
Solution:
The answer is 20. 20 shots are necessary: if Jacopo fires 19 shots or fewer, then there exists at least one row or at least one column targeted by only one shot. That shot divides that row (or column) into two spaces, one of which must be at least 5 squares long, and thus could hide the aircraft carrier.
On the other hand, 20 shots are sufficient for Jacopo to be certain of hitting the aircraft carrier. He could, for example, fire them as in the figure, that is, 10 shots on the main diagonal of the grid, and the others distributed as follows: on the sixth square of the first row, on the seventh of the second, and so on up to the tenth square of the fifth row; on the first of the sixth, on the second of the seventh, and so on up to the fifth square of the tenth row.
