Team selection test for the 54th IMO

We call a unit square bad if it is covered more than once.

(Bound) Choose an arbitrary row and mark its cells in the columns $r+1$, $r+n+1$, $\dots$, $r+(m-1)n+1$. Consider all $n\times n$ squares having nonempty intersection with the chosen row. Since $mn<mn+r<(m+1)n$, we have at least $m+1$ such squares. Moreover, each such square covers at least one of the marked cells. Since we have $m$ marked cells, we conclude that at least one of them is bad.

Analogously, there is at least one bad unit square among the intersecting squares of this row with columns with numbers $r+2$, $r+n+2$, $\dots$, $r+(m-1)n+2$, and so on. Thus, in this row we have at least $n-r$ bad squares. The same reasoning shows that there are at least $n-r$ bad squares in any of the remaining rows. We repeat the above observation for all remaining $(m+1)r$ columns and conclude that there are at least $n-r$ bad cells in each of them. Therefore, there are at least $$(mn+r)(n-r)+(m+1)r(n-r)=(mn+mr+2r)(n-r)$$ bad cells.

(Construction) Consider the first $n+r$ rows (starting from below) and first $n+r$ columns (starting from the left). Their intersection forms a $(n+r)\times (n+r)$ square $A$. Cover this square using four $n\times n$ squares in its four corners. It is easy to see that the number of bad cells equals $(n+r{)}^2-4r^2$. Consider the $\Gamma$-shaped figure consisting of all cells in the $(2n+r)\times (2n+r)$ square without the cells of $A$. We cover all cells in this figure by five $n\times n$ squares (two squares in each of the two rectangular parts and one square in the right upper corner) and leave $n^2-r^2$ bad cells. The same procedure is applied $m-1$ times for all $\Gamma$-shaped figures of width $n$. The number of bad cells equals $$(n+r{)}^2-4r^2+(m-1)(n^2-r^2)=(mn+mr+2r)(n-r).$$