鸽巢原理/抽屉原理
鸽巢原理（Pigeonhole Principle），又称抽屉原理，是组合数学中一个重要的原理。以下将从其基本概念、常见形式、证明方法、应用示例几个方面进行详细介绍：
基本概念
鸽巢原理的基本思想是：如果有比鸽巢数量更多的鸽子，那么必然至少有一个鸽巢里会有两只或更多的鸽子。这个原理虽然表述简单，但却有着广泛的应用。
常见形式
- 简单形式
- 内容：如果把 n+1 个物体放入 n 个抽屉中，那么至少有一个抽屉里会放有两个或更多的物体。
- 示例：假设有 4 个鸽巢，养鸽人养了 5 只鸽子，那么当鸽子飞回巢中后，至少有一个鸽巢里有 2 只或 2 只以上的鸽子。
- 一般形式
- 内容：设 q1,q2,⋯,qn 是正整数。如果将 q1+q2+⋯+qn−n+1 个物体放入 n 个抽屉内，那么或者第一个抽屉至少含有 q1 个物体，或者第二个抽屉至少含有 q2 个物体，……，或者第 n 个抽屉至少含有 qn 个物体。
- 假如有 3 个抽屉（n=3），q1=2，q2=2，q3=2 ，那么 q1+q2+q3−n+1=2+2+2−3+1=4 ，也就是有 4 个东西要放进 3 个抽屉。
- 对于每个抽屉 i（i=1,2,⋯,n），我们先假设它里面有 qi−1 个物体。这是一种尽量不满足“第 i 个抽屉至少有 qi 个物体”的放置方式。
那么 n 个抽屉里物体的总数最多就是 (q1−1)+(q2−1)+⋯+(qn−1) ，根据去括号法则，展开可得 (q1+q2+⋯+qn)−n 。
但是，这样的放置方式并不能满足题目要求。当我们再增加 1 个物体时，也就是放入 (q1+q2+⋯+qn)−n+1 个物体时，无论把这个物体放到哪个抽屉，都会使得对应的那个抽屉里的物体数量达到或超过 qi 个。
所以，就得到了公式：如果将 q1+q2+⋯+qn−n+1 个物体放入 n 个抽屉内，那么或者第一个抽屉至少含有 q1 个物体，或者第二个抽屉至少含有 q2 个物体，……，或者第 n 个抽屉至少含有 qn 个物体。 - 特殊情况：当 q1=q2=⋯=qn=k 时，q1+q2+⋯+qn−n+1=nk−n+1=n(k−1)+1，即如果把 n(k−1)+1 个物体放入 n 个抽屉中，那么至少有一个抽屉里有 k 个物体。
- 示例：把 16 个苹果放入 5 个抽屉，因为 16=5×(3−1)+6，这里 n=5，k=4，16=5×3+1，根据鸽巢原理，至少有一个抽屉里有 4 个或 4 个以上的苹果。
- 平均形式
- 内容：如果 n 个非负整数 m1,m2,⋯,mn 的平均数 nm1+m2+⋯+mn>k−1（k 是整数），那么至少有一个整数大于或等于 k。
- 示例：在一次考试中，某班 30 名学生的平均成绩为 85 分。因为 85>84，根据平均形式的鸽巢原理，至少有一名学生的成绩不低于 85 分。
证明方法
以简单形式为例，采用反证法证明：
假设每个抽屉里最多只有 1 个物体，那么 n 个抽屉里最多只能放 n 个物体。但现在有 n+1 个物体，这与已知条件矛盾。所以，至少有一个抽屉里会放有两个或更多的物体。
应用示例
- 生日问题
- 问题描述：在一个 367 人的群体中，至少有两个人的生日相同。
- 分析：一年最多有 366 天（闰年），可将这 366 天看作 366 个“抽屉”，367 个人看作 367 个“物体”。根据鸽巢原理，把 367 个物体放入 366 个抽屉中，至少有一个抽屉里有两个或更多的物体，即至少有两个人的生日相同。
- 选举问题
- 问题描述：在任意 6 个人的集会上，或者有 3 个人以前彼此相识，或者有 3 个人以前彼此不相识。
- 分析：把 6 个人看作 6 个点 A1,A2,⋯,A6。如果两个人彼此相识，就把代表这两个人的点之间的连线染成红色；如果两个人彼此不相识，就把代表这两个人的点之间的连线染成蓝色。那么，问题就转化为证明在这个完全图 K6 中，一定存在一个红色 K3（即三个点两两之间的连线都是红色）或者一个蓝色 K3（即三个点两两之间的连线都是蓝色）。从任意一个点 A1 出发，有 5 条连线，根据鸽巢原理，这 5 条连线中至少有 3 条同色。不妨设 A1A2，A1A3，A1A4 这三条连线都是红色。如果 △A2A3A4 的三条边也都是红色，那么就找到了一个红色 K3；如果 △A2A3A4 的三条边中至少有一条是蓝色，比如 A2A3 是蓝色，那么 A2A3A4 就是一个蓝色 K3。