MathLabs

第6题

考虑一个 2025×20252025\times2025 的单位正方形网格。玛蒂尔达希望在网格上放置若干矩形瓷砖(大小可以不同),使得每块瓷砖的每条边都在网格线上,且每个单位正方形至多被一块瓷砖覆盖。求玛蒂尔达需要放置的最少瓷砖数,使得网格的每一行和每一列都恰好有一个单位正方形未被任何瓷砖覆盖。
第 4/6 步:标记四个象限并统计写下的字母数
C=n+a+b (or n+a+b+1 if the LIS and LDS meet)C=n+a+b\ (\text{or}\ n+a+b+1\ \text{if the LIS and LDS meet})
详细分析

沿 CC 中相邻的格子画折线,将其首格连接到西南角、末格连接到东北角。对 AA 也画同样的折线,将首格和末格分别连接到西北角和东南角。由于 CC 是链而 AA 是反链,两条折线除公共格 cc 外不相交,并把棋盘分成北、东、南、西四个区域。对北区每个黑格,在其正上方的格子写 NN;南区写在正下方为 SS;西区写在左侧为 WW;东区写在右侧为 EE。折线上的格子写下所有相邻区域对应的字母。由于 cc 同时在两条折线上,它收到全部四个字母;A∪CA\cup C 中其他每个格子收到两个字母,而 A∪CA\cup C 之外的每个格子收到一个字母。因此字母总数为 C=n+a+b+1C=n+a+b+1(这里的 CC 表示字母数,不是链)。