MathLabs

第6题

考虑一个 2025×20252025\times2025 的单位正方形网格。玛蒂尔达希望在网格上放置若干矩形瓷砖(大小可以不同)，使得每块瓷砖的每条边都在网格线上，且每个单位正方形至多被一块瓷砖覆盖。求玛蒂尔达需要放置的最少瓷砖数，使得网格的每一行和每一列都恰好有一个单位正方形未被任何瓷砖覆盖。
第 5/6 步：每块瓷砖至多带一个字母，由此得到界
上一步下一步
#tiles ≥ C−4 ≥ n+a+b−4 ≥ n+2ab−4 ≥ n+2n−4 (or −3 if LIS, LDS meet)\#\text{tiles}\ \ge\ C-4\ \ge\ n+a+b-4\ \ge\ n+2\sqrt{ab}-4\ \ge\ n+2\sqrt n-4\ (\text{or }-3\text{ if LIS, LDS meet})
详细分析

关键的几何事实是：不同黑格的映射不可能指向同一块瓷砖。因为瓷砖是边平行于坐标轴的矩形；若两个格子使用同一方向，该矩形就必须包含两条相邻边之间的整条轴平行带，而经过 CC 或 AA 中相邻格子的折线会穿过这条带，于是矩形要么覆盖黑格，要么穿过区域边界，二者均不可能。若两个方向不同，相应的两段路径只在 cc 处相交；矩形的凸性再次迫使瓷砖穿过这个交点，因此唯一可能的共同来源只能是格子 cc 本身。故不同黑格的所有映射都指向不同瓷砖。第一次映射中恰有 n−4n-4 次成功：只有第一行、末行、第一列、末列各至多失败一次。(A∪C)∖{c}(A\cup C)\setminus\{c\} 中每个格子再提供一个成功方向，共增加 a+b−2a+b-2 次，而 cc 再提供三个方向。因此瓷砖数至少为 (n−4)+(a+b−2)+3=n+a+b−3(n-4)+(a+b-2)+3=n+a+b-3。由 ab≥nab\ge n 及 AM-GM 不等式，a+b≥2ab≥2n=2ka+b\ge2\sqrt{ab}\ge2\sqrt n=2k，所以瓷砖数至少为 n+2k−3n+2k-3。当 n=2025=452n=2025=45^2 时，下界为 2025+90−3=21122025+90-3=2112，与显式构造相等。