鸽巢原理

本系列前面的每一页都在把方案数算出来。计数之外还有另一类问题：不问共有多少种，只断言某种情形一定出现。鸽巢原理（pigeonhole principle）是其中最简单的一条，它既不指出是哪一屉，也不给出分布，却能推出一批按两条计数原理硬算不出来的结论。

1 · 基本形与加强形

$n > m$ 时 $\lceil n/m \rceil \ge 2$，退回最常见的说法：物品比抽屉多，必有一屉装了不止一件。加强形给出的下界是紧的，均分即达到：写 $n = qm + r$（$0 \le r < m$），让 $r$ 个抽屉各放 $q + 1$ 件、其余各放 $q$ 件，最满的一屉恰好 $\lceil n/m \rceil$ 件。所以这条原理的结论无法再改进，能改进的只有巢的选法。

2 · 巢的设计

原理本身一行就能证完，用起来的全部难度在一步：谁是鸽子、谁是巢。两个经典例子的巢都不是题面上现成的。

从 $1$ 到 $2n$ 中任取 $n + 1$ 个数，必有一个整除另一个。巢取最大奇因子：每个正整数唯一写成 $2^a b$（$b$ 为奇数），而 $1$ 到 $2n$ 之间的奇数只有 $n$ 个，于是 $n + 1$ 个数里必有两个共用同一个 $b$，写成 $2^{a_1} b$ 与 $2^{a_2} b$ 后，指数小的整除指数大的。$n + 1$ 这个数量不能再减：$n + 1, n + 2, \dots, 2n$ 这 $n$ 个数两两不整除，因为其中任意两个的比值都严格落在 $1$ 与 $2$ 之间。

任意 $n$ 个整数中，必有若干连续项之和被 $n$ 整除。鸽子是 $n + 1$ 个前缀和 $S_0 = 0, S_1, \dots, S_n$，巢是模 $n$ 的 $n$ 个余数；两个前缀和同余时相减，$S_j - S_i$ 正好是第 $i + 1$ 项到第 $j$ 项之和，被 $n$ 整除。空前缀 $S_0$ 必须算作一只鸽子，否则只有 $n$ 只鸽子进 $n$ 个巢，结论落空；consecutiveSumDivisible 里那句把余数 $0$ 预先记在下标 $-1$ 上的初始化，兑现的就是这一只鸽子。

3 · Erdős–Szekeres 定理

证法是给每个位置贴一对标号。第 $i$ 位标 $(\text{inc}_i, \text{dec}_i)$，分别是以该位结尾的最长递增子列长度与最长递减子列长度。任取两个位置 $i < j$：若 $a_i \le a_j$，把第 $j$ 位接到第 $i$ 位的递增子列后面，得 $\text{inc}_j > \text{inc}_i$；否则 $a_i > a_j$，同理得 $\text{dec}_j > \text{dec}_i$。两种情形下标号都不相同，故 $mn + 1$ 个标号两两互异。若定理不成立，每个 $\text{inc}$ 至多 $m$、每个 $\text{dec}$ 至多 $n$，全部标号只能落进 $m \times n$ 个格子，装不下 $mn + 1$ 个互异标号。

长度 $mn$ 是紧的。把 $1$ 到 $mn$ 切成 $n$ 段，段内递增而段与段之间整体下降，$m = n = 3$ 时即 $7, 8, 9, 4, 5, 6, 1, 2, 3$。递增子列跨不了段，最长为 $m$；递减子列每段至多取一项，最长为 $n$。定理给的只是下界，随机序列离它很远：$m = n = 4$、长 $17$ 的 $2000$ 个随机排列实测，$1782$ 个同时含长 $5$ 的递增子列与长 $5$ 的递减子列，最长单调子列平均 $6.01$ 项。

把「必有一屉两件」从抽屉搬到图的边上，就得到 Ramsey 型结论：Ramsey 理论里 $R(3, 3) = 6$ 的上界论证，正是对某个顶点的 $5$ 条边按二色分巢，取出不少于 $\lceil 5/2 \rceil = 3$ 条同色边。

4 · 参考文献

1. Pigeonhole principle. Wikipedia. 基本形、加强形与若干标准应用。https://en.wikipedia.org/wiki/Pigeonhole_principle
2. Erdős–Szekeres theorem. Wikipedia. 定理陈述、标号法证明与 $mn$ 紧例。https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem
3. Longest increasing subsequence. Wikipedia. 标号的计算方法与 $O(n \log n)$ 算法。https://en.wikipedia.org/wiki/Longest_increasing_subsequence