Mathematical Olympiad Rioplatense

The minimum of $N$ is 201.

In an arbitrary configuration take the minimal rectangle $R$ that contains all black cells. Choose a black cell on every side (there is at least one by minimality) and label these $A,B,C,D$ as in the first figure. Consider the special rectangles $[AB],[BC],[CD],[DA]$ and $[AC]$. Here we write $[XY]$ for the grid rectangle with opposite corner cells $X$ and $Y$ (they determine the rectangle uniquely). Note that if the part of $R$ to the left of rectangle $[AC]$ is ignored, the remainder is covered by $[AB],[BC]$ and $[AC]$. Likewise if the part of $R$ to the right of $[AC]$ is ignored, the remainder is covered by $[CD],[DA]$ and $[AC]$. Hence the entire $R$ is covered by the five rectangles, with certain overlaps. Each of cells $A$ and $C$ belongs to 3 of the 5 rectangles; each of $B$ and $D$ belongs to 2 of them. (There may be other black cells contained in more than one rectangle.) Hence if $x_1,\dots ,x_5$ are the numbers of black cells in the 5 rectangles we obtain $x_1+\cdots +x_5\ge 995+3\cdot 2+2\cdot 2=1005$. This is because the sum counts each black cell except $A,B,C,D$ at least once, each of $B$ and $D$ at least twice, and each of $A$ and $C$ at least thrice. It follows that one of $x_1,\dots ,x_5$ is at least $\frac{1005}{5}=201$. So there is always a special rectangle with at least 201 black cells. Therefore $N\ge 201$ for every configuration.

We tacitly assumed that $A,B,C,D$ are distinct. This can be ensured indeed unless there are no black cells on some two adjacent sides of $R$ except their common corner cell. But then it is clear that $R$ can be covered by at most 3 special rectangles like the ones above, so $N>201$. (We ignore the trivial case where $R$ has a side 1.)

Now we show an example where $N=201$. In the second figure the 999 black squares are inside a big $3k\times 3k$ grid square, with $k>400$. Four groups 1, 2, 3, 4 of 200 black cells each are placed in the corner $k\times k$ squares as shown, in a diagonal-like manner.





Let $X$ and $Y$ be opposite black corner cells of a special rectangle $T$ which contains $m$ black cells. If $X$ and $Y$ are in the same group it is clear that $m\le 200$. If $X$ and $Y$ are in adjacent groups among 1, 2, 3, 4 then $T$ intersects only these two groups. In addition observe that one of the two groups has exactly one cell in $T$ (this is $X$ or $Y$). Thus $m\le 200+1=201$.

Let $X$ and $Y$ be in opposite corner groups, say 1 and 3. Then $T$ does not intersect groups 2 and 4. Moreover $X$ and $Y$ are the only black cells of $T$ from groups 1 and 3. The remaining ones are all in the central part. Hence $m\le 199+2=201$. Finally let one of $X$ and $Y$ be in the central group, say $X$. If $Y$ is also there then $m\le 199$. And if $Y$ is in a corner group then $Y$ is the only black cell of $T$ out of the central part. So $m\le 199+1=200$ which completes the solution.