##### 鸽巢原理 - 鸽巢原理 - **鸽巢原理**粗略地说就是如果有许多鸽子飞进不够多的鸽巢内, 那么至少要有一个鸽巢被两个或多个鸽子占据, 或者说如果 $k+1$ 个或更多的物体放入 $k$ 个盒子, 那么至少有 $1$ 个盒子包含了 $2$ 个或更多的物体, 即一个从有 $k+1$ 甚至更多个元素的集合到 $k$ 个元素的集合的[[映射]] $f$ 不是一对一映射. 一般形式是如果 $n$ 个物体放入 $k$ 个盒子, 那么至少有一个盒子包含了至少 $\displaystyle\lceil\frac{n}{k}\rceil$ 个物体, 其中 $\displaystyle\lceil\cdot\rceil$ 是[[取整函数|向上取整函数]]. 相关有[[拉姆齐定理]]和[[霍尔婚配定理]] >[!example]- 鸽巢原理 >- 有 $13$ 个人, 他们的生日必须落在一年中的 $12$ 个月份中, 则至少有一个月有大于等于 $2$ 个人的生日 >- $100$ 张纸条放进 $9$ 个抽屉中, 则存在某个抽屉里至少有 $\left\lceil \frac{100}{9} \right\rceil = 12$ 张纸条 >- 任意 $6$ 个整数, 一定存在其中两个数, 其差是 $5$ 的倍数, 考虑整数模 $5$ 的余数, 只有 $5$ 种 $0,1,2,3,4$, 将 $6$ 个整数映射到这 $5$ 个余数, 则至少有两个数余数相同, 且差可被 $5$ 整除