鸽巢原理

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

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

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

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

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

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

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

给定任意 $n\ge 1$ 个整数 $a_1,\dots ,a_n$，令 $s_0=0$、$s_j=a_1+\cdots +a_j$。这 $n+1$ 个前缀和只有 $n$ 种模 $n$ 的余数，故有 $i<j$ 满足 $s_i\equiv s_j(\mathrm{mod}n)$。相减得到

因此必有一段非空连续子序列之和被 $n$ 整除。加入空前缀 $s_0$ 很关键：它既补足了鸽子的数量，也使“从第一项开始的片段”包含在差分表示中。例如 $n=4$、序列 $2,3,1,5$ 的前缀和为 $0,2,5,6,11$，其中 $s_1=2$ 与 $s_3=6$ 同余，找出的片段就是 $3+1=4$。

同样的做法还可把几何点按网格单元分类，以小单元限制两点距离；把输入前缀按自动机状态分类，则可找出进入同一状态的不同前缀。每次都需要说明“同巢”怎样转回题目要求的结论。

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