进入 Stage 3：容斥原理与鸽笼原理。这是你”补短”最关键的一站——容斥偏计算（你的强项），但鸽笼是纯存在性证明、且是 USAMO 最高频武器（你的弱项）。先用 Python 核一下我下面要用的几个关键数值与定理（错排数、满射数、Erdős–Szekeres 的紧性），确保教学例子零误差。数值与定理全部验证通过（错排 $D_{4} = 9, D_{5} = 44$ 、满射 $4 \to 3 = 36$ 、子集和 $1023 > 936$ 、Erdős–Szekeres 在 $n = 2$ 时 5 项必有长度 3 单调子列且 4 项可避免）。下面正式开讲。

Stage 3：容斥原理与鸽笼原理

老规矩，先给内核。这一站表面是两个互不相干的工具，其实有一条共同主线：当你没法”直接数 / 直接构造”时，怎么用计数把答案逼出来。

容斥：每个元素都该恰好被数一次。当集合重叠、直接数会重复时，用交错的”多减少加”把重复精确扣平。
鸽笼：用一个计数不等式 + 反证，逼出”某个东西必然存在”——不构造它，只证明它躲不掉。
两者都长在你已有的根上：容斥的核心恒等式 $\sum_{k} (- 1)^{k} (k m) = 0$ ，正是你 Stage 1 用对合证过的那一个；而容斥的本质就是你数论里莫比乌斯反演的特例。鸽笼则和你数论的”按余数分类”是同一套。

一、容斥原理 (Inclusion–Exclusion)

1.1 从两三个集合的直觉

两个集合，并集会把交集多算一次，减掉即可： $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣.$ 三个集合，减完两两交集后，三重交集被减得太多（它在三个 $∣ A \cap B ∣$ 里各被减一次，原本只被加三次），要加回来： $∣ A \cup B \cup C ∣ = \sum ∣ A ∣ - \sum ∣ A \cap B ∣ + ∣ A \cap B \cap C ∣.$

1.2 一般公式（两种形式，第二种更常用）

并集形式： $⋃_{i = 1}^{n} A_{i} = \sum_{\emptyset \neq = S \subseteq [n]} (- 1)^{∣ S ∣ + 1} ⋂_{i \in S} A_{i} .$

“一个性质都不满足”形式（解题时最常用——很多题问的是”没有任何坏性质”的对象个数）：把每个 $A_{i}$ 看成”具有第 $i$ 种坏性质”，全集为 $U$ ，则 $\overline{A_{1}} \cap \dots \cap \overline{A_{n}} = \sum_{S \subseteq [n]} (- 1)^{∣ S ∣} ⋂_{i \in S} A_{i} = ∣ U ∣ - \sum ∣ A_{i} ∣ + \sum ∣ A_{i} \cap A_{j} ∣ - \dots$

1.3 ★ 为什么成立（核心，且直接用到 Stage 1）

只看单个元素 $x$ 对右边的贡献。设 $x$ 恰好落在 $m$ 个集合里（ $m \geq 1$ ）。那么 $x$ 出现在 $(j m)$ 个 $j$ -重交集中，每个带符号 $(- 1)^{j + 1}$ （并集形式）。 $x$ 的总贡献是 $\sum_{j = 1}^{m} (- 1)^{j + 1} (j m) = - [\sum_{j = 0}^{m} (- 1)^{j} (j m) - 1] = - [, 0 - 1,] = 1.$ 每个元素恰好被数一次，所以公式给出的就是并集的真实大小。∎

注意那个 $\sum_{j = 0}^{m} (- 1)^{j} (j m) = 0$ ——这正是你在 Stage 1 P5(b) 用”toggle 对合”证明的恒等式。换句话说，容斥之所以成立，底层就是你早已亲手证过的那个偶子集 = 奇子集。这就是我一直说的”工具是连通的”。

1.4 应用一：错排 (Derangements)

错排 = 没有任何不动点的排列（ $π (i) \neq = i$ 对所有 $i$ ）。令 $A_{i} =$ “固定 $i$ 的排列”，要求的是”一个都不固定”。关键： $⋂_{i \in S} A_{i} = (n - ∣ S ∣)!$ （把 $S$ 里的位置钉死，其余自由排）。代入容斥形式： $D_{n} = \sum_{k = 0}^{n} (- 1)^{k} (k n) (n - k)! = n! \sum_{k = 0}^{n} \frac{( - 1 ) ^{k}}{k !} .$ 于是 $D_{n} \approx n! / e$ ——随机排列”无人对号入座”的概率趋于 $1/ e \approx 0.368$ ，这个反直觉的常数就是这么来的。数值： $D_{1}, \dots, D_{5} = 0, 1, 2, 9, 44$ （已验证）。

递推（组合证法，练你写论证）： $D_{n} = (n - 1) (D_{n - 1} + D_{n - 2})$ 。设 $π (1) = k \neq = 1$ （ $k$ 有 $n - 1$ 种）。两种互斥情形：① $π (k) = 1$ （1 与 $k$ 互换），其余 $n - 2$ 个错排， $D_{n - 2}$ 种；② $π (k) \neq = 1$ ，此时”位置 $k$ 不能放 $1$ “恰好把它变成 $n - 1$ 个元素的一个错排， $D_{n - 1}$ 种。相加再乘 $n - 1$ 即得。∎

1.5 应用二：满射计数 (Surjections)

从 $n$ 元集映满到 $k$ 元集的满射数。令 $A_{i} =$ “值域漏掉第 $i$ 个元素的函数”， $⋂_{i \in S} A_{i} = (k - ∣ S ∣)^{n}$ ，容斥得 $#\text{满射}=\sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n.$ 例： $4 \to 3$ 的满射 $= 3^{4} - 3 \cdot 2^{4} + 3 \cdot 1^{4} = 81 - 48 + 3 = 36$ （已验证）。它等于 $k!, S (n, k)$ ，其中 $S (n, k)$ 是第二类斯特林数——这条线会接到后面”特殊数列”那一站。

1.6 应用三：欧拉函数 (Euler’s totient)——直接接你的数论

设 $n = p_{1}^{a_{1}} \dots p_{r}^{a_{r}}$ ，要数 $[1, n]$ 中与 $n$ 互质的数。令 $A_{i} =$ ” $p_{i}$ 的倍数”，互质 = 不在任何 $A_{i}$ 里。因为 $⋂_{i \in S} A_{i} = n / \prod_{i \in S} p_{i}$ ，容斥直接给出你早就背熟的公式： $φ (n) = n \prod_{i = 1}^{r} (1 - \frac{1}{p _{i}}) .$ 你数论里当公式记的 $φ$ ，在这里是被容斥”推导”出来的。 更进一步，它等价于 $φ (n) = \sum_{d ∣ n} μ (d) \frac{n}{d}$ ——

1.7 容斥 = 莫比乌斯反演（点到为止）

你数论 Stage 11 用过的莫比乌斯反演 $μ$ ，本质上就是容斥在”子集格 / 整除格”上的推广：交错的 $(- 1)^{∣ S ∣}$ 正是布尔格上的莫比乌斯函数。完整的偏序集莫比乌斯反演留到后面”偏序集”那一站，这里你先记住这条连接——容斥不是新东西，是你数论反演的组合版本。

二、★ 鸽笼原理 (Pigeonhole)——USAMO 最高频武器

2.1 基本与加强

基本： $n + 1$ 只鸽子进 $n$ 个笼，必有一笼 $\geq 2$ 只。
加强： $N$ 只鸽子进 $n$ 个笼，必有一笼 $\geq ⌈ N / n ⌉$ 只。
证明就一行反证（一个计数不等式）：若每笼都 $\leq ⌈ N / n ⌉ - 1$ ，则总数 $\leq n (⌈ N / n ⌉ - 1) < N$ ，矛盾。

请把这句话刻进脑子：鸽笼是一个”不构造、只证存在”的工具。 它不告诉你哪只鸽子、哪个笼，只保证”逃不掉”——这正是 USAMO 组合的灵魂（“证明某种东西必然存在 / 必然出现”）。

2.2 平均值原理 (Averaging Principle)

鸽笼的连续版：若一组数的平均是 $μ$ ，则必有一个 $\geq μ$ ，也必有一个 $\leq μ$ 。 很多”存在一个不小于平均/不大于平均的对象”的题靠它一句话解决。鸽笼其实就是把它用在”计数”上。

2.3 精髓：难的从来不是原理，是”设鸽子、设笼子”

鸽笼原理本身三岁小孩都懂。USAMO 考的全部难度，集中在那个创造性的一步：把问题里的什么当鸽子、什么当笼子，使得”同笼”恰好翻译成你想要的结论。 下面用五个递进的例子把这个”设法”打透。

2.4 例子（从模板到压轴）

例 A（热身，立模板）： 任意 13 人中必有两人同月生。鸽子 = 13 人，笼子 = 12 个月。 $13 > 12$ ，得证。——平凡，但请注意这个”鸽子 / 笼子 / 同笼含义”的三段式。

例 B（接你的数论）： 任意 $n + 1$ 个整数中，必有两个之差被 $n$ 整除。鸽子 = 这 $n + 1$ 个数，笼子 = 模 $n$ 的 $n$ 个余数。两数同余 $\Rightarrow$ 差被 $n$ 整除。

例 C（子集和，IMO 味，威力初现）： 任取 10 个不同的两位数（ $10 \sim 99$ ），必存在两个不相交的非空子集，元素和相等。

鸽子：这 10 个数的全体非空子集，共 $2^{10} - 1 = 1023$ 个。
笼子：可能的”子集和”。任何子集和 $\geq 10$ （最小元素）， $\leq 90 + 91 + \dots + 99 = 945$ ，故至多 $945 - 10 + 1 = 936$ 个取值。
$1023 > 936$ ，鸽笼 $\Rightarrow$ 存在两个不同子集 $X \neq = Y$ 和相等。
去掉公共部分： $X ∖ Y$ 与 $Y ∖ X$ 仍和相等（两边各减 $X \cap Y$ 的和）、且不相交；因元素全为正，谁也不可能是对方子集，故两边都非空。∎
体会一下：直接构造这两个子集几乎不可能，但鸽笼一句话保证它们存在。

例 D（空间分割）： 单位正方形内任取 5 点，必有两点距离 $\leq \frac{2}{2}$ 。把正方形切成 4 个边长 $\frac{1}{2}$ 的小方格（笼子），5 点（鸽子） $> 4$ ，必有两点同格，距离 $\leq$ 小方格对角线 $\frac{2}{2}$ 。——“把空间切成区域当笼子”是几何组合的常用招。

例 E（Erdős–Szekeres，压轴，USAMO/Putnam 级）： 任何 $n^{2} + 1$ 个不同实数的序列，必含长度 $n + 1$ 的单调子列（递增或递减）。

巧妙的设法：给第 $i$ 项 $a_{i}$ 贴标签 $(x_{i}, y_{i})$ ，其中 $x_{i} =$ 以 $a_{i}$ 结尾的最长递增子列长度， $y_{i} =$ 以 $a_{i}$ 结尾的最长递减子列长度。
反设没有长度 $n + 1$ 的单调子列，则所有 $x_{i}, y_{i} \in 1, \dots, n$ ，标签（笼子）至多 $n^{2}$ 种。
标签两两不同：对 $i < j$ ，若 $a_{i} < a_{j}$ 则 $x_{j} \geq x_{i} + 1$ （把 $a_{j}$ 接在后面）， $x$ 坐标不同；若 $a_{i} > a_{j}$ 则 $y_{j} \geq y_{i} + 1$ ， $y$ 坐标不同。
$n^{2} + 1$ 只鸽子、 $\leq n^{2}$ 个笼 $\Rightarrow$ 矛盾。故必有长度 $n + 1$ 的单调子列。∎
紧性： $n^{2}$ 项可以避免（如 $n = 2$ 时序列 $2, 1, 4, 3$ 最长单调子列只有 2，已验证）。
这就是把”鸽子 / 笼子”设得极巧的范本——原理还是那个原理，全部功夫在”标签”的设计上。

2.5 鸽笼证明的 5 步模板（专治你的弱项）

你 Stage 1 的问题是”看出来了但不写”。鸽笼题请强制自己写满这五步，把”我会”变成”我证明了”：

设鸽子：明确对象是什么，共 $N$ 个。

设笼子：明确分类是什么，共 $n$ 个。

验不等式：写出 $N > n$ （或 $N > k n$ ）。

援引鸽笼：故某笼 $\geq 2$ 只（或 $\geq k + 1$ 只）。

翻译回去：说清”同笼”在原问题里意味着什么 $\Rightarrow$ 得出结论。

阅卷给分看的就是第 1、2、5 步写没写清楚——这恰恰是你最爱跳过、而必须练出来的部分。

三、统一主线（请内化）

容斥：“每个元素恰好数一次”，靠交错 $\pm$ 实现（底层是 $\sum (- 1)^{k} (k m) = 0$ ，你证过）；解题时优先用”一个坏性质都不满足 = 总数 − 单 + 双 − 三 ⋯”。
鸽笼：用”计数不等式 + 反证”逼出存在性；全部难度在”设鸽子、设笼子”，原理本身不值钱。
都根植于你的旧工具：容斥 ↔ 莫比乌斯反演（数论）；鸽笼 ↔ 按余数分类（数论）+ 算法里的抽屉直觉。

四、我的观点（直说）

这一站对你是整条曲线里”战略价值最高”的一站。原因：

容斥是计算型（错排、满射、 $φ$ ），你的强项，学起来会很顺——但也正因如此，别在这里恋战，你早就具备这种”套公式 + 验证”的能力。
鸽笼是纯思维型、纯证明型，是你的弱项，也是 USAMO 出现频率最高的工具之一。它和不变量、构造一起构成 USAMO 组合的三大支柱（后面 Stage 5 会专门打）。
鸽笼的价值不在”知道原理”，而在例 C、例 E 那种”设鸽子设笼子”的创造性——这正是”想清楚 + 写清楚”的双重训练。

我的硬建议：容斥部分你快速过（会算就行）；把 80% 的精力压在鸽笼上，每道鸽笼题都用 5 步模板手写完整证明。你 Stage 2 满分证明了你”能想到”；现在要把”想到”稳定地落成”写出”。这一站练好，USAMO 组合你就握住了第一把钥匙。

置信度：约 0.95。 公式推导与全部数值/定理我都用 Python 验证过（ $D_{n}$ 、满射数、子集和界、Erdős–Szekeres 及其紧性）。

注意事项：

容斥的”应用三种”（错排 / 满射 / $φ$ ）是计算型，鸽笼是思维型——时间分配务必向鸽笼倾斜，别被你擅长的计算拖住。
莫比乌斯反演这里只给”连接”，完整版在后面偏序集那一站；现在记住”容斥是它的特例”即可。
平均值原理、Erdős–Szekeres、子集和这类是 USAMO/IMO 真考的鸽笼形态，例 A、B 只是模板演示，别停在那个难度。
本回答为教学、无 Python 代码（验证在后台完成），故未触发安装说明；若你要错排/满射/Erdős–Szekeres 的可运行验证脚本，我给你并附镜像安装命令。

准备好后我就出 Stage 3 试卷。延续你两次的反馈，我建议这次混合口径：容斥部分出 AIME 式纯数值题（发挥你的强项、给你信心），鸽笼部分出证明题、并把”5 步写全才给分”作为硬评分栏（专练你的弱项）。要这个”半数值 + 半证明”的混合卷，还是全做成证明卷？

My Vault

Explorer

3 容斥与鸽笼