Международная олимпиада 2025, Саншайн-Кост (Квинсленд), Австралия, 2025 год

Рассмотрим сетку размером $2025 \times 2025$ из единичных квадратов. Матильда хочет разместить на сетке несколько прямоугольных плиток, возможно, разных размеров, так, чтобы стороны каждой плитки лежали на линиях сетки, а каждый единичный квадрат был покрыт не более чем одной плиткой.
   Определите минимальное количество плиток, которые Матильде нужно разместить так, чтобы в каждой строке и каждом столбце сетки был ровно один единичный квадрат, не покрытый ни одной плиткой.

Комментарий/решение

Пусть $n = 45$. Мы утверждаем, что ответ для $ n ^ 2 \cdot n^2 $ равен в штучной упаковке ${n ^ 2 + 2n - 3}.$ Построение состоит в том, чтобы разложить плоскость на $ n \cdot n $ квадратов и $ 1 \cdot 1 $ квадратов и центрировать $n^ 2 \cdot n ^ 2$ сетки на $ 1\cdot 1$ или $ n \cdot n$ в зависимости от того, является ли $ n$ нечетным или четным.

Чтобы доказать правильность привязки, рассмотрим "заблокированные" ячейки как перестановку от $ 1$ до $n ^ 2$. Согласно Эрдешу-Секерешу, существует максимально увеличивающаяся подпоследовательность длиной не менее $n$ или максимально уменьшающаяся подпоследовательность длиной не менее $n$. В Б.О.О последовательность увеличивается.

Теперь постройте последовательность, в которой $a \le b$ если $a$ находится слева и выше от $b$. Обратите внимание, что возрастающая подпоследовательность является антицепью в этой последовательности. Теперь возьмем минимальное покрытие цепочки. Поскольку каждая цепочка пересекает самую длинную антицепь не более одного раза, согласно теореме Дилворта, мы можем заключить, что каждая такая цепочка пересекает самую длинную антицепь один раз. Теперь, если максимально увеличивающаяся подпоследовательность имеет длину $x$, по крайней мере, одна из этих цепочек