4. consider a $7 \times 7$ field that is divided into 49 unit squares. Into this field we want to place tiles in the shape of a Swiss cross, consisting of 5 unit squares. The edges of the crosses should lie on the lines of the field. Determine the smallest possible number of squares that must be marked on the field so that each cross, no matter where it is placed on the field, covers at least one marked square.

## Solution
Insert coordinates. It is easy to see that each cross represents one of the 7 squares

$$
(2,5),(3,2),(3,3),(4,6),(5,4),(6,2),(6,5)
$$

covered. This shows that 7 markings are sufficient. We now show that 7 marks are necessary. Assume not. The crosses with centers

$$
(2,2),(2,6),(3,4),(5,2),(5,6),(6,4)
$$

are disjoint, so each of these crosses must cover a marked field. Therefore, five markings are not enough. Assume that exactly 6 squares are marked. Then
each of the 6 crosses in (1) covers exactly one mark. Therefore, the squares $(1,1),(1,3),(1,4)$ and $(1,6)$ cannot be marked. By rotating and mirroring the cross arrangement (1) and analogous arguments, it follows that no square can be marked at the edge of the field. It also follows that the squares $(3,4),(4,3),(4,5)$ and $(6,4)$ cannot be marked. Consequently, $(4,4)$ is marked. The 5 crosses with center points

$$
(2,6),(3,3),(5,2),(5,6),(6,4)
$$

are disjoint and none contains the central square. Therefore, each covers a marked square and in particular the squares $(2,2),(2,4)$ and $(3,5)$ cannot be marked. If we replace the cross $(3,3)$ in (2) with $(2,3)$, we see analogously that the squares $(3,2)$ and $(3,4)$ cannot be marked. For reasons of symmetry, it now follows as before that not a single square other than $(4,4)$ can be marked, contradiction.