Bóna · 枚举与解析组合学导论 · 第 1 章 基本方法

1.5　鸽笼原理The pigeonhole principle

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

鸽笼原理（pigeonhole principle）的陈述几乎和加法原理一样简单。然而事实证明，它是一件非常有力的工具，拥有大量出人意料地强大的应用。

本节目标讲清一句话：把“很多东西”放进“不多的盒子”里，必然有某个盒子里东西特别多。我们要把这句话写成精确的不等式（定理 1.44），用反证法证明它，再用四个例子展示它如何解决看似毫不相干的问题——从纽约人口、整除性，到无理数的逼近。
定理 1.44（鸽笼原理）设 \(A_1,A_2,\cdots,A_k\) 是两两不相交（pairwise disjoint）的有限集合。又设 \[|A_1\cup A_2\cup\cdots\cup A_k|>kr.\] 那么至少存在一个下标 \(i\)，使得 \(|A_i|>r\)。

换句话说，如果若干个不相交集合的并集“很大”，那么其中至少有一个集合也必须“相当大”。在为忙碌的一周安排课程时，你大概体会过这一点。如果你想在五天的一周里安排多于 \(20\) 小时的课，那么至少有一天的课会多于 \(4\) 小时。

思考鸽笼原理的一种经典方式是用盒子与小球（这看起来比把鸽子塞进笼子更人道一些）。如果我们把多于 \(kr\) 个小球分到 \(k\) 个盒子里，那么至少有一个盒子里会有多于 \(r\) 个小球。

把 \(13\) 个球放进 \(4\) 个盒子（\(k=4,\ r=3,\ kr=12\)） 3 个 3 个 3 个 4 个 ←
每盒至多 \(3\) 个的话，\(4\) 个盒子至多装 \(4\times 3=12\) 个，可球有 \(13>12\) 个。于是某盒必须破例装到 \(4>3\) 个。这正是 \(r=3,\ k=4\) 的鸽笼原理。

鸽笼原理的证明是一种标准证明技巧的范例。我们通过说明“它的反面不可能成立”来证明定理。也就是说，我们假设原命题的反面为真（在这里，即假设不存在使 \(|A_i|>r\) 成立的下标 \(i\)），然后从这个假设导出矛盾。这种做法称为间接证明（indirect proof）或反证法（proof by contradiction）。

证明. 假设我们想证明的命题为假。那么对每个 \(i\) 都有 \(|A_i|\le r\)。于是 \[|A_1\cup A_2\cup\cdots\cup A_k|=|A_1|+|A_2|+\cdots+|A_k|\le kr,\] 这与我们最初的假设 \(|A_1\cup A_2\cup\cdots\cup A_k|>kr\) 矛盾。♦
  1. 因为要证“某个 \(|A_i|>r\)”不好正面下手，于是先假设它的反面：每一个 \(|A_i|\) 都 \(\le r\)。
  2. 各集合两两不相交，用广义加法原理（定理 1.2）把并集大小写成各部分之和：\(|A_1\cup\cdots\cup A_k|=|A_1|+\cdots+|A_k|\)。
  3. 把每一项都换成它的上界 \(r\)，共 \(k\) 项，得到总和 \(\le kr\)。
  4. 这与题设“并集 \(>kr\)”直接冲突。假设站不住脚，所以必有某个 \(|A_i|>r\)。
例 1.45 目前居住在纽约市的人中，至少有八个人是在同一年、同一天、同一小时出生的。

尽管纽约市的人口每天都在变化，但可以稳妥地假设它始终超过 \(750\) 万人。

解. 我们可以稳妥地假设纽约市所有居民都不超过 \(120\) 岁。因此他们最早在 \(120\) 年前出生。由于每年至多有 \(366\) 天，我们考虑的这些人至多 \(120\cdot 366=43920\) 天大。这么多天里的小时数为 \[k=24\cdot 43920=1054080.\] 现在令 \(A_1\) 为在第一个可能的小时出生的纽约居民之集合，令 \(A_2\) 为在第二个可能的小时出生的纽约居民之集合，依此类推，\(A_k\) 表示在最后一个可能的小时（即此刻正在结束的那个小时）出生的居民之集合。那么我们知道 \[|A_1\cup A_2\cup\cdots\cup A_k|\ge 7500000.\tag{1.11}\] 因为所有 \(A_i\) 的并集就是纽约市的全部人口。现在我们取 \(r=7\) 应用鸽笼原理。由于 \(k=1054080\)，可见左边大于 \(7k=7\,378\,560\)，所以至少有一个 \(A_i\) 必须包含多于七个人。♦
  1. 定盒子：把“一个具体的出生小时”当作一个盒子。最多 \(120\) 岁、每年至多 \(366\) 天、每天 \(24\) 小时，所以盒子数 \(k=24\cdot 366\cdot 120=1054080\)。
  2. 定球：每个纽约人按其出生小时放进对应盒子。球数（人口）\(\ge 7\,500\,000\)。
  3. 选 \(r\)：要证“至少八人同一小时”，即要某盒 \(>7\) 个。取 \(r=7\)，需验证球数 \(>kr=7k\)。
  4. 验证：\(7k=7\times 1054080=7\,378\,560<7\,500\,000\)。题设球数确实超过 \(kr\)。
  5. 由鸽笼原理，必有一盒装了 \(>7\) 个人，即至少 \(8\) 人同年同日同一小时出生。♦

鸽笼原理一个经常被用到的特殊情形是 \(r=1\)。此时原理说：如果 \(k\) 个盒子总共装了多于 \(k\) 个球，那么至少有一个盒子必须装多于一个球。即便是这个简单的特殊情形，也有有趣的应用，下面我们就会看到。

\(r=1\)：\(4\) 个球放进 \(3\) 个盒子（\(4>3\)） 这盒装了 2 个 ←
三盒若每盒至多 \(1\) 个，至多装 \(3\) 个；现有 \(4\) 个，必有一盒装到 \(2\) 个。这就是最常用的“多于 \(k\) 个进 \(k\) 个盒”版本。
例 1.46 考虑数列 \(1,3,7,15,31,\dots\)，换言之，第 \(i\) 项为 \(a_i=2^i-1\) 的数列。设 \(q\) 为任意奇数。那么我们的数列含有一个能被 \(q\) 整除的项。

这是一个相当强的命题。除了“\(q\) 是奇数”之外，我们对 \(q\) 没有任何要求。因此，我们的命题对 \(q=17\) 成立，对 \(q=2007\) 或 \(q=3542679\) 同样成立。所有这些数都有一个倍数恰好等于“某个 \(2\) 的幂减一”。

解. 考虑数列的前 \(q\) 项。如果其中某一项能被 \(q\) 整除，那就证完了。如果不能，那么考虑它们除以 \(q\) 的余数。也就是说，写 \[a_i=d_i q+r_i,\] 其中 \(0m\)。于是 \(a_n=d_n q+r_n\) 且 \(a_m=d_m q+r_n\)，从而 \[a_n-a_m=(d_n-d_m)q,\] 或者，整理后 \[\begin{aligned}(d_n-d_m)q&=a_n-a_m\\&=(2^n-1)-(2^m-1)\\&=2^m(2^{\,n-m}-1)\\&=2^m a_{\,n-m}.\end{aligned}\] 由于这串等式的第一个表达式能被 \(q\) 整除，所以最后一个表达式也必须能被 \(q\) 整除。注意 \(2^m\) 与任何奇数 \(q\) 互素，即 \(2^m\) 与 \(q\) 的最大公约数为 \(1\)。因此，等式 \((d_n-d_m)q=2^m a_{\,n-m}\) 蕴含 \(a_{\,n-m}\) 能被 \(q\) 整除。这就完成了求解。♦
具体数字演示（取 \(q=5\)） 数列前 \(5\) 项：\(a_1=1,\ a_2=3,\ a_3=7,\ a_4=15,\ a_5=31\)。它们除以 \(5\) 的余数依次为 \[1,\ 3,\ 2,\ 0,\ 1.\] 其中 \(a_4=15\) 余数已经为 \(0\)，即 \(5\mid 15\)，直接命中。再看“余数相等”的机制：\(a_1\) 与 \(a_5\) 的余数都是 \(1\)（\(n=5,m=1\)），于是 \[a_5-a_1=31-1=30=2^1\cdot 15=2^1 a_{4},\] 而 \(30\) 能被 \(5\) 整除、\(2\) 与 \(5\) 互素，所以 \(a_4=15\) 也能被 \(5\) 整除——与直接观察一致。
  1. 只看前 \(q\) 项的余数。余数取值只能是 \(1,2,\dots,q-1\)（题设里它们都不为 \(0\)），共 \(q-1\) 个“盒子”。
  2. 余数有 \(q\) 个（\(q\) 个球），球比盒多，由 \(r=1\) 的鸽笼原理必有两项余数相同：\(r_n=r_m\)。
  3. 两项相减，余数抵消，得 \(a_n-a_m=(d_n-d_m)q\)，左边能被 \(q\) 整除。
  4. 用 \(2^n-2^m=2^m(2^{n-m}-1)=2^m a_{n-m}\) 把差改写。因为 \(2^m\) 与奇数 \(q\) 互素，整除性只能落到 \(a_{n-m}\) 头上。
  5. 于是数列的第 \(n-m\) 项 \(a_{n-m}\) 被 \(q\) 整除，命题得证。

下文中，我们用 \([n]\) 表示集合 \(\{1,2,\cdots,n\}\)，即前 \(n\) 个正整数构成的集合。

例 1.47 我们从集合 \([2n]\) 中任意选取 \(n+1\) 个不同的整数。那么所选整数中至少有一对，其和为 \(2n+1\)；并且所选整数中至少有一对，其差为 \(n\)。
解. 把我们的集合分成 \(n\) 个子集，即子集 \(\{1,2n\}\)、子集 \(\{2,2n-1\}\)，依此类推，一般的子集为 \(\{i,\ 2n+1-i\}\)，其中 \(1\le i\le n\)。由于我们选了 \(n+1\) 个整数，而 \([2n]\) 只被分成了 \(n\) 个两元素子集，鸽笼原理表明：必存在一个两元素子集 \(X\)，使得 \(X\) 的两个元素都被选中。\(X\) 中两元素之和为 \(2n+1\)，因此第一个论断得证。

现在把 \([2n]\) 分成 \(n\) 个子集 \(\{1,n+1\}\)、\(\{2,n+2\}\)，依此类推，一般的子集为 \(\{i,\ n+i\}\)，其中 \(1\le i\le n\)。同样地，由鸽笼原理，这 \(n\) 个子集中必有一个，记为 \(Y\)，由两个被选中的整数组成。然而 \(Y\) 中两元素之差为 \(n\)，第二个论断得证。♦
取 \(n=4\)，即 \([8]=\{1,\dots,8\}\)，按“和为 \(9\)”配对成 \(4\) 个盒子 {1, 8}和=9 {2, 7}和=9 {3, 6}和=9 {4, 5}和=9 选 \(n+1=5\) 个数放进这 \(4\) 个盒子…… 必有一盒装满两个 → 那一对的和恰为 \(9=2n+1\)
关键在于怎样分盒：要凑“和为 \(2n+1\)”就让每盒两数相加得 \(2n+1\)；要凑“差为 \(n\)”就让每盒两数相差 \(n\)（即 \(\{i,n+i\}\)）。两种分法都恰好得到 \(n\) 个盒子，而我们手里有 \(n+1\) 个数，鸽笼原理保证某盒被占满。

根据前两个例子，读者也许会以为鸽笼原理只能用于所有相关对象都是整数的问题。事实远非如此，下面的例子即为明证。

例 1.48 设 \(p\) 为任意正无理数。那么存在一个正整数 \(n\)，使得 \(np\) 与最近的整数之间的距离小于 \(10^{-10}\)。

这里的 \(10^{-10}\) 并无任何神奇之处，我们只是用它代表“极小的数”。换句话说，本例断言：任何无理数的倍数都可以任意接近某个整数。这一点常被表述为：无理实数的集合在全体实数的集合中是稠密的（dense）。

解. 我们用一个圆来表示全体正实数的集合，如图 1.11 所示。也就是说，我们把这个圆看成周长为 \(1\)；如果两个实数之差为整数，则它们用圆上的同一个点来表示。

现在把圆周分成 \(10^{10}\) 等份。（图 1.11 为了画面清晰，只画了分成 \(12\) 份的情形。）取数列 \(p,2p,3p,\cdots\) 的前 \(10^{10}+1\) 项。由于只有 \(10^{10}\) 段弧，由鸽笼原理，必有一段弧 \(T\) 含有这个数列的至少两项。设 \(ip\) 与 \(jp\) 是这样的两项，其中 \(i♦
1, 2, 3, … 1.25, 2.25, … 1.5, 2.5, … 1.75, …
图 1.11：用一个周长为 \(1\) 的圆表示 \(\mathbb{R}^+\)。相差整数的实数落在同一点上（这就是“取小数部分”）。把圆周等分成许多小弧当作盒子，\(p,2p,3p,\dots\) 当作球，球比弧多，必有两球同弧；它们之差的倍数 \((j-i)p\) 就贴近整数了。
  1. 为什么用圆：只关心 \(np\) 离整数多近，等价于只关心 \(np\) 的小数部分。把相差整数的点等同起来，正实数就卷成了一个周长 \(1\) 的圆。
  2. 分盒：把圆周等分成 \(10^{10}\) 段小弧，每段长 \(10^{-10}\)。这是 \(10^{10}\) 个盒子。
  3. 放球：取前 \(10^{10}+1\) 个倍数 \(p,2p,\dots\)，按其在圆上的位置投进对应小弧。球数 \(>\) 弧数。
  4. 鸽笼：必有一段弧 \(T\) 同时装下 \(ip\) 与 \(jp\)（\(i
  5. 作差：两点在圆上的距离正是 \((j-i)p\) 离整数的距离（小数部分之差），于是它 \(<10^{-10}\)。取 \(n=j-i\) 即可。
即时自测
  1. 把 \(r=1\) 的特殊情形重新陈述一遍：要保证“某盒至少 \(2\) 个球”，至少要放多少个球进 \(k\) 个盒子？再据此说明：任取 \(13\) 个人，必有至少两人是在一年中的同一个月出生的。
  2. 仿照例 1.47 的分盒方法：从 \(\{1,2,\dots,10\}\) 中任取 \(6\) 个数，证明其中必有两个数之和为 \(11\)。请写出你用的 \(5\) 个“盒子”。
  3. 仿照例 1.46：取 \(q=7\)，逐项计算 \(a_i=2^i-1\) 除以 \(7\) 的余数，找出数列中第一个被 \(7\) 整除的项。

返回 全书目录