# Ⅳ：抽屉原理简介
本文介绍**抽屉原理**（也叫**鸽巢原理**，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$$ 个，所以至少会有两个人，他们跟别人握手的人数数量是一样的。