《第一节-鸽巢原理》由会员分享，可在线阅读，更多相关《第一节-鸽巢原理（12页珍藏版）》请在金锄头文库上搜索。
1、鸽巢原理及其他第一节 鸽巢原理 关于鸽巢原理的阐释，粗略地说就是如果有许多鸽子飞进不够多的鸽巢内，那么至少要有一个鸽巢被两个或多个鸽子占据。一、鸽巢原理的简单形式1、定理1：如果要把n+1个物体放进n个盒子，那么至少有一个盒子包含两个或更多的物体。 证明：用反证法进行证明。如果这n个盒子中的每一个都至多含有一个物体，那么物体的总数最多是n，这与有n+1个物体矛盾。所以某个盒子至少有两个物体。2、定理1的说明：无论是鸽巢原理还是它的证明，都不能具体找出含有两个或更多物体的盒子。它只是证明这样的盒子存在，即如果人们检査每一个盒子.那么他们会发现有的盒子里面放有多个物体。另外，当只有n个（或更少）物
2、体时，是无法保证鸽巢原理的结论的。这是因为可以在n个盒子的每一个里面放进一个物体。所以鸽巢原理成立的条件是至少为n+1个物体。 3、鸽巢原理的两个简单应用应用1：在13个人中存在两个人，他们的生日在同一个月份里。应用2：设有n对己婚大妇。至少要从这2n个人中选出多少人才能保证能够选出一对夫妇？ 为了在这种情形下应用鸽巢原理，考虑n个房间，其中一个房间对应一对夫妇。如果选择n十1个人并把他们中的每一个人放到他们夫妻所对应的那个房间中去，那么就有一个房间含有两个人；也就是说，已经选择了一对已婚夫妇。选择n个人使他们当中一对夫妻也没有的两种方法是选择所有的丈夫和选择所有的妻子，因此，n+1是保证能有
3、一对夫妇被选中的最小的人数。4、从应用2得出的两个推论推论1：如果将n个物体放入n个盒子并且没有一个盒子是空的，那么每个盒子恰好有一个物体。 说明：以应用2为例，选择n个人，如果其中有一对夫妻，那么必然有一个房间是空的，为了保证没有空房间，则必须从每对夫妻中选一个人，即恰好从每对夫妻中选一个人。推论2:如果将n个物体放入n个盒子并且没有盒子被放入多于一个的物体，那么每个盒子里恰好有一个物体。说明：以应用2为例，选择n个人，每个房间只能是夫妻中的一个人，2n个人，恰好每个从每对夫妻当中选择一个人。5、例题例1：给定m个整数a1，a2，am，存在满足0klm的整数k和l，使得ak+1+ ak+2+
4、 al能够被m整除。分析：题目通俗化，即给定m个整数的序列，其中连续几个的和能被m整除。所以考虑序列中连续和的情况。如果其中任何一个能被m整除，那么结论就成立了。对此，只能先假设连续和不能被整除，即有余数。解：找出鸽子：m个正整数连续和，即a1，a1+a2， a1+a2+a3，al+a2+a3+ am共m个和构造鸽巢：连续和不能被整除，那么余数必然为1,2，m-1共m-1个。如果余数为0或m，则已经整除结论成立，所以只能是m-1个。鸽巢原理：m个和，m-1个余数，那么必然有两个余数是相同的。因此存在整数k和l，0klm，使得al+a2+a3+ ak及al+a2+a3+ al除以m有相同的余数，
5、不妨设al+a2+a3+ ak=cm+ral+a2+a3+ al=dm+r，其中c，d，r为正整数。-可得ak+1+ ak+2+ al=(d-c)m从而可得ak+1+ ak+2+ al能够被m整除。特例如下设m=7,且整数为2, 4, 6, 3, 5, 5, 6。计算上面的和得到 2, 6, 12， 15, 20, 25, 31，这些整数被7除时余数分别为2, 6, 5，1，6, 4, 3。有两个等于 6的余数，这意味着结论：6 + 3 + 5 = 14可被7整除。例2： 一位国际象棋大师有11周的时间备战一场锦标赛，他决定每天至少下一盘棋，但为了不使自己过于疲劳他还决定每周不能下超过12盘棋
6、。证明存在连续若干天，期间这位大师恰好下了 21盘棋。分析：问题通俗化即连续若干个正整数的和恰好为21。实际问题转化为数学模型，即构造一个用来表示若干天下棋总盘数的数列。然后用鸽巢原理证明。证明：找出鸽子：设a1是在第一天所下的盘数，a2是在第一天和第二天所下的总盘数，a3是在第一天、第 二天和第三天所下的总盘数，11周总共77天，以此类推，a77表示77天下的总盘数。因为每天至少要下一盘棋，故a11，,因为在任意一周最多下12盘棋，所以a7712x11=132，则有序列1ala2a3a77 =132，为一个严格递增序列。根据若+干个正整数的和为21这一提示，构造数序列al+21a2+21a3
7、+21a77+21，此序列也是严格递增序列，由此可得al，a2，a3，a77 ，al+21，a2+21，a3+21，a77+21共77+77=154个数。构造鸽巢：由1ala2a3a77 =132，则有，1+21al+21a2+21a3+21a77+21=132+21=153。由此可得al，a2，a3，a77 ，al+21，a2+21，a3+21，a77+21是从1到153的正整数。鸽巢原理：al，a2，a3，a77 ，al+21，a2+21，a3+21，a77+21共154个数，而这些数是从1到153的正整数，从而可知其中必然存在两个数是相等的。而al，a2，a3，a77严格递增，各不相等。
8、al+21，a2+21，a3+21，a77+21也严格递增且各不相等， 那么必然有如下相等的情况存在一个正整数i和一个正整数j，使得ai=aj+21。ai为大师在前i天所下的盘数之和，aj为大师在前j天所下的盘数之和，ai-aj=21即为大师从第j+1天，第j+2天到第i天，下了21盘棋。例3：从整数1, 2,，200中选出101个整数。证明：在所选的这些整数之间存在两个这样的整数，其中一个可被另一个整除。证明之前，先介绍一种正整数的表示方法。正整数有奇数有偶数，而任何一个偶数，都可以通过提取因数2，变为奇数与若干个2乘积的形式，例如8=1x2x2x2,24=3x2x2x2，写成一般形式即奇数
9、x2n（其中n=1,2,3），而这个奇数绝不会超过这个偶数的一半。下面来证明例3。证明：找出鸽子：1到200中任意选出的101个整数。构造鸽巢：用奇数x2n的形式，把1到200的整数全部列出，1，1x21，1x22，1x273，3x21，3x22，3x265，5x21，5x22，5x2599，99x21199这样，就把1到200的全部整数列出，共100行。鸽巢原理：101个整数放到100行内，必然有两个整数在同一行，这两个数表示为p=ax2m，q=ax2n,其中，a为奇数，1a199，m、n为正整数，不妨设nmq/p=(ax2n)/(q=ax2m)= 2n-m。二、鸽巢原理的加强形式1、定理2
10、：如果要把多于mxn（比如mxn+1）个物体放进n个盒子，那么至少有一个盒子包含m+1个或m+1个以上的物体。例4：空间有六个点，其中任何三点都不共线，任何四点都不共面，在每两点之间连接直线段后涂色，将每一条这样的线段图成红色或蓝色，求证：不论如何涂色，一定存在一个三角形，它的三边有相同的颜色。证明：找出鸽子：从一点出发，连接的空间直线段有5条，即2x2+1条。构造鸽巢：红色和蓝色。鸽巢原理：根据定理2，则至少有三条线段的颜色是相同的。如图：三条实线段颜色相同，虚线连接三条线 段的端点。三条虚线段颜色不同时，则与 实现三条实线段构成颜色三边颜色相同 的三角形。三条虚线段颜色相同，但与三 条实线
11、段颜色不同时，由虚线段构成的三 角形就已经符合结论了。2、定理3：设ql，q2，q3，qn 是正整数，如果将ql+q2+qn-n+1个物体体放进n个盒子内，那么或者第一个盒子至少包含ql个物体，或者第二个盒子至少包含q2个物体，或者第n个盒子至少包含qn个物体。证明：ql+q2+qn-n+1=(ql-1)+(q2-1)+(qn-1)+1根据鸽巢原理，可得第i个盒子至少包含qi个物体，i=1,2，反正法：设第i个盒子含有少于qi个物体物体，那么物体的总数为(ql-1)+(q2-1)+(qn-1)=ql+q2+qn-n，比物体总数少1个，与题设矛盾，故结论成立。说明：上述结论中，当物体总数为ql+
12、q2+qn-n时，则有第i个盒子不含有qi或者更多个物体，i=1,2，只需将qi-1个物体分配到第i个盒子即可实现。例5：个果篮装有苹杲、香蕉和橘子。为了保证篮子中或者至少有8个苹果，或者至少 有6个香蕉，或者至少有9个橘子，则放人篮子中的水果的最小件数是多少？解：根据定理3可得，所需的水果最小件数为8+6+9-3+1=21件。3、从定理3得到的一个推论推论3：设n和r都是正整数。如果把n(r-1)+1个物体分配到n个盒子中，那么至少有一个盒子含有r或更多个物体。证明：n(r-1)+1=nr-n+1，令定理3中ql=q2=qn=r，则结论成立。4、由推论3得到的3个平均原理平均原理1：如果n个
13、非负整数，ql，q2，q3，qn的平均数大于r-1，即(ql+q2+qn)/n(r-1),那么那么这n个数中，至少有一个整数大于r-1（即大于或等于r）。分析：根据推论3，如果n(r-1)+1个物体平均分配到n个盒子中，除一个盒子为r个物体外，其余盒子均为r-1个。反过来，如果平均数要大于r-1，那个必然一个盒子中的物体数量要大于或等于r。证法1：(ql+q2+qn)/n= n(r-1)+1/n=r-1+1/n(r-1),rN+,则必有qir，i=1,2，证法2：反证法，不妨设ql=q2=qn=r-1，即设这n个整数全部比r小，则有(ql+q2+qn)/n=(r-1)，与题设r-1矛盾，所以这
14、n个数不可能全部小于r，则必至少有一个大于或等于r。平均原理2：如果n个非负整数，ql，q2，q3，qn的平均数小于r+1，即(ql+q2+qn)/n(r+1),那么那么这n个数中，至少有一个整数小于r+1。分析：根据推论3，如果n(r+1)-1（因为平均数小于r+1，所以设为n(r+1)-1，其平均数才能小于r+1）个物体平均分配到n个盒子中，除一个盒子为r个物体外，其余盒子均为r+1个。反过来，如果平均数要小于r+1，那个必然一个盒子中的物体数量要小于或等于r。证明：(ql+q2+qn)/n= n(r+1)-1/n=r+1-1/n(r+1),rN+。平均原理3：如果n个非负整数，ql，q2，q3，qn的平均数至少等于r，即(ql+q2+qn)/nr,那么这n个数中，至少有一个整数大于等于r。证明：令平均原理中的r-1=u，则结论成立。例5：有两个碟子，其中一个比另一个小，它们都被分成200个均等的扇形。在大碟子中，任选100个扇形并着成红色，而其余的100个扇形着成蓝色。在小碟子中，每一个扇形或者着成红色，或者着成蓝色，所着红色扇形和蓝色扇形的数目没有限制。然后，将小碟子放到大碟子上面使两个碟子的中心重合。证明：能够将两个碟子的扇形对齐使得小碟子和大碟子上相同颜色重合的扇形
