组合与博弈

$n+1$ 个物体放进 $n$ 个抽屉，必有一屉 $\ge2$。难点永远在设计抽屉：

• 按余数：$n+1$ 个整数必有两个 $\bmod n$ 同余（差被 $n$ 整除）。
• 按奇部：$\{1,\dots,2n\}$ 取 $n+1$ 个必有一个整除另一个（写 $m=2^a\cdot(\text{奇})$，奇部只有 $n$ 种）。
• 按奇偶格点 $(\mathbb Z/2)^2$：任意 5 个整点必有两个中点为整点。
• 区域切分：单位正方形分成 4 个小正方形 ⇒ 5 点必有两点距离 $\le\tfrac{\sqrt2}{2}$。

用完鸽巢别忘紧性构造说明界不可改进。

取一个使某量达到最大/最小的对象，再证它必满足所需性质，否则可微调得到更优者、矛盾。

典型：最大割——把顶点二分使跨组边最多；若某顶点在本组的邻居多于对面，移动它会增加跨组边，矛盾。于是「每人在对面组的朋友 $\ge$ 本组」。这也证明了任意图的最大割 $\ge$ 一半的边。

不变量（invariant）：找一个在每步操作下守恒的量（常是某个模），用它证明「目标状态不可达」（黑板改数、硬币翻转、拼图奇偶）。

单变量 / 单调量（monovariant）：找一个每步严格单调且有界的量，证明过程必然终止（如把一排硬币的状态看成二进制数，每次操作使它严格减小）。

同一个量用两种方式数，令其相等。图论里 $\sum_v\deg(v)=2|E|$（握手引理）。

应用：Mantel 定理——无三角形图的边数 $\le\lfloor n^2/4\rfloor$。证法：无三角形 ⇒ 每条边两端 $\deg(u)+\deg(v)\le n$；对所有边求和得 $\sum\deg^2\le n|E|$，再由 Cauchy–Schwarz $\sum\deg^2\ge\tfrac{(2|E|)^2}{n}$，合并得 $|E|\le n^2/4$。

分治归纳：把 $2^{n+1}$ 问题四分成 $2^n$ 子问题——如 $2^n\times2^n$ 缺一格棋盘用 L 形三格骨牌铺满（中心放一块，给另三象限各造一个缺口）；$n$ 条直线分平面为 $1+n+\binom n2$ 块（第 $k$ 条线加 $k$ 块）。

插入法：把新元素插进已排好的序列——每个锦标赛都有哈密顿路径（沿链找胜负翻转处插入）。

剥离法：找一对相邻的目标、连起来、剥掉、归纳——圆上 $2n$ 点 $n$ 红 $n$ 蓝可用 $n$ 条非交叉红蓝弦相连。

Ramsey $R(3,3)=6$：$6$ 人必有 3 互识或 3 互不识（对一人用鸽巢逼出 3 条同色边，再看这 3 人内部）。$5$ 人不够（五边形 + 五角星反例）。

Erdős–Szekeres：$n^2+1$ 个不同实数必含长 $n+1$ 的单调子序列（给每项贴标签 $(x_i,y_i)=$（结尾于 $i$ 的最长增/减长度），鸽巢 + 局部可延展性）。

幸福结局：一般位置 5 点必含凸四边形（按凸包分类）。