KöMaL 2019 A752

Let $k$, $s$ and $n$ be positive integers such that $s<(2k+1)^2$, and let $R$ be the set of lattice points $(x,y)$ in the plane, satisfying $1\le x,y\le n$. On the grid $R$ we perform the following procedure. Initially, we colour one point of $R$ green; all other points in $R$ are coloured white. On every move, we choose a square $S$, consisting of ${\color{red}(2k+1)\times(2k+1)}$ lattice points in such a way that the center of $S$ is green and it contains at least $s$ white points; then we re-colour $s$ white points of $S$ to green. We repeat this step as long as there is a suitable square $S$. We say that the number $s$ is $k$-sparse , if there exists a positive real number $C$ such that, for every $n$, for every choice of the initial green point, and for every valid sequence of moves, the total number of green points in the grid cannot exceed $Cn$. Determine the least $k$-sparse positive integer $s$ in terms of $k$.