鸽巢原理是什么?鸽巢原理在数学中的巧妙应用

橘子网 6,509 0

很多时候,常识里往往蕴含着大道理。

在数学中,有一些看上去由于过于显然,以致显得不是那么重要的观点,却因为内有乾坤而受到了很多数学家的重视,我们所熟知的“鸽巢原理”(Pigeonhole Principle)就是其中之一。

鸽巢原理是什么?鸽巢原理在数学中的巧妙应用

鸽巢原理能够用来解决很多有趣的问题,经常还会得到一些出人意料的结论,其影响力堪比德国数学王子高斯的配对技巧。

一、基本原理

鸽巢原理又称“鸽笼原理”、“抽屉原理”或“鞋盒原理”。为了纪念19世纪德国著名的数学家和物理学家狄利克雷(Peter Dirichlet,1805~1859年)在解决数论问题的证明中首先使用这个原理,鸽巢原理也被称作“狄利克雷原理(Dirichlet Principle)”。

鸽巢原理是什么?鸽巢原理在数学中的巧妙应用

鸽巢原理可以简单地表述为:假如你拥有的鸽子比鸽笼要多,当你准备把这些鸽子放入这些鸽笼时,至少有一个鸽笼里要装进最少两只鸽子。

比如:有10只鸽子,要放入9个笼子,那么无论如何,至少有一个笼子里要装进最少2只鸽子。

鸽巢原理是什么?鸽巢原理在数学中的巧妙应用

我们可以一般化地得到抽屉原理1:如果把n+1个物体放入n个盒子中,则至少有一个盒子中有两个或者更多的物体。

这个原理很容易通过反证法证明得到。假如这n个盒子中的每一个最多只含有一个物体,那么这些物体的总数量最多就是n,与我们有n+1个物体的前提条件相矛盾,所以至少有一个盒子中有两个或者更多的物体。

这里需要进一步说明的是,鸽巢原理及其证明对于找出具体是哪个盒子里含有两个或更多的物体并没有任何帮助。它只是简单地告诉我们,一定会存在某个盒子里面放有多个物体。鸽巢原理只是一个证明存在性的数学原理。

另外,当只有n个或者更少的物体时,我们是无法确保鸽巢原理的结论必然成立的,因为我们可以在n个盒子的每一个里面放进一个物体。因此,鸽巢原理只是断言无论我们在n个盒子中如何分配n+1个物体,总是无法避免将两个物体放入同一个盒子之中的。

再比如:有19只鸽子,要放入9个笼子,那么无论如何,至少有一个笼子里要装进最少3只鸽子。

鸽巢原理是什么?鸽巢原理在数学中的巧妙应用

同样,我们可以一般化地得到抽屉原理2:如果把m×n+1个物体放入n个盒子中,则至少有一个盒子中有m+1或更多的物体。

这里,我们同样可以用反证法证明得到,假如这n个盒子中的每一个最多只含有m个物体,那么这些物体的总数量最多就是m×n,与我们有m×n+1个物体的前提条件相矛盾,所以至少有一个盒子中有m+1或更多的物体。

鸽巢原理看上去是那么地显而易见,小朋友们不需要具备多少数学知识就可以理解和接受。然而,鸽巢原理在实际应用时却是知易行难,但如果我们能够灵活加以应用的话,就会得到一些意想不到的结果。而且,在历年不同级别的国内外数学竞赛中,与鸽巢原理有关的试题也是频繁出现,鸽巢原理对解决很多问题起到了至关重要的作用。

在后面的文章里,我们将会看到,其实在鸽巢原理的背后隐含着重要的数学思维,或者说数学思想。

二、小试牛刀

下面,我们就通过一些简单的例子来说明鸽巢原理的应用。

例1:新学期开学,市实验中学迎来了367位初一新同学,那么在这些同学中,一定会有两位同学是同年同月同日生的。

这个问题的理由很简单。因为一年里最多366天(闰年),把这367位初一新同学看作367只鸽子,按照出生日子,放入366个“鸽巢”(或者“抽屉”)中,由于鸽子数量大于鸽巢数量,则必然会有一个鸽巢中放入了两只鸽子。也就是说,至少有两名新同学的生日是相同的。进一步来说,由于大家都是初一新生,他们的年龄差通常是在一年之内,那么生日相同的两位同学就一定是同年同月同日生的了。

例2:假如一门课的考试分数是从0~100的整数,那么在102位考生中至少有两位是分数相同的。

这里,我们可以把0~100这101个整数看作101个鸽巢,根据鸽巢原理,由于鸽子数(考生人数)大于鸽巢数(不同的考分),所以至少有2个学生会出现相同的考分。

例3:从一副完整的54张扑克牌中,至少取出多少张,才能保证四种花色都出现?

由于我们知道在一副完整的扑克牌中,除了大小王外,一共是52张扑克牌,四种花色,每种花色13张。从最不利的情况出发,其中三种花色都取到,取了3×13=39张。为了保证四种花色齐全,我们还要再取一张第四种花色的扑克牌,同时还要考虑大小王2张牌。因此,为了符合题目要求,至少要取3×13+1+2=42张扑克牌。

例4:为了丰富同学们的课外知识,学校开设了天文、地理、演讲和航模四个兴趣小组,每位同学最多可以报两个兴趣小组,也可以不参加。请问:至少需要多少学生才能保证有7个人参加小组的情况完全相同?

根据“每位同学最多可以报两个兴趣小组,也可以不参加”这个条件,我们可以罗列出所有的情况:

(1)只参加1个兴趣小组的情况有4种:{天文}、{地理}、{演讲}、{航模};

(2)参加2个兴趣小组的情况有6种:{天文,地理}、{天文,演讲}、{天文,航模}、{地理,演讲}、{地理,航模}、{演讲,航模};

(3)不参加兴趣小组的情况只有1种。

以上合计11种情况,可以看作是11个鸽巢。要保证“有7个人参加小组的情况完全相同”,我们从最糟糕的情况出发去考虑,即每种情况下都有6位同学。由于是11种情况,根据鸽巢原理,当学生人数只少有6×11+1=67人时才能保证有7个人参加小组的情况完全相同。

说明一下,这里的11种情况,熟悉组合计数的同学很快就可以通过计算得到:C(4,1)+C(4,2)+C(4,0)=4+6+1=11种。

例5:甲、乙、丙、丁四位好友组织聚会,每人各带了两件礼品,分别赠与其他三位好友中的两位。请你证明:至少有两对好友,每对好友是互赠礼品的。

题目要求是证明互赠礼品,那么我们先看,假如是单向赠送礼品的话,有多少种不同的情况?显而易见,单向赠送礼品的情况有6种:{甲,乙}、{甲,丙}、{甲,丁}、{乙,丙}、{乙,丁}、{丙,丁}。这6种情况可以视作6个“鸽巢”。根据题意,四位好友,每人带了两件礼品,则一共8件礼品,放入6个“鸽巢”,势必会有两个“鸽巢”出现是互赠礼品的情况。这样,我们就证明了至少有两对好友,每对好友是互赠礼品的。

例6:从1~10这10个数字中任意选取6个数字,其中必定有两个数之和为11。

我们将这10个数字首尾两两相加,分别得到{1,10}、{2,9}、{3,8}、{4,7}、{5,6}这么5组数字,其和均为11。将这5组数字视作5个“鸽巢”,任取的6个数字视作“鸽子”,则根据鸽巢原理,这6个数字中一定会有两个同时来自于5组中的某一组,它们相加之和为11。

例7:从1~10这10个数字中任意选取6个数字,其中必定有两个数互质(两个数的公因数只有1)。

我们知道,前后相邻的两个自然数一定是互质的。因此,我们可以将这10个数字前后相邻的两两一组,分别得到{1,2}、{3,4}、{5,6}、{7,8}、{9,10}这么5组数字。同样,我们可以将这5组数字视作5个“鸽巢”,任取的6个数字视作“鸽子”,则根据鸽巢原理,这6个数字中一定会有两个同时来自于5组中的某一组。于是我们可知,任取的这6个数字中必定有两个数互质。

例8:有红、黄、蓝三种颜色的袜子各10只,混放在一个暗箱中。请问:在看不见颜色的情况下,至少要取出多少只袜子才能保证取出两双颜色不同的袜子?

从最糟糕的情况来看,我们先从暗箱中取出10只同色的袜子,比如10只红色袜子。然后,再取1只黄色袜子和1只蓝色袜子。到现在为止,还是没有满足“两双颜色不同的袜子”的要求。但是,只要我们再从剩下的黄色和蓝色两种颜色的袜子中多取一只,就又能凑齐第二双同色袜子了。于是,我们一共需要取10+1+1+1=13只袜子才能保证满足题目的要求。

这里,我们再倒回去看这个问题。13只袜子中,数量最多的同色袜子共有10只,还剩下3只,这3只袜子是其他两种颜色的。根据鸽巢原理,必定有两只袜子是同色的。

例9:在一个边长为4的正方形上,任意放入9个点,则其中必有3个点,它们构成的三角形的面积不超过2。

题目要求三角形面积不超过2,就是相当于是要求三角形面积小于或等于2。

鸽巢原理是什么?鸽巢原理在数学中的巧妙应用

显然,把边长为2的正方形沿着对角分割,可以得到两个面积为2的三角形。这让我们尝试着将这个边长为4的正方形分割成一个2×2的方格图,每个方格都是边长为2的小正方形。

这4个小正方形可以视作4个“鸽巢”,而9个点则可以视作“鸽子”。根据鸽巢原理,必定会有3个点落入其中一个边长为2的小正方形之中。而这3个点所能围成的三角形面积最大只能是2。所以这个问题的证明就完成了。

例10:任何一个有理数(m/n,m、n均为整数)最终一定可以表示为十进制循环小数。

我们知道,在除法运算中,余数只能小于或等于除数。因此,在十进制下,m除n后所出现的余数r一定是满足条件1≤r≤n-1的。那么,经过n次除法之后,必定会重复出现同一个余数。因此,这样得到的小数最终一定是循环小数。

小结:以上10个例子就是鸽巢原理的简单应用。能够快速得到完美的解决方案是鸽巢原理的一个典型特点。通过以上例子,我们大致可以得到应用鸽巢原理的几个步骤:

(1)先确定这个问题可能会运用鸽巢原理来解决;

(2)确定什么是“鸽子”,什么又是“鸽巢”?这是解决问题的关键;

(3)“鸽子”和“鸽巢”的数量分别是多少?

用鸽巢原理解题的本质是把所要讨论的问题利用鸽巢原理缩小范围,使之在一个特定的小范围内考虑问题,从而使问题变得简单明确。

用鸽巢原理解题的本质是把所要讨论的问题利用鸽巢原理缩小范围,使之在一个特定的小范围内考虑问题,从而使问题变得简单明确。用鸽巢原理解题的基本思想是根据问题的自身特点和本质,弄清对哪些元素进行分类,找出分类的规律,这里的关键是构造出合适的“鸽巢”或者“抽屉”。

在应用鸽巢原理解决问题时,凡是鸽巢原理可以证明的问题,理论上都可以用反证法得到证明,因为鸽巢原理本身就是通过反证法证明得到的。

另外需要特别强调的是,要理解和掌握鸽巢原理,就必须从极端的思想入手。所谓的极端思想就是从“极端糟糕”的最不利的情况出发去考虑问题。这个思想不仅在数学上是一个思考问题的利器,在物理学乃至经济学上同样有着非常广泛的应用。

上一篇:

下一篇:

相关阅读

分享