6.3 鸽巢原理
第 6.2 节计算排列或选择一共有多少种可能。鸽巢原理回答另一类问题：无论安排得多么巧妙，什么时候重复分配都不可避免？
它只需要很少的信息。我们常常不必知道哪一次碰撞发生，只需证明某次碰撞一定存在。
基本鸽巢原理
如果把多于 个对象放入 个盒子，那么至少有一个盒子包含至少两个对象。
传统名称是：
- 对象称为鸽子；
- 盒子称为鸽巢。
对象和盒子可以代表任何事物。
反证
假设没有盒子包含两个对象。于是 个盒子各自至多有一个对象，全部盒子合起来至多容纳
个对象。
但前提说对象数多于 ，产生矛盾。因此某个盒子至少包含两个对象。
这个证明也说明为什么必须严格多于。把恰好 个对象放入 个盒子，可以每盒一个而不碰撞。
建模是主要挑战
应用原理时要识别：
1. 被分配的对象是什么；
2. 代表可能类别的盒子是什么；
3. 为什么每个对象恰好属于一个盒子；
4. 为什么对象数超过盒子数。
示例：出生月份
人中至少有两人在同一个月出生。
- 鸽子： 个人；
- 鸽巢： 个月份；
- 分配：每个人进入自己的出生月份。
因为
所以必然有共享月份。
原理不告诉我们是哪一个月或哪两个人，它证明的是存在性。
示例：余数
选择 个整数。每个整数除以 后，余数属于
之一。
有 个整数和 个剩余类，所以两个所选整数具有相同模 余数。
若两个整数为 ，则
这把鸽巢原理与第 4.3 节的等价类连接起来。
函数视角
把对象分入盒子会定义一个函数
其中 是鸽子集合， 是鸽巢集合。
如果
那么 不可能是单射。因此存在不同鸽子 满足
所谓“碰撞”，正是单射失败。
常见错误
鸽巢原理本身简单，但模型可能出错。
- 类别重叠会让一个对象没有唯一盒子；
- 遗漏可能类别会让鸽巢数偏小；
- 鸽子与鸽巢数量相等时不强制碰撞；
- 结论只保证至少一个拥挤盒子，不表示每个盒子都拥挤。
例如， 人与 个月份保证共享月份，却不保证每个月都有人出生。
把代币发射进类别传送门，对手会尽力避免所有碰撞。你可以选择鸽巢数量和放置策略；街机将找出单射不再可能的准确发射时刻，并给出发生碰撞的一对见证。
广义鸽巢原理
基本原理保证某盒至少有 个对象。对象更多时，可以保证更大的负载。
如果把 个对象放入 个盒子，那么某个盒子至少包含
个对象。
符号 表示 的上取整：大于或等于 的最小整数。
例如，
所以把 个对象放入 个盒子，会保证某盒至少有 个对象。
为什么上取整界不可避免
令
假设每个盒子至多含 个对象，那么 个盒子合起来至多包含
个对象。
因为 ，所以
与全部 个对象都已放入矛盾。因此至少一个盒子含 个对象。
平衡分配说明保证是紧确的
写成
可以这样分配：
- 个盒子各放 个；
- 剩下 个盒子各放 个。
最大负载为
所以一般不能提高这个保证。
对 ，
最平衡分配的负载为
至少一个盒子必须达到 ；这个安排也说明没有盒子被迫达到 。
反向求保证数量
要保证 个盒子中某盒至少有 个对象，先问：保持每盒至多 个时，最多能放多少对象？
最大值是
再增加一个对象，就会强迫目标负载：
示例：保证四只同色袜子
袜子有 种颜色。至少选多少只，才能保证某颜色有 只？
在不达到 的前提下，每种颜色至多选 只，共
只。
下一只必然使某颜色达到 ：
数据与算法中的应用
有限资源接收大量项目时，广义原理经常出现：
- 把哈希键放入表桶；
- 把请求分配给服务器；
- 把学生分入时间段；
- 按余数给整数分组；
- 把文件存入固定类别。
它给出最佳可能最大负载的下界。即使负载均衡算法完美，也不可能把 个任务分到 台服务器，并让每台负载都小于 。
扮演调度员，在任务到达时尽量降低最忙服务器的负载。对手会改变到达数量与服务器数；实时下界把你的分配与最优平衡模式比较，并揭示所要求的最大负载什么时候根本不可能。
本节衔接
鸽巢原理从总数量推出局部行为不可避免。最后一节将回到重叠集合与重复代数选择的精确计数。二项式系数会组织展开式，容斥原理会修复第 6.1 节留下的重叠问题。