SELECTION TESTS FOR THE 2019 BMO AND IMO

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.