课上我们把这道题走了一遍,这里把完整的线索留下来,方便你自己推一遍。
题目。
2025×2025 的方格表里放长方形的砖:沿格线放,互不重叠,大小随意。要求每一行、每一列恰好留一个空格。最少放几块?答案是 2112。说清楚这个答案要两半:先构造出 2112 块的铺法(上界),再证明不可能更少(下界)。
前一半:构造(上界)。
先看小的。4×4 的方格,把空格排在对角线上要 6 块;把空格挪成第 1 到 4 行分别在第 2、4、1、3 列,中间正好让出一块 2×2,外圈 4 块,一共 5 块。9×9 照同样的想法:空格在第 1 到 9 行分别放在第 3、6、9、2、5、8、1、4、7 列,也就是分成三段,段内一行比一行往右跳 3 格,下一段整体往左挪一格。空格之间让出 4 块 3×3 的方砖,外圈 8 块,一共 12 块。一般地,边长是 k² 时,这样排能让出 (k−1)² 块 k×k 的方砖,外圈再用 4(k−1) 块,一共 k²+2k−3 块。2025=45²,所以 44²+4×44=1936+176=2112 块可行。
后一半:下界(不能更少)。
每行每列恰好一个空格,所以从上往下读每一行空格在第几列,得到 1 到 N 的一个排列。排列里从左到右挑出几个数、一个比一个大,叫上升子列;最长的上升子列长 a。一个比一个小的叫下降子列,最长的长 b。在棋盘上,上升子列是一串往右下排的空格,下降子列是一串往左下排的空格。
第一步是一条引理:不管怎么摆,砖数不少于 N+a+b−3。它的证明提纲是这样的:挑一条最长的上升子列和一条最长的下降子列,各连成折线、接到棋盘的两个对角,棋盘被分成上、右、下、左四个区域;每个空格朝它所在区域的方向,在相邻的格子里做一个标记,落在子列上的空格多做标记;可以证明同一块砖里最多一个标记,而最多有 4 个标记落在棋盘外,数下来就是这个式子。完整的论证见文末的笔记。你可以拿小棋盘验一验:对角线 1 2 3 4 是 a=4、b=1,下界是 4+4+1−3=6;2 4 1 3 是 a=2、b=2,下界是 5;都恰好等于实际的最少块数。
第二步:想省砖,a 和 b 都要小。可它们不能同时都小。1935 年的 Erdős–Szekeres 定理说:a×b ≥ N。证明只要抽屉原理。给排列里的每一项配一个数对(下面叫它的“标签”):以它结尾的最长上升子列有多长,以它结尾的最长下降子列有多长。任取两个数,后面的那个如果比前面的大,就能接在前面那个的上升子列后面,第一个标签至少多 1;如果比前面的小,第二个标签至少多 1。所以任何两个数的标签都不同。标签的第一个数最大是 a,第二个最大是 b,最多 a×b 种;N 个数要 N 种不同的标签,于是 a×b ≥ N。
第三步是基本不等式:a+b ≥ 2√(ab) ≥ 2√N。N=2025 时 a+b ≥ 90,所以砖数 ≥ 2025+90−3=2112。
上界 2112,下界 2112,所以最少恰好是 2112 块。顺带一提,9×9 的那个排列 3 6 9 2 5 8 1 4 7,九个数的标签正好是 (1,1) 到 (3,3) 这九对,一对不多一对不少:这个构造让最长上升子列和最长下降子列都取到了可能的最小长度。
这道题难在哪。
两半都要。前一半要看出一个没见过的构造;后一半要想到,铺砖的问题里藏着一条讲排列的定理。2025 年达到金牌线的 AI 做对了前五题,在这一题上是 0 分。一年以后的事,见第 1 讲。
想自己再走一步。
边长不是平方数时答案是多少?5×5 是 7 块,你能摆出来吗?能证明 6 块不行吗?
出处
IMO 2025 官方题目;IMO 2025 个人成绩;Evan Chen 的 IMO 2025 解答笔记(构造、下界的证明);维基百科 Erdős–Szekeres theorem。小棋盘的块数(3×3 是 4 块,4×4 是 5 块,5×5 是 7 块)和上面两个下界的例子,课程组用程序穷举核过。