4. Consider the game "Battleship" on a $5 \times 5$ square grid. What is the minimum number of shots needed to guarantee hitting a ship of size $1 \times 4$ cells?
Solution. Obviously, less than five shots are not enough, since at least one shot must be made in each vertical and each horizontal. We will show that five shots are not enough. Indeed, a shot made in the first vertical leaves four consecutive cells on the given horizontal, which means at least one more shot must be made in this horizontal. At least one shot must also be made in the other four horizontals, totaling no less than six shots. Six shots are guaranteed to be enough: