Appearance
组合极值与构造
引言
组合极值问题研究在给定约束条件下某个量的最大值或最小值。这类题目往往需要两方面的功力：一是「构造」——给出一个达到目标的例子以证明下界/上界是紧的；二是「证明」——用不等式、反证法或极端原理证明不可超越该值。二者相辅相成，构成竞赛组合题的核心范式。
前置阅读：计数原理与方法 | 不等式证明方法综述 | 数学归纳法
一、极值原理与极端原理
1.1 极值原理
极值原理
在有限非空集合中，最大值和最小值一定存在。这是组合数学中最基本也是最强有力的推理工具之一。
1.2 极端原理的应用
极端原理 (Extremal Principle)
在面对一个组合结构时，考虑其中「最大」或「最小」的元素（如最长路径、最大度数顶点、面积最大的三角形等），利用其极端性推导矛盾或得出结论。
例1：极端原理的经典应用
平面上有 $n$ 个点，任意三点不共线。证明：存在一条直线恰好经过其中两个点。
- 证明
考虑每对点确定的直线。由于点有限，存在一对点 $(A, B)$使得直线$AB$ 不经过任何其他点（只需取所有点对中，使得第三个点到该直线距离非零且最小的一对——若所有点对确定的直线都经过至少三个点，则所有点共线，与「任意三点不共线」矛盾）。
虽然这是一个经典几何结论（Sylvester-Gallai 定理），但极端原理提供了一种优雅的证明：在所有点对中选取点 $C$到直线$AB$的距离为正且最小的一对$(AB, C)$。若 $AB$还经过第四点$D$，则 $C$到$AD$或$C$到$BD$ 的距离更小，矛盾。$\square$
:::
例2：极端原理在图论中的应用
证明：每个连通无向图中都存在一个顶点，删除它后图仍然连通（非割点），除非该图是 $K_2$。
- 证明
考虑图 $G$的一棵生成树$T$。取 $T$的一个叶子$v$（度数为 $1$的顶点）。删除$v$不影响$T$中其余顶点的连通性（因为$v$只在$T$中连着一个顶点），所以也不影响$G$ 中其余顶点的连通性（$G$的边数$\geq$ $T$ 的边数）。极端地取最长路径的端点即可找到这样的叶子。
:::
二、构造法
构造法的思想
在组合极值问题中，需要两件事：
- 上界估计：证明 $f(n) \leq M$。
- 构造：给出一个达到 $M$的具体例子，证明$f(n) \geq M$，从而 $f(n) = M$。
构造是实现「等号成立」的关键。
例3：构造法求极值
$n$ 个点最多能确定多少条线段，使得其中任意三条不构成三角形？（即不含三角形的图的最大边数）
- 解析（Turán 定理特例）
答案：$\lfloor n^2/4 \rfloor$条边。这是 Turán 定理$T(n,2)$的特例（禁止$K_3$）。
上界证明（Mantel 定理）：设图 $G$ 不含三角形，$\deg(v)$为顶点$v$的度数。对于任意边$uv$，$u$和$v$的邻居集不交（否则与$uv$构成三角形），故$\deg(u) + \deg(v) \leq n$。求和： $$\sum_{v} \deg(v)^2 = \sum_{uv \in E} (\deg(u) + \deg(v)) \leq |E| \cdot n$$ 由 Cauchy-Schwarz：$\left(\sum \deg(v)\right)^2 \leq n \sum \deg(v)^2 \leq n \cdot |E| \cdot n$，即 $4|E|^2 \leq n^2 |E|$，得 $|E| \leq n^2/4$，整数性给出 $|E| \leq \lfloor n^2/4 \rfloor$。
构造（达到上界）：将 $n$个点尽可能均分为两组（大小差至多为$1$），组内无边，组间全部连边。当 $n$为偶数时每组$n/2$个点，边数$= (n/2)^2 = n^2/4$。这是完全二部图 $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$，显然不含三角形（二部图无奇圈）。
:::
三、反证法在组合极值中的应用
反证法 + 极值原理
假设存在反例，取其中某个量极端（最小/最大）的反例，然后通过构造更小的反例或推出矛盾来证明原命题。
例4：反证法+极值原理
证明：任意 $2n+1$个整数中，存在$n+1$个数，它们的和是$n+1$ 的倍数。
- 证明（Erdős–Ginzburg–Ziv 定理特例）
这是 EGZ 定理的一个特殊情形（模 $n+1$时更复杂）。对于$n=1$：$3$个数中必有$2$个和能被$2$ 整除，即必有两个同奇偶（鸽巢原理）。
对于一般的 $n$，使用 Cauchy-Davenport 定理或组合数论工具。这里给出 $n=2$ 的特例：$5$个整数中必有$3$个其和被$3$整除。考虑模$3$余数分类，若某类$\geq 3$则取该类$3$个即得；否则各类都$\leq 2$，则三类都有代表，各取一个余数和 $0+1+2=3 \equiv 0$。$\square$
:::
四、子集族与 Sperner 定理
反链 (Antichain)
设 $\mathcal{F}$是$[n] = \lbrace 1, 2, \ldots, n\rbrace $的一族子集。若$\mathcal{F}$中任意两个集合互不包含（即不存在$A, B \in \mathcal{F}$满足$A \subsetneq B$），则称 $\mathcal{F}$ 是反链。
Sperner 定理 (1928)
$n$元集合的反链的最大尺寸为$\binom{n}{\lfloor n/2 \rfloor}$，该最大值在取所有 $\lfloor n/2 \rfloor$ 元子集时达到。
证明思路（LYM 不等式）
最大链（全序子族）共有 $n!$条（每个排列对应一条从$\varnothing$依次加入排列中各元素的链）。任意$k$元集合$A$恰好出现在$k!\thinspace(n-k)!$条最大链中。若$\mathcal{F}$为反链，每条最大链最多包含$\mathcal{F}$ 中的一个集合，故： $$\sum_{A \in \mathcal{F}} |A|!\thinspace(n-|A|)! \leq n!$$ 除以 $n!$得$\sum_{A \in \mathcal{F}} 1/\binom{n}{|A|} \leq 1$。若 $\mathcal{F}$中集合大小不一，以其中数量最多的尺寸层的反链替换之，用$\binom{n}{\lfloor n/2 \rfloor}$ 的极大性得证。
例5：Sperner 定理应用
设 $\mathcal{F}$是$[n]$的子集族，且对任意$A, B \in \mathcal{F}$，$A \cap B \neq \varnothing$（两两相交）。求 $|\mathcal{F}|$ 的最大值。
- 解析
答案为 $2^{n-1}$。取所有含有元素 $1$ 的子集即达到该值。 证明极大性：若 $|\mathcal{F}| > 2^{n-1}$，则必存在 $A \in \mathcal{F}$使得$A^{\complement} \in \mathcal{F}$（鸽巢原理），但 $A \cap A^{\complement} = \varnothing$，矛盾。
:::
五、组合几何
5.1 Erdős–Szekeres 定理
Erdős–Szekeres 定理（凸包版本）
对于任意 $n \geq 3$，平面上任意 $2^{n-2} + 1$个处于一般位置（无三点共线）的点中，存在$n$个点构成凸$n$ 边形的顶点。
简化版本（$n=4$）
任意 $5$个无三点共线的点中，存在$4$个点构成凸四边形。证明：若$5$ 个点的凸包是五边形或四边形，结论显然；若凸包是三角形，内部两点确定的直线必定与三角形的两条边相交，从而这两个内部点与三角形的某两个顶点共同构成凸四边形。
5.2 凸包与凸性
凸包 (Convex Hull)
点集 $S$的凸包是包含$S$的最小凸集，等价于$S$ 中所有点的凸组合的集合。平面上有限点集的凸包是一个凸多边形。
竞赛应用
凸包是极端原理在几何中的典型体现。在讨论「最远点对」「最小覆盖圆」等问题时，极值点往往落在凸包的顶点上。
六、双计数法 (Double Counting)
双计数法
对同一个对象用两种不同的方式计数，令两个表达式相等，从而得到方程或不等式。这是组合数学中最优雅的技巧之一。
常见双计数对象
- 按行按列求和：矩阵中元素按行求和 = 按列求和。
- 边—度双计数：$\sum \deg(v) = 2|E|$（握手定理）。
- 有序对 $(x, S)$：元素 $x$属于子集$S$ 的计数。
- 关联矩阵：顶点与边的关联关系。
例6：双计数法证明恒等式
证明：$\displaystyle \sum_{v \in V} \binom{\deg(v)}{2} \geq |E| \cdot \left(\frac{2|E|}{|V|} - 1\right)$（即图中长度为 $2$ 的路径数的下界估计）。
- 解析
长度为 $2$的路径数$P_2$可按顶点计数：每个顶点$v$从它的$\deg(v)$个邻居中选$2$ 个作为路径端点（$v$为中间点），故$P_2 = \sum_v \binom{\deg(v)}{2}$。 由凸性（或 Cauchy-Schwarz）：$\sum_v \deg(v)^2 \geq \frac{(\sum \deg(v))^2}{|V|} = \frac{4|E|^2}{|V|}$ 故 $P_2 = \frac{1}{2}\sum_v \deg(v)(\deg(v)-1) = \frac{1}{2}(\sum \deg(v)^2 - 2|E|) \geq \frac{1}{2}(\frac{4|E|^2}{|V|} - 2|E|) = |E|(\frac{2|E|}{|V|} - 1)$。
:::
例7：双计数法经典题
在一个 $n \times n$的$0$-$1$矩阵中，设每行恰有$k$个$1$，每列也恰有 $k$个$1$。证明：存在一种排列（置换矩阵）使得这些 $1$中$n$ 个互不同行不同列。
- 证明（Birkhoff–von Neumann 定理特例 + 双计数 + Hall 定理）
行和 = 列和 = $k$。构造二部图：左侧为 $n$行，右侧为$n$ 列，$(i,j)$位置为$1$则连边。每个左顶点度数为$k$，每个右顶点度数为 $k$。任取 $r$个行，它们连接到$t$个列，总边数$rk$全部落在这$t$列中，每列至多$k$条边，故$rk \leq tk$即$r \leq t$。由 Hall 定理，存在完美匹配（$n$条互不共享顶点的边），即$n$个位置上的$1$ 互不同行不同列。
:::
七、覆盖与填装问题
经典覆盖与填装
- 棋盘覆盖：用 $2 \times 1$多米诺骨牌覆盖去掉两个对角方格的$8 \times 8$ 棋盘（不可能，因为染色论证）。
- 球面填装（竞赛中的简单情形）：平面上不相交的单位圆的最大密度。
- 填装与覆盖的对偶性：往往通过面积/体积的双计数来建立不等关系。
染色论证
将棋盘黑白相间染色，每个 $2 \times 1$ 骨牌必覆盖一黑一白。去掉对角同色的两个方格后黑白格数不等，故不可能覆盖。
八、综合例题
例8：组合极值综合题
给定正整数 $n$。求最大的正整数 $m$，使得存在 $m$个$[n]$的子集$A_1, A_2, \ldots, A_m$，满足： 对于任意 $i \neq j$，$A_i \not\subseteq A_j$且$A_j \not\subseteq A_i$，且 $A_i \cap A_j \neq \varnothing$。
- 解析
条件即要求 $\lbrace A_i\rbrace $是两两相交的反链。由 Sperner 定理的变体（或直接取含固定元素的子集），最大值为$\binom{n-1}{\lfloor (n-1)/2 \rfloor}$。
构造：取所有含有元素 $1$且大小为$\lfloor n/2 \rfloor$的子集。这些集合显然两两相交（都有$1$），且因为大小相同所以互不包含。
:::
例9：极端原理+构造
某国有 $n$座城市，任意两座城市之间恰有一条单向航线（锦标赛图）。证明：存在一座城市，从它出发可以通过不超过$2$次飞行到达任意其他城市（即该图存在「半径不超过$2$」的顶点）。
- 证明
在锦标赛（有向完全图）中，取出度最大的顶点 $v$。设 $\deg^+(v) = d$，即 $v$可直接到达$d$座城市。对于任意未直接连向的城市$u$（不在 $v$ 的出邻集中），$u$到$v$ 是有向边。
若存在 $u$使得从$v$不能$2$步内到达，这意味着$u$及其所有出邻居都不在$v$的出邻居集$N^+(v)$中。但这会导致$\deg^+(u) > \deg^+(v)$（因为 $u$连向$v$而$v$不连向$u$，并且 $u$还要连向$N^+(v)$ 中所有元素......），这需要更仔细的论证。
准确证明：取 $v$使得出度最大。对于任意其他城市$u$，若边方向为 $v \to u$，则已达；若 $u \to v$，则考察有无中间城市 $w$使得$v \to w \to u$。若不存在这样的 $w$，即对所有 $w \in N^+(v)$都有$u \to w$。此时 $\deg^+(u) \geq \deg^+(v) + 1$（$u$连向$v$和所有$N^+(v)$），与 $v$出度最大矛盾。故极端顶点$v$满足半径$\leq 2$。
:::
例10：双计数法在几何中的应用
平面上有 $n$ 条直线，任意两条不平行，任意三条不共点。这些直线将平面分成多少个区域？
- 解析
设 $a_n$为$n$条直线将平面分成的区域数。第$n$条直线与前面$n-1$条直线交于$n-1$个不同点，被分成$n$ 段，每段将原有区域一分为二。故： $$a_n = a_{n-1} + n$$ 初始 $a_0 = 1$。递推得： $$a_n = 1 + \sum_{k=1}^{n} k = 1 + \frac{n(n+1)}{2}$$
双计数视角（欧拉公式法）：交点数为 $\binom{n}{2}$，边数为各直线上被交点分割成的线段数。每条直线有 $n-1$个交点，被分成$n$条线段/射线。由平面图的欧拉公式$V - E + F = 1 + C$（$C$为连通分支数，此处$C=1$），可同样得到 $F$ 的公式。
:::
九、Turán 定理（一般形式）
Turán 定理 (1941)
不含 $K_{r+1}$子图的$n$ 顶点图的最大边数为 $$\text{ex}(n, K_{r+1}) = \left(1 - \frac{1}{r}\right) \frac{n^2}{2} \quad \text{(精确到整除)}$$ 极值图为 Turán 图 $T(n, r)$：将 $n$个顶点分成$r$ 个大小尽可能相等的部分，部分内无边，部分间全连。
Mantel 定理作为特例
取 $r = 2$ 即得 Mantel 定理：不含三角形（$K_3$）的图至多有 $\lfloor n^2/4 \rfloor$条边，极值图是完全二部图$K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$。
例11：Turán 定理的归纳证明（$r=2$ 即 Mantel）
设 $G$不含$K_{r+1}$。取一个最大团 $K = \lbrace v_1, \ldots, v_s\rbrace $，$s \le r$。任何其他顶点至多与 $K$中$r-1$个点相邻（否则与$K$形成$K_{r+1}$）。 对归纳假设：$|E(G)| \le \text{ex}(n-1, K_{r+1}) + \delta$，其中 $\delta$ 为加入新顶点时的边数。 详细证明见 拉姆齐理论与极图理论。
Erdős–Stone 定理（极图渐近）
对任意禁图 $H$含色数$\chi(H) = r+1$： $$\text{ex}(n, H) = \left(1 - \frac{1}{r} + o(1)\right) \binom{n}{2}$$ 即禁图色数决定极值边数的渐近。详见 拉姆齐理论与极图理论。
十、Erdős–Ko–Rado 定理（相交族）
Erdős–Ko–Rado 定理 (1961)
设 $n \ge 2k$，$\mathcal{F}$是$[n]$的一族$k$-子集，且任意 $A, B \in \mathcal{F}$满足$A \cap B \ne \varnothing$（相交族）。则 $$|\mathcal{F}| \le \binom{n-1}{k-1}$$ 等号成立当且仅当 $\mathcal{F}$为「所有含某固定元素$i$的$k$-子集」（星型族）。
直观理解
固定一个元素（如 $1$），所有含 $1$的$k$-子集两两相交（都含 $1$），其数量为 $\binom{n-1}{k-1}$。EKR 定理断言这是相交族的最大尺寸。
例12：EKR 的 Katona 证明（影子法）
Katona 的证明巧妙运用「影子」与「圆排列」：将 $[n]$排成圆周，相交的$k$-区间族至多有 $k$个（圆上任意$2k$个相邻点至多贡献$k$个相交$k$-区间）。对所有圆排列计数，每族被计数 $\le k \cdot (n-1)!/(n-k)! \cdot k!$ 次... 详细见专题。
Hilton–Milner 定理（非平凡相交族）
若相交族 $\mathcal{F}$不是星型族（即$\bigcap_{A \in \mathcal{F}} A = \varnothing$），则 $|\mathcal{F}| \le \binom{n-1}{k-1} - \binom{n-k-1}{k-1} + 1$。这是 EKR 的加强版。
十一、概率方法初探
概率方法范式
概率方法是组合极值中证明存在性的强大工具。核心思想：以随机性证明存在性——若某对象以正概率出现，则其必存在。详见 概率方法与随机结构。
期望方法
设 $X$是某随机结构的随机变量（如「不良子结构数」），若$E[X] < 1$，则存在使 $X = 0$ 的样本，即不存在该不良结构。
例13：独立集下界（alteration 方法）
设 $G$为$n$顶点图，最大度$\Delta$。证明 $\alpha(G) \ge n/(\Delta + 1)$。
- 证明（贪心 + 概率）
贪心法：任取顶点 $v$加入独立集$I$，删除 $v$及其邻居（至多$\Delta + 1$个），重复。每次删除$\le \Delta + 1$个点，故$|I| \ge n/(\Delta + 1)$。
概率法视角：以均匀随机顺序处理顶点，顶点 $v$加入$I$当且仅当$v$在其邻居前被处理。对每个$v$，$P(v \in I) \ge 1/(\deg(v) + 1) \ge 1/(\Delta + 1)$。故 $E[|I|] = \sum_v P(v \in I) \ge n/(\Delta + 1)$，存在顺序使 $|I| \ge n/(\Delta + 1)$。
:::
例14：Ramsey 数下界 $R(k, k) > 2^{k/2}$
Erdős 1947：对 $K_n$的边随机染红/蓝（概率各$1/2$）。同色 $K_k$的期望数为$\binom{n}{k} \cdot 2 \cdot 2^{-\binom{k}{2}}$。当 $n < 2^{k/2}$时期望$< 1$，故存在染色无同色 $K_k$，即 $R(k, k) > 2^{k/2}$。详细见 拉姆齐理论与极图理论 与 概率方法与随机结构。
十二、组合不等式速查
常用极值不等式
| 问题 | 上界 | 极值结构 | 来源 |
|---|---|---|---|
| 禁 $K_3$最大边数 | $\lfloor n^2/4 \rfloor$ | $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$ | Mantel 1907 |
| 禁 $K_{r+1}$最大边数 | $\approx (1-1/r) n^2/2$ | Turán 图$T(n,r)$ | Turán 1941 |
| 反链最大尺寸 | $\binom{n}{\lfloor n/2 \rfloor}$ | 中间层 | Sperner 1928 |
| 相交 $k$-子集族 | $\binom{n-1}{k-1}$ | 星型族 | EKR 1961 |
| $n$顶点图独立数 | $\ge n/(\Delta+1)$ | — | Turán 贪心 |
| 平面图边数 | $\le 3n - 6$ | 三角剖分 | Euler 公式 |