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