鸽子洞原理

想象一群鸽子依偎在一套 $n$一致的。如果有 $n$鸽子，那么所有的鸽子都有可能在不同的鸽子洞里快乐地休息。但是，如果至少还有一只鸽子到达，总数就超过 $n$鸽子，那么至少有一个鸽子洞，不可避免地，最终会有不止一只鸽子。

鸽子比鸽子洞多需要鸽子洞有多于一只鸽子，这个想法看似微不足道，但事实证明，它足够重要，以至于有了一个名字:

鸽子洞原理(幼稚形式):

如果超过 $n$对象被放置在 $n$框，则至少一个框必须包含多个对象。

乍一看，鸽子洞原理(也称为狄利克雷原理为了纪念这位以自己名字命名的德国数学家)可能看起来太过明显而无用;的确，这一原则的力量来自于巧妙地选择“盒子”和“对象”。尽管原理本身很简单，但它是否有用，如果有用，如何有用，并不总是很清楚。例如，考虑下面的例子:

一个盒子里有三双袜子，分别是红色、蓝色和白色的。假设我看都不看就把袜子拿出来。我要拿出多少只袜子才能确保里面有一双配套的袜子?

---

如果我只拿 $2$或 $3.$袜子，有可能它们都是不同的。例如，它们可能是一个红色和一个蓝色;或者一红一蓝一白。但如果我取出 $4$袜子，这些必须包括一双配套的。在这里, $4$选择的袜子是“对象”和 $3.$颜色是“盒子”;根据PP1，它可以推断出四个被选的颜色中至少有两个是相同的，因此必须是匹配的一对。因此，拿出的袜子的最小数量是 $4$． $_ \广场$

一所学校需要多少学生才能保证至少有两个学生的首字母相同?

---

有 $26\乘26 = 676$用26个字母A, B, C，…， Z，所以学生人数应该大于676。因此，学生的最小数量是 $677$． $_ \广场$

在许多情况下，鸽子洞原理的“幼稚”形式可以直接应用。在大多数问题中，“对象”和“框”是相当明显的。

一个盒子里有三双袜子，分别是红色、蓝色和绿色的。如果没有看就选择了袜子，那么必须抽多少只袜子才能保证至少有一双匹配的袜子?

---

三个或更少的袜子的任何选择都可能只由不同的袜子组成。如果有三只袜子可供选择，那么一只红、一只蓝、一只绿的可能性就会降低。然而,如果四个袜子在选择时，鸽子洞原理确保两只袜子必须是一样的。每只袜子的颜色都是一个“盒子”，每只被画出来的袜子都是一个“对象”，要被归类到盒子里。如果是三个方框，则必须绘制三个以上的项目才能有两个匹配的项目。 $_ \广场$

注意，严格地说，必须始终验证是否 $n$(或更少)物体不适合 $n$盒子。鸽子洞原理保证了碰撞的发生更多的比 $n$物体被放置在 $n$盒子;但是，它没有指定是否 $n$或更少的物体可以放进去 $n$盒子，这当然可能不是真的，这取决于问题中给出的限制(想象一些鸽子不喜欢彼此，或者，也许，一些鸽子洞包含阻塞)。

一个学校 $n$学生。最小的是什么? $n$这样至少有两个学生的首字母和尾字母是一样的?

---

有 $26 \cdot 26 = 676$首字母和尾字母的明显组合。与 $676$同学们，给每个学生分配一组不同的首字母和尾字母当然是可能的。不过，根据鸽子洞原理，有了 $n = 677$学生保证至少两个学生必须有匹配的首字母。 $_ \广场$

给出一组 $n$正整数，存在一个非空子集它的和能被整除 $n$．

---

让 $n$整数表示为 $a_1, \ ldots an$．形成了 $n$总结

$\{对齐}开始S_1 & = a_1 \ \ S_2 & = a₁+ a₂ \\ &\ \, \ vdots \ \ S_n & = a_1 + \ cdots + an。结束\{对齐}$

如果这些和中的一个能被 $n$，那么我们就完成了。否则，根据鸽子洞原理，至少有两个和在除以时余数相同 $n$ $（$因为只有 $n - 1$可能存在明显的残余 $）.$选两个这样的数字 $S_i$而且 $S_j$, $>我$．接下来就是

$S_j - S_i = a_{i + 1} + \cdots + a_j$

一定能被 $n$． $_ \广场$

注意:如果 $一个$而且 $b$除以后余数相等吗 $n,$然后 $a - b$是整除 $n。$

一群统计学教授在晚宴上举行见面会。宴会开始后没有新客人进入，宴会结束前没有人离开。证明至少有两位教授与相同数量的不同的人握手。（提示:教授不能和自己握手。)

---

如果有 $n$教授们，那么每个人最多只能和他们握手 $n - 1$其他个人。此外，如果有个人与。握手 $n - 1$其他的人，那么就不存在一个人不为其他的人握手，反之亦然。换句话说，每个 $n$教授可以被认为是一个可以分类的对象 $n - 1$盒子根据不同的人握手的数量来划分。根据鸽子洞原理，它们之间至少存在一个整数 $1$而且 $n - 1$或 $0$而且 $n - 2$这相当于至少两位教授与不同个体握手的次数。 $_ \广场$

鸽子洞原理也可以应用于发生在“连续”空间上的问题，如果选择了一个巧妙的空间分区。

给定长度的线段 $l$包含 $n + 1$点,让 $d$是连续点之间最短段的长度。的最大值是多少 $d$除以所有可能的点构型?

---

首先，考虑点的一个简单配置。让所有的点均匀间隔，每段的两端各有一个点。在这种情况下，这些点将直线分成 $n$片段，每个片段的长度 $\压裂Ln$．

显然，我们不能做得比 $\压裂Ln$，但有可能做得更好吗?

乍一看，答案似乎是否定的。移动任何非端点都会增加一个内部线段的长度，但总是以缩短相邻线段为代价。

使用鸽子洞原理，我们可以这样处理这个问题:考虑每一个 $n$均匀间隔的片段作为一个“盒子”和每个 $n + 1$点作为一个项目放在盒子里。鸽子洞原理意味着至少一个盒子(或部分)必须有两个物品(或点)，这保证了两个连续的点之间的距离不能超过 $\压裂Ln$． $_ \广场$

十个点放置在一个单位等边三角形中。证明存在两个最多距离的点 $\压裂{1}{3}$分开。

---

考虑将三角形划分为9个等边三角形，如下图所示:

9个小三角形中的每一个都代表一个方框，十个点中的每一个都代表要放在方框中的物品。根据鸽子洞原理，九个三角形中至少有一个必须包含至少两个点。因为三角形中任意两点之间的最大距离是 $\压裂{1}{3}$在美国，这样的两点之间的距离不可能大于距离 $\压裂{1}{3}$． $_ \广场$

设一组正数的平均值为 $\μ$．使用鸽子洞原理来证明至少存在一个小于或等于的数字 $\μ$．

---

选择一套 $n$平均值为 $\μ$相当于放置 $n + 1$在长度线段上的点 $n \μ$有两个固定的端点。每一个 $n$在连续的点之间形成的段表示集合中的一个数。

此外，将整个段划分为 $n$sub-segments长度 $\μ$．因此鸽子洞原理意味着至少一个线段包含至少两个点，也就是说，必须至少有一个长度线段 $\μ$或更少。它立即得出至少有一个数字小于或等于 $\μ$． $_ \广场$

鸽子洞原理的更一般形式如下:

鸽子洞原理(一般形式):

如果超过 $k \ cdot n$对象被放置在 $n$那么至少一个盒子必须包含超过 $k$对象。

的情况下 $k = 1$对应于前面提到的朴素鸽子洞原理。

最后，让我们证明(广义)鸽子洞原理。这个论点相当直截了当。

为了矛盾起见，假设没有包含超过 $k$鸽子。在这种情况下，每个鸽子洞可能包含最多 $k$鸽子, $n$鸽子洞最多可以包含 $k \ cdot n$鸽子。但这与之前的假设相矛盾更多的比 $k \ cdot n$对象。因此，至少有一个盒子必须包含超过 $k$鸽子。 $_ \广场$

应该指出，矛盾只允许矛盾最弱的关于箱子里的东西，可以提出索赔。如果不是这样，那么每个盒子最多 $k$对象，唯一能确定的是至少有一个盒子里有至少还有一个比 $k$对象。

从标准套牌中抽出的最少牌数是多少，才能保证至少有三张相同花色的牌?

---

让这四套衣服对应我们的“盒子”。鸽子洞原理意味着，如果我们画了多于 $2 \ cdot 4$卡的 $4$西装，那么至少一套西装必须有多于 $2$画的卡片。

最后，我们应该注意到，在抽了8张牌的情况下，每种花色正好有两张牌是可能的，所以最小数量确实是 $9.\ _ \广场$

如果超过 $n$对象被分布到 $n$盒子，那么至少一个盒子必须有至少两个对象。

接下来要注意，如果每一个 $n$最多可装的箱子 $1$对象，只有这时 $n$箱子最多只能接收 $n$对象与假设相反，多 $n$物品被放进箱子里。

这一原则是由狄利克雷因此也被称为狄利克雷的原则或狄利克雷的抽屉原理．让我们把它应用到一些解决的例子中:

一个盒子里有三双袜子，分别是红色、蓝色和白色的。假设我看都不看就把袜子拿出来。我要拿出多少只袜子才能确保里面有一双配套的袜子?

---

如果我只拿出来 $2$或 $3.$袜子，有可能它们都是不同的。例如，它们可能是一个红色和一个蓝色;或者一红一蓝一白。但如果我取出 $4$袜子，这些必须包括一双配套的。在这里, $4$选择的袜子是“对象”和 $3.$颜色是“盒子”;根据PP1，它可以推断出四个被选的颜色中至少有两个是相同的，因此必须是匹配的一对。因此，拿出的袜子的最小数量是 $4.$ $_ \广场$

一所学校需要多少学生才能保证至少有两个学生的首字母相同?

---

有 $26\乘26 = 676$用26个字母A, B, C，…，Z. So by PP1, the number of students should be grater than 676, and thus the minimum number of students is $677.$ $_ \广场$

对于任何正整数 $n$而且 $t,$如果 $tn + 1$或者放入更多的对象 $n$盒子，那么至少一个盒子将包含超过 $t$对象。

如果每个盒子包含最多 $t$对象,那么 $n$盒子最多只能装 $tn$对象。这与事实相矛盾 $tn + 1$或者在盒子里放更多的东西。因此，至少一个盒子必须包含超过 $t$对象。 $_ \广场$

如果的平均值 $n$积极的数字是 $t$，那么至少有一个数字大于或等于 $t$．此外，至少有一个数字小于或等于 $t$．

让 $a_1,, \ ldots, an$是数字。然后通过数据

$\压裂{\ sum_ {i = 1} ^ n ai} {n} = t \意味着\ sum_ {i = 1} ^ = nt。\ n a_i qquad (1)$

因此，如果每个 $n$数字 $a_1,, \ ldots, an$小于 $t,$那么这些数的和将小于 $nt$矛盾的是, $(1)。$

类似的论证表明，至少有一个数字小于或等于 $t$． $_ \广场$

如果这些数字 $a_1,, \ ldots, an$都是整数，那么PP3说至少有一个是整数 $t \ \组\ lceil rceil$至少有一家是 $\ leq \ \ rfloor lfloor t$,在那里 $\ ceil \text{} \ ceil$而且 $\lfloor \text{} \rfloor$是天花板而且地板上功能,安排。

让 $q_1 q_2,…,q_n$是正整数。如果 $左(\ \ displaystyle \ sum_ {i = 1} ^ n q_i - n + 1 \右)$对象被放入 $n$盒子，要么第一个盒子包含至少 $q_1$对象，或者第二个框至少包含 $q_2$对象,……,或者是 $n ^ \文本{th}$这个盒子里至少装了 $q_n$对象。

假设我们分发 $左(q_1 + q_2 + \ \ cdots + q_n-n + 1 \右)$对象 $n$盒子。如果为每个 $我= 1,2,3,…,n$的 $我^ \文本{th}$盒子的容量小于 $q_i$对象，则对象的总数 $n$盒子是 $\ leq (q_1-1) + (q_2-1) + \ cdots + (q_n-1) = q_1 + q_2 + \ cdots + q_n-n。$

但是这个数字小于放在 $n$盒子。至少有一个 $我$, $我^ \文本{th}$盒子必须包含至少 $q_i$对象。 $_ \广场$