Question 100
A grid consists of $n\times n$ points, where $n$ is a positive integer. A sentinel is placed at some of these points. Each sentinel chooses two perpendicular directions from the row and column directions and watches all points in the chosen directions. Each sentinel also watches the point it occupies. Depending on its chosen directions, a sentinel on the boundary may look out into empty space.
For example, in the diagram below showing five sentinels on a $4\times4$ grid, the sentinels at $A,B,C,D,E$ watch $1,3,4,5,7$ points, respectively. Points $D,E$ are watched by one sentinel each, point $C$ by two sentinels, and points $A,B,F$ by three sentinels each.
Part a. Prove that twelve sentinels can be placed on a $4\times4$ grid so that each grid point is watched by at most two sentinels.
Part b. Let $S(n)$ be the greatest number of sentinels that can be placed on an $n\times n$ grid so that each grid point is watched by at most two sentinels. Prove that $3n\le S(n)\le4n$ for every $n\ge3$.
For example, in the diagram below showing five sentinels on a $4\times4$ grid, the sentinels at $A,B,C,D,E$ watch $1,3,4,5,7$ points, respectively. Points $D,E$ are watched by one sentinel each, point $C$ by two sentinels, and points $A,B,F$ by three sentinels each.
Part a. Prove that twelve sentinels can be placed on a $4\times4$ grid so that each grid point is watched by at most two sentinels.
Part b. Let $S(n)$ be the greatest number of sentinels that can be placed on an $n\times n$ grid so that each grid point is watched by at most two sentinels. Prove that $3n\le S(n)\le4n$ for every $n\ge3$.