# 第六题为什么是 2112

第 01 讲 · 精读文章

2025 年 IMO 的第六题，630 名选手里只有 6 人得满分，那一年到了金牌线的 AI 是 0 分。答案 2112 是怎么来的：一半是构造，一半是 1935 年的 Erdős–Szekeres 定理。

更新：2026-11-20

课上我们把这道题走了一遍，这里把完整的线索留下来，方便你自己推一遍。

## 题目。

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 块）和上面两个下界的例子，课程组用程序穷举核过。

- IMO 2025 官方题目
- IMO 2025 个人成绩
- Evan Chen，IMO 2025 解答笔记
- Erdős–Szekeres 定理（维基百科）

## 引用与相关资料

- [网页版文章](https://intro2llm.pages.dev/lectures/01/notes/why-2112)
- [本讲导读](https://intro2llm.pages.dev/lectures/01)
- [讲义](https://intro2llm.pages.dev/lectures/01/notes)
- [IMO 2025 官方题目](https://www.imo-official.org/assets/documents/problems/2025/2025_eng.pdf)
- [IMO 2025 个人成绩](https://www.imo-official.org/results/individual/year/2025/)
- [Evan Chen，IMO 2025 解答笔记](https://web.evanchen.cc/exams/IMO-2025-notes.pdf)
- [Erdős–Szekeres 定理（维基百科）](https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem)
