Problem: Consider a $2025 \times 2025$ grid of unit squares.
Matilda wishes to place on the grid some rectangular tiles, possibly of different sizes,
such that each side of every tile lies on a grid line
and every unit square is covered by at most one tile.

Determine the minimum number of tiles Matilda needs to place
so that each row and each column of the grid has exactly one unit square
that is not covered by any tile.

\end{enumerate}

Solution: The answer is $2112 = 2025 + 2 \cdot 45 - 3$.
In general, the answer turns out to be $\left\lceil n + 2 \sqrt n - 3 \right\rceil$,
but when $n$ is not a perfect square the solution is more complicated.

\begin{remark*}
  The 2017 Romanian Masters in Math asked the same problem where the tiles
  are replaced by \emph{sticks}, i.e.\ $1 \times k$ tiles.
  The answer to that problem is completely different and as far as I know
  there is no connection at all to the present IMO problem.
\end{remark*}

\paragraph{Construction.}
We show a general construction when $n = k^2$ illustrated below for $k=5$;
it generalizes readily.
There are a total of $(k-1)^2$ tiles which are $k \times k$ squares and another
$4(k-1)$ tiles on the boundary, giving a total of
\[ (k-1)^2 + 4(k-1) = k^2 + 2k - 3 \]
tiles as promised.

\begin{center}
\begin{asy}
  unitsize(0.4cm);
  int n = 5;
  int N = n*n;
  path outer = box((0,0),(N,N));
  pair P(int i, int j) {
    return (n*i+j,n*j-i+n-1);
  }
  for (int i=0; i<N; ++i) {
    draw((0,i)--(N,i), dotted);
    draw((i,0)--(i,N), dotted);
  }
  for (int i=-n; i<2*n; ++i) {
  for (int j=-n; j<2*n; ++j) {
    fill(shift(P(i,j))*unitsquare);
    filldraw(shift(P(i,j)+(1,0))*scale(n)*unitsquare, opacity(0.2)+yellow, red+1.2);
  }
  }
  clip(outer);
  draw(outer, blue+1.8);
\end{asy}
\end{center}

\begin{remark*}
  Ironically, the construction obtaining the answer
  in the floor pattern at Sunshine Coast airport,
  the closest airport to the site of the exam.
  See \href{https://i0.wp.com/havewheelchairwilltravel.net/wp-content/uploads/2019/10/IMG_6815.jpg}{this image}
  or \href{https://stea.com.au/wp-content/uploads/2020/12/sunshine-coast-airport-design-stea-architectural-projects-20.jpg}{this image}.
\end{remark*}

\paragraph{Bound.}
There are several approaches (all hard), but
the shortest proof seems to be the following one that exploits
the Erd\"{o}s-Szekeres theorem; it is Solution 6 in the shortlist.
The theorem being quoted is:
\begin{theorem*}
  [Erd\"{o}s-Szekeres]
  Let $n \ge 1$ be an integer.
  Given a permutation of $(1, \dots, n)$,
  if a \emph{longest increasing subsequence (LIS)} has length $a$ and
  a \emph{longest decreasing subsequence (LDS)} has length $b$, then $ab \ge n$.
\end{theorem*}
This is a stronger version of the theorem compared to another version
which instead just asserts that $\max(a,b) \ge \sqrt n$.

To apply this to the present problem, take the $n$ uncovered squares
which we henceforth call ``black'' as a permutation.
Then consider both an LIS of length $a$ and an LDS of length $b$.
We do the following artistic illustration:
\begin{itemize}
  \ii Draw the LIS as a broken line,
  then connect it to the southwest and northwest corner of the board.

  \ii Similarly, draw the LDS as a broken line,
  then connect it to the northwest and southeast corner of the board.

  \ii These two steps partition the board into four quadrants,
  which we call north, east, south, west.

  \ii For each black cell in the north quadrant,
  write an $\mathbf{N}$ in the cell above it
  (for the cell in the first row, this will be off the board).
  Do the same for $\mathbf{E}$ (east), $\mathbf{S}$ (south), $\mathbf{W}$ (west).

  \ii Some black cells are in multiple quadrants (i.e.\ part of the LIS/LDS).
  Write all letters in that case.
\end{itemize}
The figure below shows two examples of the process,
each for a board with $n=9$, for two choices of LIS and LDS.
The cells in the LIS and LDS have been marked with green circles,
and the boundaries of the quadrants are drawn in green lines.
In the left example, the LIS and LDS have a black square in common
(that cell has all four directions labeled).
In the right example, the LIS and do not have common squares.

\begin{center}
\begin{asy}
  unitsize(0.65cm);
  int n = 3;
  int N = n*n;
  path outer = box((0,0),(N,N));
  pair P(int i, int j) {
    return (n*i+j,n*j-i+n-1);
  }
  pair Q(int i, int j) {
    return P(i,j)+(0.5,0.5);
  }
  for (int i=0; i<N; ++i) {
    draw((0,i)--(N,i), dotted);
    draw((i,0)--(i,N), dotted);
  }
  for (int i=-n; i<2*n; ++i) {
  for (int j=-n; j<2*n; ++j) {
    fill(shift(P(i,j))*unitsquare);
    filldraw(shift(P(i,j)+(1,0))*scale(n)*unitsquare, opacity(0.2)+yellow, red+1.2);
  }
  }
  clip(outer);
  draw(outer, blue+1.8);
  draw((0,0)--Q(0,0)--Q(2,1)--Q(2,2)--(N,N), deepgreen+1.5);
  draw((0,N)--Q(0,2)--Q(1,2)--Q(2,1)--(N,0), deepgreen+1.5);
  real r = 0.4;
  filldraw(circle(Q(0,0), r), lightgreen, deepgreen+1.5);
  filldraw(circle(Q(2,1), r), lightgreen, deepgreen+1.5);
  filldraw(circle(Q(2,2), r), lightgreen, deepgreen+1.5);
  filldraw(circle(Q(0,2), r), lightgreen, deepgreen+1.5);
  filldraw(circle(Q(1,2), r), lightgreen, deepgreen+1.5);

  label("$\mathbf{N}$", (2.5,9.5));
  label("$\mathbf{N}$", (5.5,8.5));
  label("$\mathbf{N}$", (8.5,7.5));
  label("$\mathbf{N}$", (7.5,4.5));

  label("$\mathbf{W}$", (1.5,8.5));
  label("$\mathbf{W}$", (0.5,5.5));
  label("$\mathbf{W}$", (-0.5,2.5));
  label("$\mathbf{W}$", (4.5,7.5));
  label("$\mathbf{W}$", (3.5,4.5));
  label("$\mathbf{W}$", (6.5,3.5));

  label("$\mathbf{E}$", (9.5,6.5));
  label("$\mathbf{E}$", (8.5,3.5));

  label("$\mathbf{S}$", (7.5,2.5));
  label("$\mathbf{S}$", (0.5,1.5));
  label("$\mathbf{S}$", (3.5,0.5));
  label("$\mathbf{S}$", (6.5,-0.5));
\end{asy}
\qquad
\begin{asy}
  unitsize(0.65cm);
  int n = 3;
  int N = n*n;
  path outer = box((0,0),(N,N));
  pair P(int i, int j) {
    return (n*i+j,n*j-i+n-1);
  }
  pair Q(int i, int j) {
    return P(i,j)+(0.5,0.5);
  }
  for (int i=0; i<N; ++i) {
    draw((0,i)--(N,i), dotted);
    draw((i,0)--(i,N), dotted);
  }
  for (int i=-n; i<2*n; ++i) {
  for (int j=-n; j<2*n; ++j) {
    fill(shift(P(i,j))*unitsquare);
    filldraw(shift(P(i,j)+(1,0))*scale(n)*unitsquare, opacity(0.2)+yellow, red+1.2);
  }
  }
  clip(outer);
  draw(outer, blue+1.8);
  draw((0,0)--Q(0,0)--Q(0,1)--Q(2,2)--(N,N), deepgreen+1.5);
  draw((0,N)--Q(0,2)--Q(1,1)--Q(2,1)--(N,0), deepgreen+1.5);
  real r = 0.4;
  filldraw(circle(Q(0,0), r), lightgreen, deepgreen+1.5);
  filldraw(circle(Q(0,1), r), lightgreen, deepgreen+1.5);
  filldraw(circle(Q(2,2), r), lightgreen, deepgreen+1.5);
  filldraw(circle(Q(0,2), r), lightgreen, deepgreen+1.5);
  filldraw(circle(Q(1,1), r), lightgreen, deepgreen+1.5);
  filldraw(circle(Q(2,1), r), lightgreen, deepgreen+1.5);

  label("$\mathbf{N}$", (2.5,9.5));
  label("$\mathbf{N}$", (5.5,8.5));
  label("$\mathbf{N}$", (8.5,7.5));

  label("$\mathbf{W}$", (1.5,8.5));
  label("$\mathbf{W}$", (0.5,5.5));
  label("$\mathbf{W}$", (-0.5,2.5));

  label("$\mathbf{E}$", (9.5,6.5));
  label("$\mathbf{E}$", (8.5,3.5));
  label("$\mathbf{E}$", (5.5,4.5));

  label("$\mathbf{S}$", (7.5,2.5));
  label("$\mathbf{S}$", (1.5,4.5));
  label("$\mathbf{S}$", (0.5,1.5));
  label("$\mathbf{S}$", (3.5,0.5));
  label("$\mathbf{S}$", (4.5,3.5));
  label("$\mathbf{S}$", (6.5,-0.5));
\end{asy}
\end{center}

We observe that:
\begin{claim*}
  In this algorithm, the total number of letters written is exactly
  \[
    C \coloneq \begin{cases}
      n + a + b + 1 & \text{if the LIS and LDS intersect} \\
      n + a + b & \text{otherwise}.
    \end{cases}
  \]
\end{claim*}
\begin{proof}
  This is obvious. Each black square contributes at least one letter.
  Each black square on exactly one of the LIS and LDS contributes one extra letter.
  And a black square on both contributes $4$ letters instead of $1+1+1$.
\end{proof}
Note by AM-GM we have $a + b \ge 2 \sqrt{ab} \ge 2 \sqrt n$,
so we have a bound of
\[ C \ge n + 2 \sqrt n + \eps \quad\text{where}\quad
  \eps \coloneq \begin{cases}
    1 & \text{if the LIS and LDS intersect} \\
    0 & \text{otherwise}.
  \end{cases} \]

To relate $C$ to the number of tiles,
the critical claim is the following, which is by construction:
\begin{claim*}
  None of Matilda's tiles can have more than one letter written in any cell.
\end{claim*}
\begin{proof}
  This follows from the construction.
\end{proof}

We split into two cases based on $\eps$.
\begin{itemize}
  \ii When $\eps = 1$, at most four letters go off the grid
  (one for each direction), the number of tiles is at least $C - 4 \ge n + 2 \sqrt n - 3$.
  \ii Suppose $\eps = 0$.
  Then $C - 4 \ge n + 2 \sqrt n - 4$.
  However, we make the additional observation here that the tile
  where the LIS and LDS meet has no letters on it either;
  hence there are at least $1 + (C-4) \ge n + 2 \sqrt n - 3$ tiles.
\end{itemize}

\begin{remark*}
  \href{https://aops.com/community/p35341804}{USJL} mentions that when $n = ab$,
  it is in fact always possible to guarantee $\eps = 1$.
  Moreover, when $a \neq b$, the AM-GM inequality is strict.
  This gives a way to avoid the additional observation needed for $\eps = 0$ above.
\end{remark*}