抽屉原理

Pigeonhole Principle

本文介绍抽屉原理（也叫鸽巢原理，Pigeonhole Principle）。

在之前的内容里，我们不少用到了抽屉原理的思想。

例如在融合待定数组里，我们知道因为有 $n$ 个单元格里要填入 $n$ 种不同的数字，因为数字不能出现重复项，因此每一种数字都必须出现恰好一次；更进一步地，由于存在 $n$ 种数字要填入到 $n + 1$ 个单元格里，所以为了确保数字均能填入，有一种数字必须出现两次才能满足条件。

另外，数组的显隐性互补里我们也知道，由于两个数组互补，他们只能位于同一个区域下，所以规格的和一定是小于等于 9 的。所以不论哪一个超过 5，则必有另外一侧互补的数组的规格小于 5，因此数组实际做题中是不存在五数组及以上规格的情况的。

这种用法参考和借鉴了抽屉原理的主旨思想。

基础定义

这个说法起源自狄利克雷（Dirichlet），就是提出那个狄利克雷函数的那个人。这个人是德国一名数学家，它最初将问题描述成这样：

若有 $n$ 个笼子和 $n + 1$ 只鸽子，如果所有的鸽子都会被关进鸽笼里的话，那么至少会有一个笼子里会有两只鸽子。

这个例子里，它是显然的。因为鸽子要关进去，每一个笼子都分配最少一只鸽子，怎么着都会剩下一只鸽子尚未归入笼子里。所以它必须放入任何一个已经有一只鸽子的笼子里去，所以这便就有了这个结论。

使用场景

问题 1：鸽巢原理推广

假设我们把前面的例子稍加改动。如有 $n$ 个笼子和 $kn + 1$ 只鸽子（其中 $k$ 是整数）。因为每一只鸽子都需要进笼，所以最次的分配方式是每一个笼子逐个让鸽子进去，一个一个地用完全部的笼子。用完之后继续让鸽子从第一个笼子开始，保证笼子内的鸽子数量尽量少地去分配。那么这样分配下来，$kn$ 只鸽子就刚好用完全部所有的笼子 $k$ 次。

于是，我们再多加一只鸽子进去，不论加在哪一个笼子，笼子里都会多一只鸽子。原本全部都是 $k$ 只，现在肯定就变成了 $k + 1$。所以，如果鸽子数量是 $kn + 1$ 的话，则必有至少一个笼子会有 $k + 1$ 只鸽子。

问题 2：发量问题

一个正常人的头发数量是 10 万根左右。倘若我们不让这个数过大（比如一个人有 100 万根头发什么的），那么，像是北京这样的城市里，由于人口数显然超过 100 万，所以必然能找得到两个人会有完全相同的发量。

问题 3：握手问题

如果有一个派对里有 $n$ 个人（假设 $n \ge 2$）。我们随意地让这些人进行两个人互相握手的操作。因为每一个人最终握手的次数都介于 $[0, n - 1]$ 这个区间内（就是说要么不握手，要么跟 1 个人握，要么 2 个人握手，这么一直下去，最多可以是跟其他所有 $n - 1$ 人都握过手）。但是，总的人数却有 $n$ 个，所以至少会有两个人，他们跟别人握手的人数数量是一样的。