抽屉原理

Summary

抽屉原理，又称鸽巢原理（Pigeonhole Principle），常被用来做存在性证明以及求最坏情况下的解。文中给出两条基本形式：把 n+1 个物品放入 n 个抽屉，则至少有一个抽屉里装了不少于 2 个物品；更一般地，把 n 个物品放入 k 个抽屉，则至少有一个抽屉里的物品数不少于 n/k 向上取整。原理本身极其简单，却是大量构造题与反证法的出发点——只要物品的数目严格超过容器的数目，就必然出现有东西挤在一起的情形，据此便能断定某种结构或某种重复一定存在。

参考资料

• 抽屉原理 - OI Wiki

简介

抽屉原理，亦称鸽巢原理（Pigeonhole Principle）。

它常被用于存在性证明和求最坏情况下的解。

抽屉原理

将 $n+1$ 个物品放入 $n$ 个抽屉中，物品最多的抽屉中至少有 $2$ 个。

将 $n$ 个物品放入 $k$ 个抽屉中，物品最多的抽屉中至少有 $\lceil\frac{n}{k}\rceil$ 个。