鸽子洞原理
试想一群鸽子依偎在一群 一致的。如果有 鸽子,那么所有的鸽子都有可能在不同的鸽子洞里快乐地休息。然而,如果至少再来一只鸽子,那么总数就超过 鸽子,那么至少有一个鸽子笼,不可避免地会有不止一只鸽子。
有更多的鸽子比鸽子洞的想法,需要一个有不止一只鸽子的鸽子洞,这似乎是微不足道的,但事实证明,它足够重要,以至于有了一个名字:
鸽子洞原理(朴素形式):
如果超过 对象被放入 ,则至少有一个框必须包含多个对象。
乍一看,鸽子洞原理(亦称狄利克雷原理以纪念德国数学家的名字命名)可能显得太明显而无用;事实上,这一原则的力量来自于对“盒子”和“对象”的巧妙选择。尽管原理本身相当简单,但它是否有用,如果有用,又是如何有用,并不总是很清楚。例如,考虑下面的例子:
一个盒子里有三双袜子,分别是红色、蓝色和白色的。假设我看都没看就把袜子拿出来。我要拿出多少只袜子才能确保里面有一双相配的?
如果我只取 或 袜子,有可能它们都是不同的。例如,它们可能是一红一蓝;或者一个红,一个蓝,一个白。但是如果我取出 袜子,这些必须包括一双配套的袜子。在这里, 选择的袜子是“对象”和 颜色是“盒子”;根据PP1,四个被选中的颜色中至少有两个是相同的,因此必须是一对匹配的。因此,拿出袜子的最小数量是 .
一所学校需要多少学生才能保证至少有两名学生名字的前两个首字母相同?
有 用26个字母A, B, C,…, Z,所以学生人数应该大于676。因此,学生的最小数量是 .
朴素鸽子洞原理
在许多情况下,鸽子洞原理的“朴素”形式可以直接应用。在大多数问题中,“对象”和“盒子”是相当明显的。
一个盒子里有三双袜子,分别是红色、蓝色和绿色的。如果袜子是不看就选的,那么要抽出多少只袜子才能保证至少有一双是相配的?
任何三个或更少袜子的选择都可能只由不同的袜子组成。给你三支袜子,一只红色、一只蓝色和一只绿色袜子的可能性很小。然而,如果四个袜子如果被选中,鸽子洞原则保证了两只袜子必须是一样的。每只袜子的颜色都是一个“盒子”,每只画出来的袜子都是一个“对象”,要被分类到盒子里。对于三个方框,必须绘制三个以上的项目才能有两个匹配的项目。
注意,严格地说,必须始终验证if (或更少)对象不适合 盒子。鸽子洞原理保证了在某些情况下会发生碰撞更多的比 对象被放置在 盒子;然而,它并没有指明是否 或更少的物体可以放入 盒子,根据问题中给出的限制条件,这当然不可能是正确的(想象一些鸽子彼此不喜欢,或者一些鸽子洞包含堵塞)。
一所学校 学生。最小的是什么 至少有两个学生的首字母和姓氏首字母是一样的?
有 首字母和尾字母的明显组合。与 学生们,当然可以给每个学生分配一组不同的首字母和尾字母。不过,根据鸽子洞原理,有了 Students保证至少两个学生的首字母必须匹配。
给出一组 正整数,存在一个和能被整除的非空子集 .
让 整数表示为 .形成了 总结
如果其中一个和能被 ,那么我们就完成了。否则,根据鸽子洞原理,当除以时,至少有两个和必须有相同的余数 因为只有 不同的剩余是可能的 挑两个这样的数字 而且 , .接下来就是
必须能被 .
注意:如果 而且 除以余数是一样的吗 然后 能被
一群统计学教授在晚宴上举行了见面会。宴会开始后没有新客人入场,直到宴会结束才有人离开。证明至少有两位教授握了相同数量的不同的人的手。(提示:教授不能自己握手。)
如果有 教授们,那么每个人最多只能和他们握手 其他个人。此外,如果有个人和 其他个体,那么就不存在一个人不为其他个体握手,反之亦然。换句话说,每一个 教授可以被认为是一种可以被分类的对象 箱子的数量由不同的人的手挥动。根据鸽子洞原理,两者之间至少存在一个整数 而且 或 而且 这相当于至少两位教授握手的人数。
连续空间上的鸽子洞原理
鸽子洞原理也可以应用于发生在“连续”空间上的问题,如果选择了一个巧妙的空间分区。
给定一个长度的线段 包含 点,让 为连续点之间最短段的长度。的最大值是多少 在所有可能的点的配置上?
首先,考虑一个简单的点配置。让所有的点均匀地间隔,每个点在段的两端。在本例中,这些点将直线分成 段,每个段的长度 .
显然,我们不能做得比 ,但有可能做得更好吗?
乍一看,答案似乎是否定的。移动任何非端点都会增加一个内部段的长度,但总是以缩短相邻段为代价。
利用鸽子洞原理,我们可以这样处理这个问题 等距段作为一个“盒子”和每个 点作为一个项目,以放置到盒子。鸽子洞原理意味着至少一个盒子(或段)必须有两个项目(或点),这保证了两个连续的点之间的距离不能超过 .
十个点被放置在一个单位等边三角形内。证明存在两个距离最大的点 分开。
考虑将三角形分成九个等边三角形,如下图所示:
九个小三角形中的每一个都代表一个盒子,十个点中的每一个都是要放入盒子中的物品。根据鸽子洞原理,九个三角形中至少有一个至少包含两个点。因为这些三角形中任意两点之间的最大距离是 ,这样的两点之间的距离不能大于距离 .
设一组正数的平均值为 .使用鸽子洞原理来证明至少存在一个小于或等于的数字 .
选择一套 这些数字平均为 就相当于放置 长度线段上的点 用两个固定的点作为端点。每一个 在连续的点之间形成的段表示集合中的一个数字。
进一步,将整个段划分为 长度分段 .鸽子洞原理意味着至少一个线段包含至少两个点,也就是说,必须有至少一个长度的线段 或更少。立即得出至少有一个数字小于或等于 .
广义鸽子洞原理
鸽子洞原理的一般形式如下:
鸽子洞原理(一般形式):
如果超过 对象被放入 则至少有一个框必须包含多个 对象。
的案例 对应于前面提到的朴素鸽子洞原理。
最后,让我们证明(广义的)鸽子洞原理。这个论点相当直截了当。
为了矛盾起见,假设没有盒子包含超过 鸽子。在这种情况下,每个鸽子洞最多可以包含 鸽子,还有所有的东西 鸽子洞最多可以包含 鸽子。但这与存在的假设相矛盾更多的比 对象。因此,至少有一个框必须包含超过 鸽子。
应当指出,矛盾只允许最弱的就箱子里的东西提出索赔。如果不是这样的话,每个盒子最多 对象,唯一能确定的就是至少一个盒子里有至少还有一个比 对象。
从一副标准牌中抽出的最少牌数是多少才能保证至少有三张相同花色的牌?
让四种花色对应我们的“盒子”。鸽子洞原理表明,如果我们画的比 卡片来自 花色,那么至少有一种花色必须多于 画的卡片。
最后,我们应该注意到,抽到八张牌时,每种花色可能刚好有两张牌,所以最小数目确实是
鸽子洞原则-解决问题
鸽子洞原理(PP1)
如果超过 对象被分布到 盒子,那么至少一个盒子必须有至少两个对象。
接下来要注意的是,如果每一个 最多装的箱子 对象,才有了 箱子最多能收到 对象与假设相反的多 物品被放进箱子里。
这一原则最初是由狄利克雷因此也被称为狄利克雷盒原理或狄利克雷抽屉原理.让我们把它应用到一些例子中:
一个盒子里有三双袜子,分别是红色、蓝色和白色的。假设我看都没看就把袜子拿出来。我要拿出多少只袜子才能确保里面有一双相配的?
如果我只取出 或 袜子,有可能它们都是不同的。例如,它们可能是一红一蓝;或者一个红,一个蓝,一个白。但是如果我取出 袜子,这些必须包括一双配套的袜子。在这里, 选择的袜子是“对象”和 颜色是“盒子”;根据PP1,四个被选中的颜色中至少有两个是相同的,因此必须是一对匹配的。因此,拿出袜子的最小数量是
一所学校需要多少学生才能保证至少有两名学生名字的前两个首字母相同?
有 用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
第二种鸽子洞原理(PP2)
对于任何正整数 而且 如果 或者放入更多的物体 框,则至少有一个框将包含多个 对象。
如果每个盒子里最多 对象,那么 盒子最多包含 对象。这与事实相矛盾 或者在盒子里放更多的东西。因此,至少有一个盒子必须包含超过 对象。
第三种鸽子洞原理(PP3)
第四种鸽子洞原理(PP4)
让 是正整数。如果 对象被放入 盒子,或者第一个盒子至少包含 对象,或者第二个框至少包含 对象,……,或 盒子里至少有 对象。
假设我们分配 对象 盒子。如果对于每一个 的 方框的容量小于 对象,那么对象的总数 盒子是
但是这个数字小于放置在 盒子。至少有一个 , 盒子必须至少包含 对象。