Problem 6

Consider a

2025\times2025

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.

Step 3 of 6: View the uncovered cells as a permutation

Previous step Next step

\text{LIS length }a,\ \text{LDS length }b\ \text{of the uncovered permutation}\ \Longrightarrow\ ab\ge n

Detailed analysis

Let $U$ be the $n$ uncovered cells. In row order they form a permutation of the columns. Order two cells $u=(u_1,u_2)$ and $v=(v_1,v_2)$ by $u<v$ when $u_1<v_1$ and $u_2<v_2$ ; this is the northeast poset. Choose a largest antichain $A$ (a decreasing subsequence), and apply Dilworth's theorem to partition $U$ into $|A|$ chains, each meeting $A$ once. Let $C$ be a longest chain in this partition, and write $a=|C|$ , $b=|A|$ . Then every chain has at most $a$ cells, so $ab\ge n$ . The chain $C$ is an increasing subsequence and $A$ is a decreasing subsequence; they meet in exactly one cell $c$ , because each chain in the Dilworth partition meets $A$ once. This deliberate choice of $A$ and $C$ is what supplies both the product bound and a common crossing cell for the counting argument.