C4. nicky is drawing kappas in the cells of a square grid. However, he does not want to draw kappas in three consecutive cells (horizontally, vertically, or diagonally). Find all real numbers $d>0$ such that for every positive integer $n$, nic $\kappa$ y can label at least $d n^{2}$ cells of an $n \times n$ square.
(Mihir Singhal and Michael Kural)
Solution by Yevhenii Diomidov, Kada Williams and Mihir Singhal:
The answer is $d \leq \frac{1}{2}$. The construction consists of placing kappas in all squares of the forms $(2 k, 4 \ell),(2 k, 4 \ell+1),(2 k+1,4 \ell+2)$, and $(2 k+1,4 \ell+3)$.

To prove that this is minimal, consider all connected components consisting of squares that contain kappas that are connected via edges. It is easy to see that there are only five different kinds of connected components.

Extend each connected component into a larger figure as shown below: Due to the fact that there are no three kappas in a line and due to the nature of the extensions, one can see that after extension, the interiors of the figures remain disjoint. However, note that the extended area of each figure is at least twice its original area (it is exactly twice except for the 2 by 2 square, for which it is $\frac{9}{4}$ times the original area). Some of the extended regions may fall outside the square, but this is fine since the error is at most $O(n)$.

Thus, Nicky can cover at most $\frac{n^{2}}{2}+O(n)$ of the squares with kappas, which is what we wanted to show.