(given to Marc Coiffier). On a square grid with a side of 1000, what is the maximum number of cells that can be colored black so that one cannot find three black cells, two of which are in the same row and two in the same column?
. We will more generally show that if we replace the grid in the statement with an $m \times n$ grid, the maximum number of squares that can be colored black is $m$ if $n=1$, $n$ if $m=1$, and $m+n-2$ if $m$ and $n$ are both strictly greater than 1. In particular, we find 1998 in the situation described in the statement. The result is obvious if $m$ or $n$ is equal to 1. If $m$ and $n$ are both strictly greater than 1, we can color $m+n-2$ squares by coloring all the squares in one row and one column except the one where they intersect. We will show by induction on $m$ that it is impossible to do better. We can assume $n \geqslant m$. We have already handled the case $m=1$. If $m=2$, if we color two squares in the same row, we cannot color any more squares afterward. The maximum is therefore achieved when we color an entire column, hence the result. Suppose $m>2$, and consider a coloring of the maximum number of squares. Since the maximum is at least $m+n-2$, we have a row that contains at least two black squares. There are no other black squares in the two columns that contain these two squares. Consider the $m-2$ remaining columns. If $m>3$, by the induction hypothesis, they contain at most $m+n-4$ black squares, which concludes the proof. If $m=3$, the remaining column cannot be completely filled, which also concludes the proof.