Problem 6. Consider a  2025x2025 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.

Solution 1

Solution 1
Call all $n^2$ squares that we will skip be Hiura.
We will solves for $n^2 \times n^2$ grid. The answer is $n^2 + 2n - 3$.
Label the coordinates on the square grid, with the bottom-left square be the origin.
We call a sequence of points be "uphill path", if $(a_1, b_1) \to (a_2, b_2) \to \dots \to (a_k, b_k)$, then $a_i < a_j$, $b_i < b_j$, for all $i < j$. Similarly with "downhill path".

$\textbf{Claim.}$ From $n^2$ Hiura squares, there exists an uphill path with length $a$, and a downhill path with length $b$ such that $a + b \geq 2n$.

$\textbf{Proof.}$ Consider the "weight" of the $n^2$ Hiura squares be its $y$-coordinate. The claim become this following problem. Given a sequence $a_1, a_2, \dots, a_{n^2}$. Then, there exist a pair of an uphill path and a downhill path which are the subsets of $a_1, a_2, \dots, a_{n^2}$ (with the same order), have $a$ and $b$ elements, res, so that $ab \geq n^2$. Assume that the $a_{\max} = t$. We will need to prove that $b \geq n^2 / t$. Then some using of Dirichlet principle give us the desired result. And the equation $a + b = 2n$ occurs iff $a = b = n$, from this we can show that these two subsequences share a common element.

Back to our main problems, we shows that there exist an uphill path and a downhill path satisfy that, then these two lines divide the grid into 4 parts (with the color of top, left, bottom, right be red, green, purple, black), as the figure shown.

For each unit square from $n^2$ Hiura squares, we label its edge depend on which parts it is in (if a unit square lies on $> 1$ parts, we label all of its edges which share a same direction with the parts). Then, we can see that, each rectangle can cover at most 1 edge.

Now, our works is just count the minimal number of edges need to be cover.
There are at most 4 edges don't need to be cover among all labeled edges (that's the edge belong to the boundary of the grid), and there are at least $a + b$ squares have 2 labeled edges, therefore the minimal number of edges need to be cover is
 
\[ n^2 + a + b - 4 \geq n^2 + 2n + 1 - 4 = n^2 + 2n - 3, \]
if the equation doesn't occur.

And if the uphill path and downhill path have a common square, then all of its edge is labeled.
Then, the minimal number of edges need to be cover is

\[ n^2 + 2n - 2 + 3 - 4 = n^2 + 2n - 3, \]
as desired.

For the construction, we do the same with the case $n^2 = 9$ below.
 
 
Solution 2 Solution2
Solution 3 Solution3
Solution 4 Solution4