鸽巢原理

鸽巢原理(Pigeonhole PRinciple)

目录

  • 1什么是鸽巢原理
  • 2鸽巢原理的形式
  • 3鸽巢原理的应用
  • 4参考文献

什么是鸽巢原理

鸽巢原理又名抽屉原理狄利克雷原理,它由德国数学家狄利克雷(Divichlet,1805—1855)首先发现。鸽巢原理在组合学中占据着非常重要的地位,它常被用来证明一些关于存在性的数学问题,并且在数论和密码学中也有着广泛的应用。使用鸽巢原理解题的关键是巧妙构造鸽巢或抽屉,即如何找出合乎问题条件的分类原则。

鸽巢原理的形式

鸽巢原理的简单形式:如果n+1个物体被放进n个盒子,那么至少有一个盒子包含两个或者更多的物体。

证明:如果这n个盒子中的每一个都至多含有一个物体,那么物体的总数最多是n。既然我们有n+1个物体,于是某个盒子就必然包含至少两个物体。

鸽巢原理的加强形式:令Q1Q2,……,Qn为正整数,如果将Q1+Q2+…+Qn-n+1个物体放入n个盒子内,那么,或者第一个盒子至少含有Q1个物体,或者第二个盒子至少含有Q2个物体,……,或者第n个盒子至少含有Qn个物体。

证明:设将Q1+Q2+…+Qn-n+1个物体分放到n个盒子中,如果对于每个i=1,2,…,n,第i个盒子含有少于Qi个物体,那么所有盒子中的物体总数不超过(Q1-1)+(Q2-1)+…+(Qn-1)=Q1+Q2+…+Qn-n,该数比所分发的物体总数少1,所以我们断定,对于某一个i=1,2,…,n,第i个盒子至少包含Qi个物体。

由上面的原理可得如下推论:推论1:m双鞋放入n个鞋盒中,则至少有一个盒子中有不少于[]双鞋。

推论2:n(m-1)+1只鸽子放入n个鸽笼,则至少有一个鸽笼中有m只鸽子。

推论3:设m1m2,…,mn均为正整数,且满足>r-1,则m1m2,…,mn申至少有一个数不小于r。

鸽巢原理的应用

1.用于几何图形

(1)在边长为1的等边三角形内任意选择5个点,存在2个点,其间距离至多为1/2。

证明:由题意,可以构造出4个抽屉,每个抽屉满足在其问的距离至多为1/2(见图1)。根据鸽巢原理,在4个抽屉里分别放置4个点,不论第5个点如何放置,都满足两点之间的距离最多为1/2。

(2)证明在边长为1的等边三角形内任意选择10个点,存在两个点,其间距离至多为1/3。

证明:按照图2的构造可以证明该题。

归纳:在边长为1的等边三角形内任意选择n2+1个点,存在2个点,其间距离为。

(3)在单位正方形内任意给定51个点,求证至少有三个点落在一个半径为1/7的圆内。

证明:将单位正方形的各边五等分,以此把它分成25个边长为l/5的小正方形,作为25个抽屉。根据抽屉原理可知,其中至少有一个小正方形中含有[]+1=3个点,而这样的小正方形外接圆半径是。又由得得/10<1/7,所以至少有三个点在半径为1/7的一个圆内。

(4)在直径为5的圆内任意给定10个点,证明存在两个点,它们之间的距离小于2。

证明:根据题意,我们最先考虑到把圆等分成9个扇形而构造出9个抽屉,但是虽然必有两个点在某一扇形内,但不能确认它们之间的距离小于2。于是我们考虑先用一个与已知圆同心,半径为1的不包含边界的小圆作为一个抽屉,然后再把圆环部分等分成八个部分,(如图3所示)这样就构成了9个抽屉。

根据抽屉原理可知,存在两个点在同一个抽屉(包括边界)中,若这两个点在小圆(不包含边界)中,显然它们之间的距离小于2。若这两个点在圆环部分的八个等分中的某一图形里,不妨设在图形ABCD中。由于

由此可知,这时两个点之间的距离也小于2,从而命题得证。

2.用于数的整除关系

(1)在前12个自然数中任取7个数,一定存在两个数,其中的一个数是另一个数的整数倍。

分析:若能把前12个自然数划分成6个集合,即构成6个抽屉,使每个抽屉内的数或只有一个,或有任意的两个数,其中的一个是另一个的整数倍,这样就可以由抽屉原理推出结论。那么如何对这12个自然数进行分组?我们知道,一个自然数,它要么是奇数,要么是偶数。若是偶数,我们总能把它表达为奇数与2k(K=1,2,3,…)的乘积的形式。这样,如果允许上述乘积中的因子2k指数K可以等于零,则每一个自然数都可表达成“奇数×2k(K=0,1,2,…)的形式,于是,把这12个自然数用上述表达式进行表达,并把式中“奇数”部分相同的自然数作为一组,构成一个抽屉。

证明:把前12个自然数划分为如下六个抽屉:

A1={l·20,l·21,l·22,1·23}

A2={3·20,3·21,3·22}

A3={5·20,5·21}

A4={7·20}

A5={9·20}

A6={11·20}

显然,上述六个抽屉内的任意两个抽屉无公共元素,且A1+A2+A3+A4+A5+A6={1,2,3,…,12}。由鸽巢原理,对于前12个自然数不论以何种方式从其中取出7个数,必定存在两个数同在A1A2A3抽屉里,那么这两个数之间存在倍数关系。即一个数是另一个数的整数倍。

归纳:从1到2n的正整数中任取n+1个数,则这n+1个数中至少有两个数,其中一个数是另一个数的倍数。

证明:设这n+1个数为ala2,…,anan + 1,我们对其中的每一个数都进行如下的处理:去掉一切2的因子,直到剩下奇数为止。例如,20=22×5,去掉2留下奇数5,结果可得到n+1个奇数r1r2,…,rnrn + l。显然1≤r1r2,…,rnrn + l<2n,而1到2n中只有n个奇数,由抽屉原理知,上面n+1个奇数中至少有两个数是相同的,设这两个数为ri=rj(i≠j),它们分别代表的整数为×ri和×rj,不论它们谁大谁小,和也之间总存在倍数关系,即一个数是另一个数的整数倍。

(2)证明任意五个整数中,必有三个整数的和是3的倍数。

证明:任一整数被3除余数只可能是0,l,2。

若给定的五个整数被3除所得的余数中0,l,2都出现,那么余数分别为O,l,2的三个数的和一定能被3整除,如果余数中至多只出现0,l,2中的两个,那么由抽屉原理,其中必有一个余数至少出现三次。而这余数相同的三个数的和一定能被3整除。

(3)证明对任意给定的52个整数,存在其中的两个整数,要么两者的和能被100整除,要么两者的差能被100整除。

证明:任意一个整数a除以100产生的余数不外乎为O,1,2,…,99。题目中的52个整数ai除以100则产生52个余数ri(i=1,2,…,52)。

如果这52个余数中有两个余数相等,即ri=rj(i≠j),那么一定有ai-aj能被100整除。即存在两个数,它们的差能被100整除。

如果这52个余数均不相等,我们现在对0,1,2,…,99这100个数来构造抽屉,将相加之和为100的两个数放在同一个抽屉里。

构造出来的51个抽屉如下:{1,99},{2,98},{3,97},...,{49,51},{0},{50}由于有52个不同的余数,根据鸽巢原理,必有两个余数来自同一个抽屉,这只能从前49个抽屉中取出。而不论从哪个抽屉取出,同一个抽屉里的两个余数之和为100,那么一定有产生这两个余数的两个整数之和能被100整除。

(4)证明对任意n+1个整数a1a2,…,an + 1,存在两个整数aiaj(i≠j),使得ai-aj能够被n整除。

证明:一个整数除以n的余数不外乎为0,1,2,…,n-1。n+1个整数a1a2,…,an + 1除以n则产生n+1个余数,由于一个整数除以n最多只能产生n个不同的余数(即n个抽屉),故根据鸽巢原理,这n+1个余数中,一定有两个相等。那么,产生相等余数的两个整数相减,其差一定能被n整除。

3.应用于“连续时间”问题

(1)某厂在五年期问的每一个月里至少试制一种新产品,每年最多试制19种新产品。试证明:一定存在连续的几个月,恰好试制24种新产品。

证明:设五年期间该厂各个月试制的新产品个数分别为a1a2,…,a59a60,按题意,构造出数列an的前n项和的数列s1s2,…s59s60,则有:1≤a1=s1<s2<…<s59<s60≤19×5=95,而序列s1+24,s2+24,…,s59+24,s60+24也是一个严格递增序列:25≤s1+24<s2+24<…<s59+24<s_{60}+24≤95+24=119于是,这120个自然数s1s2,…s59s60s1+24,s2+24,…,s59+24,s60+24都在区间[1,119]内。在[1,119]内,只有119个自然数,根据抽屉原理,必定存在两个数相等。

上述两个数列又分别是严格单调的,因此必然存在一个i和j,使得si=sj+24。从而,该厂在从第j+1个月起到第i个月的这几个月时间里,恰好试制了24种新产品。

(2)一个孩子每天至少看一个小时电视,总共看7周,但是每周看电视从不超过11小时。证明,存在连续若干天在此期间这个孩子恰好看电视20个小时。(假设这个孩子每天看电视时间为整数个小时)证明:设这个孩子7周内每天看电视的时间分别为a1a2,…,a49,现在构造出数列{an}的前n项和的数列s1s2,…s_{49},则有:1≤a1=s1<s2<…<s49≤11×7=77,而序列s1+20,s2+20,…,s49+20也是一个严格递增序列:21≤s_1+20<s_2+20<…<s_{49}+20≤77+20=97于是,这98个自然数s1s2,…s49sl+20,s2+20,…,s49+20都在区间[1,97]内。而在[1,97]内,只有97个自然数,根据抽屉原理,必定存在两个数相等。而上述两个数列又分别是严格单调的,因此必然存在一个i和j,使得si=sj+20。从而,这个孩子在第j+1天起到第i天的时间里,恰好看电视20个小时。

总结:凡遇此类问题都可按照上述方法进行证明。从上面两题的题目我们可以看出,问题中需要证明的数字(如上面的24和20)加上“在给定时间内能完成任务的最大数字”(如上面的95和77)恰好比“给定时间”的2倍少l。(如:(24+95)+1=60×2,(20+77)+1=49×2)。

这是该类问题最重要的特征,因为前两个数字之和恰好可以看成是抽屉数,而“给定时间”×2可以看成是要被放人抽屉的元素数,抽屉数刚好比元素数少1,则有两个元素一定会放人同一个抽屉,通过鸽巢原理从而完成对问题的证明。这也是解决此类问题的关键所在。

4.用于“人的相识”问题

(1)证明任意六个人中至少存在三个人或是互相认识,或是互相不认识。

证明:在这六个人中任意取定一个人P,则其余五个人可分为两类:A={与P认识的人},B={与P不认识的人}。根据抽屉原理,A和B中至少有一个集合有3个人,不妨设此集合为A,且对于集合A中的3个人a,b,c来说,若他们彼此不认识,则问题得证。否则若a,b,c中有两个人互相认识,不妨假设这两个人是a和b,则P,a,b三个人互相认识。

若集合B中至少有三个人,用类似的方法也可得到证明。

(2)证明在一群n>1个人中,存在两个人,他们在这群人中有相同个数的熟人。(某人与自己不能算是熟人)证明:在n个人中,每个人所认识的人数只能是0,1,2,…,n-1。

如果已知有两个人认识的人数相等,那么问题得证。

由于某人认识0个人的情况和另一人认识n一1个人的情况不可能同时发生,那么这n个人所能认识的人数0,1,2,…,n-1也不可能同时存在,即最多只能存在n-1种情况,我们把它看成n-1个抽屉,根据鸽巢原理,n个元素放进n-1个抽屉,则一定有两个元素在同一个抽屉内,即有两个人所认识的人数相等。

(3)在一个100人的聚会中,每个人都有偶数个(有可能是0个)熟人,证明,在这次聚会上存在3个人有相同个数的熟人。

证明:根据题意,每个人所能认识的人数可能为:O,2,4,…,96,98。

在这个100人的聚会中,若这50种情况0,2,4,...,96,98都出现,我们假设第1个人认识。个人,第2个人认识2个人,第3个人认识4个人,……,依此类推,第50个人认识98个人,那么,在余下的50个人中,如果已知有两个人有相同个数的熟人,那么可以得到有3个人认识相同个数的人,问题得证。如果不知道是否还有两个人有相同、个数的熟人,我们来做下面的假设:剩下的50个人也是依次认识0,2,4,……,98个人,那么我们无法证出结论。现在我们来分析假设是否成立。根据以上推导和假设,我们可以得到有两个人认识0个人,有两个人认识98个人,对于这两个认识O个人的人来说,他们自然也不认识那两个认识98个人的人,而对于那两个认识98个人的人来说,只能有一个人他们不认识,这就与有两个人都不认识他们矛盾,所以不可能出现两个认识0个人的人和两个认识98个人的人同时存在的情况,故假设不成立。

所以剩下的50个人中,最多只能出现认识O,2,4,……,98个人这50种情况的49种,根据鸽巢原理,必然有一种情况要重复。所以一共存在3个人有相同个数的熟人。

若在这l00个人的聚会中,只出现49种或更少的情况,那么根据鸽巢原理同样可以得到一定有3个人有相同个数的熟人。

参考文献

  1. 1.01.11.2 何春,万琳,任雅莉.鸽巢原理及其应用.计算机与数字工程2007年8期
联系管理员
15775053793

作者头像
经济百科创始人

经济百科

上一篇:投射性认同
下一篇:ROF技术

发表评论