鸽巢原理

鸽巢原理并不依赖对象是什么，只比较分类前后的容量。证明问题时，真正有创造性的部分通常不是最后一句“所以发生碰撞”，而是选择一个合适的分类函数：哪些对象当作鸽子，哪些不变量当作巢，以及每个巢最多能容纳多少对象。

它给出的是存在性。若对象多于可区分状态，就必有两个对象落入同一状态；但原理本身不会指出是哪两个，也不会给出高效寻找方法。算法若需要实际找到碰撞，还必须利用对象的表示、排序或搜索结构。

强化形式可以理解为平均数的离散版本。平均占用量是 $N/k$，因此最大占用量不可能低于其上取整。这个结论比“至少两个同巢”更适合极值问题，因为它直接给出某类中必须聚集多少对象。

把 $n+1$ 个整数按模 $n$ 的余数分类。余数只有 $0,1,\dots ,n-1$ 共 $n$ 种，所以必有两个整数同余；它们的差可被 $n$ 整除。这里选择余数作为巢，把一个数论整除结论转成有限分类碰撞。

任意简单图中，所有顶点的度数落在 $0,1,\dots ,n-1$ 之间，但度数 $0$ 与 $n-1$ 不可能同时出现：若有一个顶点连接所有其他顶点，就不存在孤立点。因此实际可出现的度数至多 $n-1$ 种，$n$ 个顶点中必有两个度数相同。这个例子显示，“巢数”有时来自额外结构，而不是表面上的取值范围。

边界必须精确。$n$ 个对象放入 $n$ 个容器并不强迫碰撞，因为双射可以让每个容器恰好一个对象。即使对象更多，鸽巢原理也只保证至少一个拥挤容器，不自动给出拥挤容器的数量、碰撞对数或分布形状。

无限集合中不能只比较“看起来更多”。自然数与偶数之间存在双射，所以把无限多个对象放进无限多个容器时，有限版容量直觉可能失效。此时必须使用基数公理库基数Cardinality · Size of a set忽略元素性质与排列，只用双射和单射刻画集合的大小及其比较。、测度或密度等更精细工具。

在组合数学中，鸽巢原理常与排序、前缀和和模分类结合。把前缀和按模 $n$ 分类，可推出某段连续子序列之和被 $n$ 整除；把几何对象按网格单元分类，可推出两个点距离很近；把字符串前缀按自动机状态分类，可推出循环或重复段。

在计算机科学中，有限哈希空间接收更多键时必然发生哈希冲突；有限状态机运行足够久后必然重复状态；固定长度摘要无法为无限消息提供无碰撞编码。这些都是同一容量事实，但实际安全性或算法性能还取决于碰撞是否容易构造、分布是否均匀以及系统如何处理冲突。