鸽巢原理

陈述只比较两个整数#

$n+1$ 个物件放入 $n$ 个盒子，则某个盒子至少有 $2$ 个。一般形式把下限从 $2$ 往上抬：多于 $kn$ 个物件放入 $n$ 个盒子，则某个盒子至少有 $k+1$ 个。$n$ 与 $k$ 都是正整数。$k=1$ 时，多于 $n$ 个物件，某个盒子至少有 $2$ 个，基本陈述就是这一档；$n+1$ 是刚刚越过 $n$ 的那个整数。每件物件落在恰好一只盒子里，没有一件同时落进两只，也没有一件留在外面。

它不指出是哪一个盒子，也不构造那一对物件。$13$ 个人分到 $12$ 个月，定理只说有一个月至少两个人，不说是哪一个月，也不留下两个人的名字。证明结束时，手里只有一句矛盾：「每只至多一个」装不下已经有的件数。存在性在这里是排除一种放法，不是交出一对样本。同一批物件可以有多种放法都发生重复，定理不在这些放法里挑一种。

「多于 $kn$」不能写成「不少于 $kn$」。恰好 $kn$ 个时，每只盒子正好 $k$ 个，做得到。这时没有一只盒子必须达到 $k+1$ 个。下限要抬到 $k+1$，件数至少得是 $kn+1$。一般形式没有另换一条原理，只是把「至多一个」换成「至多 $k$ 个」，总数的上界从 $n$ 换成 $kn$。

反证不打开盒子#

设物件有 $n+1$ 个，盒子有 $n$ 个。假若每只盒子至多 $1$ 个，总数至多是 $n$。可是 $n+1>n$，和上界矛盾。因此「每只至多一个」不成立，至少有一只盒子至少有 $2$ 个。反证到这里停。它不检查第一只盒子，也不列出配对。哪一只越界，可以随放法改变；越界这件事，不随放法改变。可以只有一只越界，也可以好几只一起越界。定理管的是「至少一只」，不是「恰好一只」。

一般形式是同一步。假若每只盒子至多 $k$ 个，总数至多是 $kn$。物件若多于 $kn$，就和这个上界矛盾，于是有一只盒子至少有 $k+1$ 个。少了「至多 $k$ 个」，上界 $kn$ 写不出来。少了「多于 $kn$」，矛盾也写不出来，因为恰好 $kn$ 时每盒 $k$ 个正好把上界用满。证明仍然不构造那 $k+1$ 件物件，也不说这样的盒子有几只。

换成函数，结论不变。放法就是从物件到盒子的函数。基本陈述等于：不存在从 $n+1$ 元集到 $n$ 元集的单射。单射要求不同物件进不同盒子，于是每只至多一件，总数至多 $n$，还是同一条反证。哈希页说的碰撞，就是这样的函数没有做成单射。函数的说法没有多给出一只盒子的名字。

十二个月只用来核对#

$12$ 个月是 $12$ 只盒子，$13$ 个人是 $13$ 件物件。$13=12+1$，必有两人同月。这里的同月是落进同一只盒子，不是同日，也不是同龄。十一个人可以分占十一个月，剩下两个人挤在最后一个月；也可以不止一个月发生重复。定理只排除一种全局放法：十二个人各占一月之后，第十三个人还能占到第十三个月。月份没有第十三只。

$25$ 个人仍用这 $12$ 只盒子。取 $k=2$，则 $2\times 12=24$，而 $2\times 12+1=25$。$25$ 多于 $24$，某个盒子至少有 $3$ 个，必有三人同月。$24$ 个人不够这句话。$24$ 正好可以每个月两人，没有任何一个月有第三个人。$24$ 与 $25$ 只差一个人，结论从「可以每盒两个」变成「必有一盒至少三个」。核对仍然不点名：不说哪一个月，不说哪三个人，也不说其余月份各有几个。一个月装下 $14$ 人、其余十一个月各 $1$ 人，总数仍是 $25$，同样满足「至少三人」。反证只禁止「每个月至多两人」。

再用基本陈述看这 $25$ 个人，只能得到较弱的一句：$25>12$，所以有一个月至少两人。这话真，但没有用上 $k=2$。要把下限说紧，应取使 $kn$ 仍小于物件数的最大正整数 $k$。$3\times 12=36$，$25$ 并不多于 $36$，不能把下限抬到 $4$。$36$ 个人可以每个月恰好三人，$37$ 才必有一个月至少四人。说紧之后，盒子里的下限就是这个最大的 $k$ 再加一。

有限只盒子装不下无限个#

物件有无限多个，盒子只有有限个，则某个盒子里有无限多个。假若每只盒子都只装有限个，有限多只这样的盒子并起来仍是有限集合。物件这边是无限的，两边对不上。因此「每只都有限」不成立，至少一只盒子里有无限多个。无限多个之中至少有两个，所以碰撞一定发生。盒子里有无限多个，比「至少两个」更强，两条都来自同一次反证，停在不同的强度上。证明仍不指出是哪一只。

盒子也可以无限多个。那时，这条有限陈述不再强迫碰撞。有限陈述里的 $n$ 是正整数，无限多只盒子写不出这个 $n$，也就写不出「每盒至多一个则总数至多 $n$」。正整数放进按正整数编号的盒子，第 $i$ 个放进第 $i$ 只，每只恰好一个，没有碰撞。这不是把有限陈述打穿了。「盒子只有 $n$ 只」在这里不成立，反证的上界没有地方写。无限只盒子也可以故意全部放进第一只。碰撞做得到，却不是被强迫的。两边都无限时，没有「多出一个」这种整数差。单射可以有，也可以没有。本页只在盒子个数是正整数时声称那个下限。

无限个键与有限个桶#

哈希页写：碰撞不可避免，括号里的理由是鸽巢原理，无限输入映射到有限输出。输入是键，输出是桶。键可以无限多个，桶只有有限个。上一节用得上：某个桶对应的键有无限多个，其中至少有两个不同的键进入同一只桶。这就是碰撞。所以那句话成立。成立是因为每一种从无限键集到有限桶集的函数都不是单射，不是因为某一只具体的函数写得不够散。在有限子集上看起来比较分散的函数也一样：定义域一旦无限、值域只有有限个桶，仍然有一只桶对应无限多个键。

这句话不告诉你哪一个桶碰撞，也不交出那两个键。本页不提供设计哈希的步骤，也不提供寻找碰撞的步骤。不挑选函数，不枚举键，也不对任何一个已经写好的函数去找一对输入。有限个键要另看个数。桶有 $n$ 只、键只有 $n$ 个时，可以每桶至多一个，碰撞不是必然。键到了 $n+1$ 个，基本陈述才说必有碰撞。哈希页那一句用的不是这个刚好多一个的有限版本。不要把它改写成：有限张表在还没放满之前就已经必然碰撞。没放满可以不碰撞。键的全体一旦无限，而桶只有有限个，则连「每桶只装有限个键」都做不到。

二十三不是必然#

「$23$ 人中约有一半概率生日相同」是概率陈述，不是本定理。概率问的是，在一种随机模型里，至少两人同日有多容易发生。常见的模型把日期当成同样可能，把各人当成彼此独立，再看这个事件的概率何时过半。过半是概率门槛。本定理没有概率，也没有「大约一半」。它只问还有没有一种放法，使所有人的日子两两不同。

把 $2$ 月 $29$ 日算进去，日期有 $366$ 个。前 $366$ 人仍可以每人一天，每盒至多一个，反证还没有矛盾。第 $367$ 人放进来，物件是 $366+1$，才在逻辑上必然有两人同日。不要把 $23$ 写成必然。$23$ 远小于 $367$。在 $23$ 个人那里，全部不同日的放法仍然存在。概率陈述比较的是这种放法有多容易碰上，不是说它在逻辑上已经消失。若不把闰日算进去，日期是 $365$ 个，必然要到第 $366$ 人，仍不是 $23$。两种数法只差要不要给闰日留一只盒子。可能性有多大属于概率，见 概率论。本页不把那个模型再乘一遍。

它不是拉姆塞定理#

拉姆塞定理要的是单色完全子图。边只用有限多种颜色来染，图一旦够大，就有一种颜色把一组点两两连满：那一组点之间的边全是同一种颜色。证明里会用到鸽巢。从一个点出发的边按颜色放进盒子，边数越过颜色种数所允许的上界时，某种颜色至少有那么多条。这一步是本页的一般形式。拉姆塞定理没有停在「某种颜色至少有两条边」。它要求这些边再组成完整的单色团。结论更强。

更强的结论不由本页送出。本页只保证某个盒子至少有 $k+1$ 个物件。物件之间还有没有第二层关系，鸽巢不管。把「至少有两条同色边」说成「已经有一张单色完全图」，是把个数下限误当成图的结构。本页不去算拉姆塞数。那些数问的是，多小的顶点集就已经强迫出指定的单色团。算出一个数，等于在某一档大小上把够与不够分开。本定理不回答这一档画在哪里。画在哪里，是 拉姆塞定理 那一页的事。

1834 没有那一年的出处#

不要说狄利克雷在 $1834$ 年发现了它。Rittaud 与 Heeffer 指出，这个年份常被引用，但没有那一年的出处。能对上文字的是另一年。狄利克雷在 $1842$ 年的逼近工作里使用了抽屉想法，讨论实数可以用有理数逼近到怎样的程度。当时他没有给这个想法命名，也没有宣称这是一条新原理。他后来才称之为 Schubfachprinzip。英文 pigeonhole 不是他的用词。鸽巢对应后来的英语说法，抽屉更靠近那个德文词。两条叫法都不要写成 $1834$ 年的发现宣言。本页标题用鸽巢原理。文中若写抽屉原理，指的也是这条个数比较，不是变分法里那条同姓的陈述。

Jean Leurechon 在 $1622$ 年的 Selectae Propositiones 里已有这类句子：必有两人头发根数相同。同一句还并列到金子和其他数量上，没有展开成上面的反证，也没有写成 $n+1$ 与 $n$。不能把 $1622$ 年说成现代定理的全文已经印出，也不能把 $1842$ 年说成第一次有人用这种强迫关系说话。两件事分开记。早先有人写出「必有两人相同」。狄利克雷在逼近里使用了抽屉想法，后来给了德文名字，并且没有把它称作自己的新原理。常被引用的 $1834$，缺的是那一年的出处。

变分法里的狄利克雷原理是另一句：能量泛函的最小值一定存在。黎曼在 $1851$ 年用它推进映照定理。$1870$ 年魏尔斯特拉斯给出反例，有下确界的泛函可以取不到最小值。对象是函数空间里的极值，不是有限只盒子里的件数。姓氏相同，只说明两条陈述都曾挂在狄利克雷名下。挂名不等于同一句话。本页不设 mathematician，也不设 year，避免把 $1842$ 年的使用、后来的德文命名，或那条被反例打开的变分存在性，收成一个人在某一年发现了鸽巢原理。

跨域连接#

• 组合数学：总览用 $13$ 个人里必有两人同月生来说明这条原理像常识，却能把存在性从逐个枚举里解放出来。本页把那句话拆成整数：$12$ 个月是盒子，$13$ 个人是物件，$13=12+1$，反证只比较 $n+1$ 与 $n$。总览还并列容斥、生成函数和双射，那些是在数一共有多少种放法。鸽巢不数放法的种数，只排除「每个盒子至多一个」这一种全局假设。$25$ 个人必有三人同月，是同一条一般形式在 $k=2$ 时的核对，不是另一条原理。读到计数公式时回到总览。留在这里，只核对存在性从哪一个整数开始，以及它为什么仍然不交出那两个人的名字。

• 哈希：哈希在计算机科学那一页。那里写碰撞不可避免，括号里点明无限输入映射到有限输出。本页说明这句话为什么成立：键可以无限多个，桶只有有限个，于是某个桶里有无限多个键，因而至少两个不同的键落入同一桶。这不告诉你是哪一只桶，也不告诉你是哪两个键。键的个数还不超过桶的个数时，可以不碰撞；哈希页那一句的前提是键的全体可以无限。设计哈希函数、处理已经发生的碰撞、寻找一对具体的键，都不是这条存在性陈述提供的步骤。本页不写这些步骤。

• 概率论：$23$ 人中约有一半概率生日相同，是概率陈述。它问随机放法下同日有多容易发生，不问是否还存在全体不同日的放法。把 $2$ 月 $29$ 日算进去，日期有 $366$ 个，前 $366$ 人可以每人一天，第 $367$ 人才在逻辑上必然同日。不算闰日则是 $365$ 个日期、第 $366$ 人，仍然远离 $23$。概率页承担样本空间里事件可能性有多大。本页没有随机模型，证明里也不出现大约一半。看见概率过半，离开这里。看见 $n+1$ 与 $n$，也不要把第 $367$ 人改写成一个概率。

• 变分法：那一页的狄利克雷原理说能量泛函的最小值一定存在。黎曼在 $1851$ 年用它推进映照定理，$1870$ 年魏尔斯特拉斯给出反例：有下确界可以永远取不到最小值。那是极值是否被取到的问题，对象在函数空间里。本页的对象是有限个盒子里的件数，证明是「至多 $k$ 个则总数至多 $kn$」这条整数上界。两件事都曾被人用狄利克雷的姓来称呼，结论不能互换。看见能量、下确界或极值，离开本页。看见抽屉或鸽巢，也不要去变分法里找一只盒子。本页标题只用鸽巢原理，不用那条变分陈述的名字做标题。

• 拉姆塞定理：拉姆塞定理要单色的完全子图。边只用有限多种颜色，图一旦够大，某种颜色就会自己把一组点两两连满。证明可以从一个顶点出发，把边按颜色放进盒子，再用本页把某种颜色的边数压过上界。这一步是鸽巢。定理没有停在这一步。它要求被压出来的那些边再组成完整的单色团，结论比某个盒子至少有 $k+1$ 个物件更强。拉姆塞数问多小的图就已经够。本页不去算那些数，也不把至少两件升级成一张单色完全图。读到颜色与完全子图时离开这里。

参考文献#

• Rittaud, Benoît, and Albrecht Heeffer. The Pigeonhole Principle, Two Centuries Before Dirichlet. The Mathematical Intelligencer, 2014. doi:10.1007/s00283-013-9389-1。这条文献用来分开两件事：Jean Leurechon 在 1622 年的 Selectae Propositiones 里已有必有两人头发根数相同这类句子；狄利克雷在 1842 年的逼近工作里使用抽屉想法，当时没有命名，也没有宣称这是新原理，后来才称之为 Schubfachprinzip。1834 这个年份常被引用，但没有那一年的出处。英文 pigeonhole 不是狄利克雷的用词。这里不编页码。
• Van Lint, J. H., and R. M. Wilson. A Course in Combinatorics. 2nd ed. Cambridge University Press, 2001。组合课程里的基本陈述可以放在这本书里核对：物件多于盒子按某个正整数 $k$ 给出的上界，则某只盒子至少再多一件。这里不编定理号。