鸽巢原理

  	      	      	    	    	      	    
鸽巢原理(Pigeonhole Principle) 
 
目录
 
 
1 什么是鸽巢原理
 
2 鸽巢原理的形式[1]
 
3 鸽巢原理的应用[1]
 
4 参考文献
 
 
 
什么是鸽巢原理
 
　　鸽巢原理又名抽屉原理或狄利克雷原理，它由德国数学家狄利克雷(Divichlet，1805—1855)首先发现。鸽巢原理在组合学中占据着非常重要的地位，它常被用来证明一些关于存在性的数学问题，并且在数论和密码学中也有着广泛的应用。使用鸽巢原理解题的关键是巧妙构造鸽巢或抽屉，即如何找出合乎问题条件的分类原则。[1] 
 
鸽巢原理的形式[1]
 
　　鸽巢原理的简单形式：如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或者更多的物体。 
　　证明：如果这n个盒子中的每一个都至多含有一个物体，那么物体的总数最多是n。既然我们有n+1个物体，于是某个盒子就必然包含至少两个物体。 
　　鸽巢原理的加强形式：令Q1，Q2，……，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：设m1，m2，…，mn均为正整数，且满足>r-1，则m1，m2，…，mn申至少有一个数不小于r。 
 
鸽巢原理的应用[1]
 
　　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个数，必定存在两个数同在A1或A2或A3抽屉里，那么这两个数之间存在倍数关系。即一个数是另一个数的整数倍。 
　　归纳：从1到2n的正整数中任取n+1个数，则这n+1个数中至少有两个数，其中一个数是另一个数的倍数。 
　　证明：设这n+1个数为al，a2，…，an，an + 1，我们对其中的每一个数都进行如下的处理：去掉一切2的因子，直到剩下奇数为止。例如，20=22×5，去掉2留下奇数5，结果可得到n+1个奇数r1，r2，…，rn，rn + l。显然1≤r1，r2，…，rn，rn + 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个整数a1，a2，…，an + 1，存在两个整数ai和aj(i≠j)，使得ai-aj能够被n整除。 
　　证明：一个整数除以n的余数不外乎为0，1，2，…，n-1。n+1个整数a1，a2，…，an + 1除以n则产生n+1个余数，由于一个整数除以n最多只能产生n个不同的余数(即n个抽屉)，故根据鸽巢原理，这n+1个余数中，一定有两个相等。那么，产生相等余数的两个整数相减，其差一定能被n整除。 
　　3.应用于“连续时间”问题 
　　(1)某厂在五年期问的每一个月里至少试制一种新产品，每年最多试制19种新产品。试证明：一定存在连续的几个月，恰好试制24种新产品。 
　　证明：设五年期间该厂各个月试制的新产品个数分别为a1，a2，…，a59，a60，按题意，构造出数列an的前n项和的数列s1，s2，…s59，s60，则有：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个自然数s1，s2，…s59，s60和s1+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周内每天看电视的时间分别为a1，a2，…，a49，现在构造出数列{an}的前n项和的数列s1，s2，…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个自然数s1，s2，…s49和sl+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.0 1.1 1.2 何春,万琳,任雅莉.鸽巢原理及其应用.计算机与数字工程2007年8期