第6题

考虑一个

2025\times2025

的单位正方形网格。玛蒂尔达希望在网格上放置若干矩形瓷砖(大小可以不同)，使得每块瓷砖的每条边都在网格线上，且每个单位正方形至多被一块瓷砖覆盖。求玛蒂尔达需要放置的最少瓷砖数，使得网格的每一行和每一列都恰好有一个单位正方形未被任何瓷砖覆盖。

第 3/6 步：把未覆盖格子看作一个排列

上一步下一步

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

详细分析

令 $U$ 为 $n$ 个未覆盖格子的集合。按行顺序排列时，它们给出列的一个排列。对两个格子 $u=(u_1,u_2)$ 、 $v=(v_1,v_2)$ ，若 $u_1<v_1$ 且 $u_2<v_2$ ，就定义 $u<v$ ；这是东北方向的偏序。取一个最大反链 $A$ （即递减子序列），再用 Dilworth 定理把 $U$ 划分成 $|A|$ 条链，每条链恰与 $A$ 相交一次。令这份划分中的最长链为 $C$ ，并记 $a=|C|$ 、 $b=|A|$ 。每条链至多含 $a$ 个格子，因此 $ab\ge n$ 。链 $C$ 是递增子序列，而 $A$ 是递减子序列；由于划分中的每条链都与 $A$ 相交一次，二者恰在一个格子 $c$ 处相交。这样有意选择 $A$ , $C$ ，同时得到乘积下界和计数所需的公共交点。