IT-CESENATICO 2021 Problem 3

A grid consists of $n\times n$ points, with $n\in\mathbb{Z}^+$ . In some of these points is a sentry. Every sentry chooses two directions, one perpendicular to the other (one vertical and the other horizontal) and watches over all the points that are found in the two chosen directions. Each sentry watches over her own point as well and the sentries on the edge of the grid can also watch the vacuum, depending on the directions they have chosen.

For instance, in the figure below, representing a disposition of $5$ sentries in a $4\times 4$ grid, the sentries in $A, B, C, D, E$ watch over $1, 3, 4, 5, 7$ points, respectively; points $D$ and $E$ are watched by one sentry, point $C$ is watched by two sentries, points $A, B$ and $F$ are watched by three sentries.

(a) Prove that we can place $12$ sentries in a $4\times 4$ grid in such a way that every point of the grid is watched by at most two sentries. (b) Let $S(n)$ be the maximum number of sentries we can place on an $n\times n$ grid in such a way that every point of the grid is watched by at most two sentries. Prove that $3n\leq S(n)\leq 4n$ for all $n\geq 3$ .

Attachments: