Bóna · 枚举与解析组合学导论 · 第 6 章 极值组合学

6.3　有总比没有强：存在性证明Something is more than nothing: Existence proofs

本页为译文 + 高中讲解合一：黑色正文为忠实翻译；彩色框（目标 / 例 / 定义 / 分步推演）与配图为面向高中生的详解，逐步推演、举例、画图，不用比喻。

本节建立在一个强有力——虽然算不上惊天动地——的想法之上：如果某类对象的数目是正的，那么它至少为 \(1\)，于是至少存在一个这样的对象。在读者嘲笑我们竟然讨论如此平凡的道理之前，我们要指出：我们将在某些场合使用这一方法，而在那些场合中，某些构造的存在性是高度不平凡的，因此恰恰需要被证明出来。

本节目标学会一种证明“某种东西存在”的手法：不去把那个东西具体造出来，而是去数“满足要求的方案有多少个”，并说明这个数目大于 \(0\)。只要数出来是正数，就断定至少有一个方案存在——哪怕我们说不出它具体长什么样。这正是“有总比没有强”的含义。

6.3.1　性质 B（Property B）

既然超图（hypergraph）的概念还停留在我们脑海中（参见上一节），我们就从这一领域里取一个例子开始。性质 B（Property B）是超图的一条被深入研究过的性质。我们用下面的例子来解释它。

例 6.41 一位橄榄球教练想和队员们试验各种进攻阵型。教练手下有 \(n\) 名进攻球员；在训练的前一天，他设计了 \(m\) 套进攻阵型，每套阵型都由 \(k\) 名进攻球员组成。然后，在训练开始时，教练给每名球员发一件橙色或蓝色的球衣穿上。请证明：如果 \(m<2^{k-1}\)，那么无论这些进攻阵型是如何设计的，教练总能这样分配球衣，使得每一套进攻阵型中两种颜色都出现。

一般地，我们称 \([n]\) 上的一个超图 \(F\) 具有性质 B（可二染色，bi-colorable），如果能够用两种颜色给 \([n]\) 的元素染色，使得 \(F\) 的任何一条边都不是单色的（即同一条边的元素不全同色）。用这套术语来说，例 6.41 的断言就是：如果 \([n]\) 上的一个 \(k\)-一致（\(k\)-uniform）超图 \(F\) 的边数少于 \(2^{k-1}\)，那么 \(F\) 具有性质 B。

术语回顾

把抽象定义落到具体小例子上，就能看清“性质 B”到底在说什么。

\(n=5\) 个顶点，两条边各含 \(k=3\) 个顶点 边 \(A=\{1,2,3\}\) 边 \(B=\{3,4,5\}\) 1 2 3 4 5 蓝=蓝色球衣，橙=橙色球衣；每条边里都既有蓝又有橙 ⇒ 没有单色边
顶点 \(1,3\) 染蓝，\(2,4,5\) 染橙。边 \(A=\{1,2,3\}\) 含蓝(1,3)与橙(2)，边 \(B=\{3,4,5\}\) 含蓝(3)与橙(4,5)。两条边都不是单色的，所以这个超图具有性质 B。
最小数字例：为什么需要“边少”这个条件 取 \(k=2\)（每条边 \(2\) 个顶点，这就是普通图）。此时 \(2^{k-1}=2^{1}=2\)，定理保证：边数 \(m<2\)（即只有 \(1\) 条边）时一定能二染色避免单色边——的确，一条边把两个端点染不同色即可。再看 \(k=3\)：\(2^{k-1}=4\)，只要阵型套数 \(m\le 3\)，无论怎么设计都能发球衣使每套阵型两色齐全。上面的图就是 \(m=2\le 3\) 的一个成功例子。

把“存在性证明”讲透：用数数代替构造

核心策略要证明“存在一种好的发衣方案”，我们不直接找出那种方案，而是：① 数出全部发衣方案共有多少种；② 数出“坏方案”（至少有一套阵型单色）最多有多少种；③ 若坏方案数 \(<\) 总方案数，则好方案数 \(=\) 总数 \(-\) 坏数 \(>0\)，于是好方案至少有一个，存在性得证。

下面把例 6.41 的证明拆成最小的步子。每名球员发橙色或蓝色，是 \(2\) 选 \(1\)；\(n\) 名球员相互独立，所以——

  1. 总方案数。每名球员有 \(2\) 种颜色可选，共 \(n\) 名，由乘法原理，发衣方案总数为 \[N_{\text{总}}=2^n.\]
  2. 固定一套阵型，数“它单色”的方案数。设某条边（某套阵型）\(e\) 恰含 \(k\) 名球员。要让 \(e\) 单色，先选 \(e\) 的统一颜色（橙或蓝，\(2\) 种），这 \(k\) 名球员的颜色随即被定死；而其余 \(n-k\) 名球员仍可任意染色，有 \(2^{n-k}\) 种。于是使这条边单色的方案数为 \[2\cdot 2^{\,n-k}=2^{\,n-k+1}.\]
  3. 把所有边的“坏”情形加起来（放大估计）。共有 \(m\) 条边。一个方案只要“至少有一条边单色”就算坏方案。按边逐一统计单色情形，可能把“同时让两条边单色”的方案重复数到，因此这只是一个上界： \[N_{\text{坏}}\ \le\ \sum_{e}2^{\,n-k+1}=m\cdot 2^{\,n-k+1}.\]
  4. 代入条件 \(m<2^{k-1}\)。把它乘进上界： \[N_{\text{坏}}\ \le\ m\cdot 2^{\,n-k+1}\ <\ 2^{\,k-1}\cdot 2^{\,n-k+1}=2^{\,n}.\]
  5. 结论：好方案数为正。好方案数 \(=\) 总方案数 \(-\) 坏方案数（坏方案被排除后剩下的就是每套阵型都两色齐全的方案），于是 \[N_{\text{好}}\ \ge\ N_{\text{总}}-N_{\text{坏}}\ >\ 2^{n}-2^{n}=0.\] 既然 \(N_{\text{好}}>0\)、而它又是一个整数，那么 \(N_{\text{好}}\ge 1\)：至少存在一种发衣方案，使每套阵型都同时出现两种颜色。\(\;\square\)♦

请注意第 5 步正是本节标题的精神所在：我们从未指出究竟该给谁发橙、给谁发蓝；我们只证明了“好方案的个数大于零”，因此“有”（存在）就比“没有”强——存在性已经成立。“有总比没有强”说的就是：数目只要是正的，就保证了至少一个对象的存在。

把全部 \(2^n\) 种发衣方案想成一条长度为 \(2^n\) 的尺子 总方案数 \(=2^{n}\) 坏方案 \(\le m\cdot2^{n-k+1}<2^{n}\) 好方案 \(>0\) 坏方案这一段比整把尺子短 ⇒ 一定剩下非空的“好方案”段 ⇒ 好方案至少有一个
条件 \(m<2^{k-1}\) 保证“坏方案”这一段严格短于整段 \(2^n\)，于是绿色“好方案”段非空。我们不需要知道绿色段里具体是哪一种染色，只要它非空，存在性就成立。
代入数字感受一下 设 \(n=6\) 名球员、每套阵型 \(k=3\) 人。则 \(2^{k-1}=4\)，条件要求 \(m<4\)，即最多 \(3\) 套阵型。
  1. 总方案数 \(N_{\text{总}}=2^{6}=64\)。
  2. 每条边单色的方案数 \(=2^{\,6-3+1}=2^{4}=16\)。
  3. 取 \(m=3\)：坏方案 \(\le 3\times 16=48\)。
  4. \(48<64\)，故好方案 \(\ge 64-48=16>0\) ——至少存在 \(16\) 种合格的发衣法。
  5. 若 \(m=4\)（违反条件）：坏方案上界变成 \(4\times16=64=N_{\text{总}}\)，上界不再小于总数，本方法失效——这说明阈值 \(2^{k-1}\) 是这套数数论证能用的边界。
即时自测
  1. 把上面的论证里“两种颜色”换成“三种颜色”，每条边仍含 \(k\) 个顶点。仿照第 2 步，使某条固定边单色的染色方案有多少种？（提示：先选统一颜色，再给其余顶点任意染色。）
  2. 承上，三色情形下总染色方案是 \(3^n\)。请写出一个保证“存在不出现单色边的三染色”的充分条件（形如“边数 \(m<\;?\)”）。
  3. 在二色、\(k\)-一致的设定下，若某超图的边数恰为 \(2^{k-1}\)，本节的数数法还能不能保证它具有性质 B？为什么？

返回 全书目录