, 2019

The required minimum is $1 + \lceil (n+1)/5 \rceil$ and is achieved by the configuration described in the second block of the proof.

Counting multiplicities, the cells $a$ and $c$ are both covered by three of these special rectangular grid arrays, the cells $b$ and $d$ are both covered by two, and all other red cells are covered by at least one. Letting $r_{[xy]}$ denote the number of red cells in $[xy]$, it follows that $r_{[ab]} + r_{[bc]} + r_{[cd]} + r_{[da]} + r_{[ac]} \ge 3 \cdot 2 + 2 \cdot 2 + (n - 4) = n + 6$. Consequently, $N \ge (n + 6)/5$.

We now describe a configuration of exactly $n$ red cells where $N = 1 + \lceil (n+1)/5 \rceil$. Write $m = \lceil (n+1)/5 \rceil$, so $n = 5m - r$ for some positive integer $r \le 5$, and $N = m + 1$.

Fix an integer $k > 2m$, let $S$ be a $3k \times 3k$ grid square, and subdivide $S$ into nine $k \times k$ grid subsquares.

Let $S_{LL}$ be the lower-left corner $k \times k$ grid subsquare of $S$. Colour red the first $m$ cells along the diagonal upward from the lower-right corner cell of $S_{LL}$.

The ‘min’ and ‘max’ in the next four paragraphs account for the first few cases where $m < r$. Had we assumed $n \ge 20$, it would then have followed that $m \ge r$, and ‘min’ and ‘max’ would have been superfluous.

Next, let $S_{UL}$ be the upper-left corner $k \times k$ grid subsquare of $S$. Colour red the first $\min(m, 4m-r)$ cells along the diagonal upward from the lower-left corner cell of $S_{UL}$.

Let further $S_{UR}$ be the upper-right corner $k \times k$ grid subsquare of $S$. Colour red the first $\min(m, 3m-r)$ cells along the diagonal downward from the upper-left corner cell of $S_{UR}$.

Complete the corner tour by letting $S_{LR}$ be the lower-right corner $k \times k$ grid subsquare of $S$. Colour red the first $\min(m, 2m-r)$ cells along the diagonal downward from the upper-right corner cell of $S_{LR}$.

Finally, let $S_C$ be the central $k \times k$ grid subsquare of $S$, and colour red $\max(0, m-r)$ cells of $S_C$; their exact location is irrelevant.

No other cell whatsoever is coloured red, and it is a routine exercise to check that exactly $n$ cells of the grid paper have been coloured red. Notice that, for each pair of 'adjacent' corner $k \times k$ grid subsquares, $S_{LL}$ and $S_{UL}$, $S_{UL}$ and $S_{UR}$, $S_{UR}$ and $S_{LR}$, and $S_{LR}$ and $S_{LL}$, there are both horizontal and vertical grid lines separating the strings of red cells they contain.

To complete the argument, we show that, if $x$ and $y$ are red cells in this configuration, then $r_{[xy]} \le m + 1$. This is clearly the case if $x$ and $y$ both lie in one of $S_{LL}$, $S_{UL}$, $S_{UR}$, $S_{LR}$ or $S_{C}$, for each of these squares contains at most $m$ red cells.

If $x$ and $y$ lie in 'adjacent' corner $k \times k$ subsquares of $S$, then the red cells in $[xy]$ come from those subsquares alone. In addition, the string of red cells in one of those subsquares has exactly one cell in $[xy]$, namely, $x$ or $y$. Consequently, $r_{[xy]} \le m + 1$. Incidentally, notice that equality holds if, for instance, $x$ is the lower-right corner cell of $S_{LL}$, and $y$ is any red cell in $S_{UL}$; since $n \ge 2$, there is at least one such.

If $x$ and $y$ lie in 'opposite' corner $k \times k$ subsquares of $S$, then they are the only red cells $[xy]$ contains from those subsquares. No red cell in the other two 'opposite' corner $k \times k$ subsquares of $S$ lies in $[xy]$, and the other red cells in $[xy]$ all come from $S_C$ which contains at most $m-1$ such. Consequently, $r_{[xy]} \le 2 + (m-1) = m+1$.

Finally, if one of $x$, $y$ lies in $S_C$, and the other lies in one of the corner $k \times k$ sub-squares of $S$, then the latter cell is the only red cell in $[xy]$ outside $S_C$. Consequently, $r_{[xy]} \le (m-1)+1 = m < m+1$. This ends the proof.