鸽巢原理又称为 抽屉原理，它的描述十分简单，却能推出一些不那么显然的结论。

简单形式

定理1 把 个物体放入 个盒子中，至少有一个盒子包含两个或两个以上的物体。

PROOF 考虑反证法。假设所有盒子的物体都不超过 个，那么总的物体数量就 这显然与条件矛盾，于是原命题成立。

对于鸽巢原理而言，我们只能用它来断定有盒子里面有两个或两个以上的物体，而对于寻找这样的盒子则无任何帮助。下面是与鸽巢原理相关的两个简单的定理。

定理2 把 个物体放入 个盒子里并保证没有盒子是空的或者没有盒子被放入了多余 个的物体，那么每个盒子里恰好有一个物体。

鸽巢原理的形式较为显然，我们看一些例子。

例1 给定 个整数 证明存在满足 的整数 使得

PROOF 考察下面 个和式： 若其中某个和能整除 那么结论成立；假设这 个数和不整除 那么由鸽巢原理（余数最多有 种而一共有 个数 ）知存在 使得 这就表明了存在 使得 综合两种情况结论得证。

例2 某人有 周的时间备战一场比赛，他决定每天至少练习一次，但是为了不使自己过于疲劳他还决定任意连续的 天内练习次数不能超过 次。证明存在连续的若干天，在这些天里这个人恰好练习了 次。

PROOF 设 是他从第一天到第 天这 天练习的总次数，由于每天至少练习一次，因此数列 严格单调递增。由于任意连续的 天内练习次数不能超过 次，因此 于是 那么对于下面这不大于 的 个数： 由鸽巢原理知其中至少有两个数相等，而 之间互不相等， 之间也互不相等，于是存在 使得 因此在第 天到第 天内，这个人练习次数恰好为

例3 从整数 中选出 个整数，证明在所选的整数中存在 使得

PROOF 这个问题可以转化为：从 对夫妻中选出 个人，这 个人中至少有一对为夫妻，而这由鸽巢原理知显然成立（若再煞有介事的证明一下的话，可以这样：将这 对夫妻与 个盒子对应，再把取出的 个人放到对应的盒子里，显然有一个盒子有两个人，这两个人是夫妻）。于是在这些整数中，可以把 看作一对夫妻，于是原命题显然成立。

另一种证明方法：这 个整数都可以写成 的形式，显然 一定是奇数且 也即一共有 个奇数，那么由鸽巢原理知取出的 个整数中一定有两个数的 是相等的，设这两个数为 显然两者其中一个可以整除另一个。

例4 证明 总可以写成十进制循环小数。

PROOF 只需要考虑 的情况（ 时化为真分数即可）。把 写成十进制小数的过程实际上为下面的带余除法： 其中 得到的小数是 下面证明从某个 开始， 为循环数列。由于余数 满足 则由鸽巢原理知在 中存在 使得 于是 这表明了 都有 因此 是周期为 的循环数列，且 于是 也为周期为 的循环数列，这就证得了 总可以写成十进制循环小数。

加强形式

定理3 设 是正整数，若将 个物体放入 个盒子中，那么对于所有的条件 第 个盒子至少存在 个物体，它们之中至少有一个成立。

PROOF 仍然考虑反证法。假设对每个 第 个盒子含有的物体数目小于 那么所有物体数便不超过 这与题设条件矛盾，于是原命题成立。

令 即可得到简单形式的鸽巢原理。

推论1 若把 个物体放入 个盒子中，那么至少存在一个盒子，它里面至少有 个物体。

PROOF 即得。

换种表述方式：若 个非负整数的平均数大于 那么至少有一个整数大于

例6 证明实数序列 要么含有长度为 的递增子列，要么含有长度为 的递减子列。

PROOF 假设它不含有长度为 的递增子列，我们来证明它存在长度为 的递减子列。对任意 设 是从 开始的最长的递增子列的长度，则在假设的条件下有 数列 共有 项，于是由推论 知道存在 个数 使得 下面我们证明 考虑反证法，假设存在某个 使得 那么以 开始的最长的自增子列的长度 这与 矛盾，于是 因此子序列 就是我们要找的长度为 的递减子列。而另一种情况同理。

定理

这是鸽巢原理的一个扩展。

定理4 （ 定理） 给定 则存在一个无向完全图 使得在给 的各边用红色和蓝色进行着色后，能找到一个一个 子图或一个 子图，这个子图的所有边同时为蓝色或红色，这简记为

在给出这个定理的证明之前，我们先证明 的情形。

PROOF 在涂过色的 中取一顶点 由鸽巢原理知与 相连的 条边中，至少有 条边是同一种颜色，不妨设边 是红色（蓝色同理），若 存在红色的边，不妨设为 那么以 为顶点的 的所有边都为红色；若边 都为蓝色，那么以 为顶点的 的所有边都为蓝色。这两种情况就表明了存在三边同色的 子图。

描述得更通俗一点就是：在认识关系为双向的前提下（这确保了关系图是无向的），六个人中一定存在三个人互不认识或存在三个人互相认识。

下面我们来证明 定理。

PROOF 考虑对变量 使用双重归纳法。

首先证明 与 存在。

定理中，使 成立的最小的数 称作 数，记作 在上述证明过程中，我们得到了

练习

1：证明：若从集合 中选择 个整数，那么总存在两个整数，它们之间最多差

2：证明对任意给定的 个整数，存在两个整数使得两者的和或差可以被 整除。

3：若从 中选择 个整数，且所选的这些整数中有一个小于 那么在这些整数中存在 使得

4：证明对任意 个整数 存在两个整数 使得

5：在边长为 的正方形内任意选 个点，证明存在两个点，它们之间的距离至多为