鸽巢原理及其应用

鸽巢原理及其应用,陈淑贞,2011.11.22,主要内容,1.引言2.鸽巢原理3.鸽巢的构造及其应用4.鸽巢原理在国内外数学竞赛中的应用5.鸽巢原理的推广Ramsey定理(介绍）,1.引言,鸽巢原理为组合学中的一个重要原理。鸽巢原理最早是由19世纪的德国数学家迪里赫莱（Dirichlet）运用于解决数学问题而提出来的，所以又称为“迪里赫莱原理”，也有称“抽屉原理”的。应用它可以解决许多有趣的问题，并且常常得到一些令人惊异的结果。它常被用来证明一些存在性的数学问题，并且在数论和密码学中也有着广泛的应用。对于一些比较特殊的问题，若用一般的数学方法去研究，很复杂或根本解决不了，但用鸽巢原理往往能起到事半功倍的效果，所以鸽巢原理也是国际国内数学竞赛中的重要内容，在数学竞赛中具有很大的应用意义。,2.鸽巢原理,2.1鸽巢原理的简单形式若有n+1只鸽子飞到n个鸽巢里面，则至少有一个鸽巢里至少有两只鸽子。,2.2鸽巢原理的加强形式,注:n+1为结论成立的最小数。,将q1q2qnn1个物品放入n个抽屉中，则至少存在某个抽屉i（1in）,使得这个抽屉里至少有qi个物品。,注:q1q2qnn1为结论成立的最小数,记为N(q1,q2,qn;1)。,显然,当q1=q2=qn=2时,加强形式即为简单形式。,即N(q1,q2,qn;1)=q1+q2+qn-n+1.,推论1n(r-1)1只鸽子飞入n个巢里，则至少有一个鸽巢里至少有r只鸽子。,当qi=r时，得：,推论3：设m1,m2,mn均为正整数,且满足,则m1,m2,mn中至少有一个数不小于r。,推论2：m只鸽子飞入n个巢里，则至少有一个鸽巢里至少有只鸽子,其中是不小于的最小整数。,3鸽巢的构造及其应用,虽然鸽巢原理十分简单明了，但不是所有的问题都一眼就可以看出什么是鸽子，什么是鸽巢。在应用它的时候却涉及很多技巧，这是利用鸽巢原理解题的魅力所在。常用的构造鸽巢的方法有：利用整数分组、余数分类，划分集合，分割区间、分割图形，利用染色等。下面给出几类常用的构造鸽巢的方法。,3.1利用整数分组构造“鸽巢”,例1试证明从1，2，kn中选n+1个数，总存在2个数，它们之间最多相差k-1。,证明：把1，2，kn分为n部分1，2，3，,k,k+1,k+2,2k,(n-1)k+1,(n-1)k+2,kn,即做n个鸽巢，从中任选n+1个数，由鸽巢原理，必有2个数选在同一个鸽巢中，所以它们的差最大为k-1。,路易波萨是匈牙利数学家,在他11岁时匈牙利大数学家厄杜斯给他出了个问题:“如果你手头上有n+1个整数，这些整数是小于或等于2n的，那么你一定会有一对数是互素的。你知道这是什么原因吗？”波萨仅思考了半分钟就巧妙地回答了这个问题。,例2在一条笔直的马路上种树，从起点起，每隔1米种一棵数。如果把三块“爱护树木”的小牌分别挂在三棵树上，那么不管怎么挂，至少有两棵挂牌的树它们之间的距离是偶数（以米为单位）。,解从起点开始给每课树编号，树上的号码依次为1,2,3,n,把这些号码分为奇数和偶数两类，当作两个鸽巢，,把三块牌分别挂在三棵树上，那么不管,怎么挂，这三棵挂牌的树至少有两棵树的号码同为奇数或偶数，而这两棵树的差必为偶数，,所以至少有两棵挂牌的树它们之间的距离是偶数（以米为单位）。,3.2利用划分图形构造“鸽巢”,例1边长为1的正方形中，任意放入9个点，求证这9个点中任取3个点组成的三角形中，至少有一个的面积不超过.,解：将边长为1的正方形等分成边长为1/2的四个小正方形，视这四个正方形为鸽巢，9个点任意放入这四个正方形中，由鸽巢原理必有三点落入同一个正方形内.现特别取出这个正方形来加以讨论.,图1,把落在这个正方形中的三点记为D、E、F.如图1，通过这三点中的任意一点（如E）作正方形边平行线,SDEFSDEGSEFG,所以，结论成立。,如果8个点无一个在圆心上，可将圆分成7个相等的扇形，由鸽巢原理，这8个点至少有两个在同一个扇形内，则这两点之间的距离小于半径。,例2在圆内（包刮圆周）有8个点，则其中必有两个点，它们之间的距离小于圆的半径。,证明分两种情况考虑。,2.如果8个点有一个点在圆心，可将圆分成6个相等的扇形，如图，,取扇形OA1A2不包含OA2,扇形OA2A3不包含OA3,扇形OA6A1不包含OA1,由鸽巢原理，余下的7个点,至少有两个在在同一个扇形内，则这两点之间的距离小于半径。,由于圆上相邻两点Ai,Aj间的弦长恰好为圆的半径，所以,在边长为1的正方形内任取5个点,则其中至少有两点,它们之间的距离不超过,2.证明:(1)在一边长为1的三角形中任取10个点,则其中至少有两点,它们之间的距离不超过1/3.(2)确定mn，使得在一边长为1的三角形中任取mn个点,则其中至少有两点,它们之间的距离不超过1/n.,类似这样的问题还有不少。,3.3利用余数分类构造“鸽巢”,例试证明任意给定52个整数，它们之中必有2个数，其和或差是100的倍数(即被100整除）。,证明：任意一个整数a除以100产生的余数为0，1，2，99共100种。用a1,a2,a52表示这52个整数，ai除以100产生的余数记为ri（i=1，2，52）。,由鸽巢原理，这52个整数分别除以100产生的52个余数r1,r2,r52中必有两个余数落在同一组中，,我们现在用0，1，2，,99这100个余数来构造鸽巢，将它们分为51组，构造出51个鸽巢：0，1，99，2，98，49,51,50,即存在两个数，它们的和或差能被100整除。,若这两个余数落在0或50中，则它们的和及,差都能被100整除。,若这两个余数落在剩下的49组中的一组，当余数相同,时，它们的差被100整除，当余数不同时，它们的和被100整除，,类似这样的例子也有不少。,这个问题的一般提法任意给定n+2个整数，它们之中必有2个数，其和或差是2n的倍数。,1.任取n+1个正整数，求证在这n+1个数中必有两个数它们之差被n整除.,2.任意给出2011个正整数证明必存在正整数,2.任意给出2011个正整数证明必存在正整数,证明构造部分和序列,则有如下两种可能：,（i）存在整数h(1h2011),使得.此时,取k=0,l=h即满足题意.,（ii）对任一整数i，均有.令，,由鸽巢原理知,存在整数,使得.,不妨设lk，则,综合（i）和（ii），即知题设结论成立.,3.4利用分割区间来构造“鸽巢“,例一个孩子每天至少看一个小时电视，共看7周，每周看电视从不超过11小时，证明：在此期间存在连续若干天这个孩子恰好看电视20个小时。（设这个孩子每看电视时间为整数个小时）,证明设这个孩子7周内每天看电视的时间分别为a1,a2,a49小时，现在构造出数列an的前n项和的数列s1=a1，s2=a1+a2，s49=a1+a2+a49，则有：1s1s2s3s49117=77,而序列s1+20，s2+20，,s49+20也是一个严格的递增序列，,且有21s1+20s2+20j)，即si-sj=20，从而这个孩子从j+1天起到第i天的时间里恰好看电视20个小时。,类似这样的例子还有不少。,1.一个乒乓球手有37天时间准备一场比赛,他决定每天至少打1场球,37天至多打60场球,证明:在此期间存在连续若干天他恰好打了21场球。,2.一个学生解数学题100天,每天至少解一道题,每10天至多解17道题,证明:在此期间存在连续若干天他恰好解了29道题.那么是否存在连续若干天他恰好解了30道题。,3.在(0,1区间上任取5个点，则必有两个点它们的距离小于1/4。,4.n+1个实数xi满足0xi1（i=1,2,n+1），求证这n+1个实数中必存在两个数xi,xj，使得,由于1ai200，所以ri(1i101)只能取1，3，5，199这100个奇数，而r1，r2，r101共有101项，由鸽巢原理知，存在1ij101，使得,ri=rj，,不妨设sisj，则,即aj能被ai整除.,3.5利用化分集合来构造“鸽巢”,例试证明在1到200个自然数中任取101个数，一定存在两个数，其中的一个数是另一个数的整数倍。,证明:设a1，a2，a101是被选出的101个整数,对任一ai，都可以唯一地写成如下的形式：,其中，si为整数，ri为奇数.,推论3的应用.,例1把1至10这十数字随机的排成一个圆圈，证明必有一个三相邻数字之和大于等于17,证明把1至10这十个数字随机排成一个圆圈,从中任取三个相邻数字的方法有10种,设这10种三个相邻数字之和分别为m1,m2,m10,则有,m1+m2+m10=3(1+2+10)=,由推论3,必存在mi(0i10),使得mi17，即问题得证,例2设有大小两个圆盘，每个都划分成大小相等的200个小扇形，在大盘上任选100个小扇形漆成黑色，其余的100个小扇形漆成白色，而将小盘上的200个小扇形任意漆成黑色或白色.现将大小两只圆盘的中心重合，转动小盘使小盘上的每个扇形含在大盘上的小扇形之内.证明：有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色.,证明：由条件，固定大盘转动小盘共有200个不同的位置，设mi表示在第i个位置时，大、小扇形同色的个数（i=1，2，200），,只要证明,对小盘上的每一个扇形，由着色的条件，旋转一周（200个位置），与大扇形同色的个数为100个，所以200个小扇形在旋转一周同色的个数共有100200=20000个.,4.鸽巢原理在国内外数学竞赛中的应用,中学数学竞赛中，鸽巢原理常常作为一种处理问题的工具，多用于组合问题，在一些代数与几何问题中亦有应用。鸽巢原理及其简单形式多用于解答存在性问题，应用鸽巢原理解题时，关键是构造适合的鸽巢。下面给出一些利用鸽巢原理解决的数学竞赛题。,例1(北京市数学竞赛复赛试题)将910瓶红、蓝墨水，排成130行，每行7瓶。证明：不论怎样排列，红、蓝墨水瓶的颜色次序必定出现下述两种情况之一种：1至少三行完全相同；2至少有两组（四行），每组的两行完全相同。,证明：910瓶红、蓝墨水，排成130行，每行7瓶。每行中的7个位置中的每个位置都有红、蓝两种可能，因而总计共有27=128种不同的行式（当且仅当两行墨水瓶颜色及次序完全相同时称为“行式”相同）。依鸽巢原理可知，在130行中必有两行（记为A，B）“行式”相同。,在除A、B外的其余128行中若有一行P与A（B）“行式”相同，则P，A，B满足“至少有三行完全相同”，结论成立；在除A，B外的其余128行中若没有与A（B）行式相同者，则128行至多有127种不同的行式，依鸽巢原则，必有两行（不妨记为C、D）行式相同，这样便找到了（A，B）、（C，D）两组（四行），每组两行完全相同，结论成立。,例2(1995年全国高中数学联赛试题)将平面上每个点以红、蓝两色之一着色，证明：存在这样的两个相似三角形，它们的相似比为1995，并且每一个三角形的三个顶点同色。,证明：如图，作两个半径分别为1和1995的同心圆，在内圆上任取9个点，必有5点同色，记为A1,A2,A3,A4,A5。如图所示，连半径0Ai交大圆于Bi（i=1,2,3,4,5），对B1，B2，B3，B4，B5，必有3点同色，记为Bi,Bj,Bk，则BiBjBk与AiAjAk为三顶点同色的相似三角形，相似比等于1995，所以结论成立.,例3(美国普特南数学竞赛题),在坐标平面上任取五个整点（该点的横纵坐标都取整数），证明其中一定存在两个整点，它们的连线中点仍是整点。,证明欲使坐标平面两点（x1,y1）、（x2,y2）的中点坐标是整数，必须而且只须x1与x2，y1与y2的奇偶性相同。,坐标平面上的任意整点按照横纵两个坐标的奇偶性考虑有且只有如下四种：（奇数、奇数），（偶数，偶数），（奇数，偶数），（偶数，奇数）以此构造四个“鸽巢”，则在坐标平面上任取五个整点，那么至少有两个整点，属于同一个“鸽巢”，因此它们连线的中点就必是整点。,我们可以把整点的概念推广：如果（x1，x2,xn）是n维（元）有序数组，且x1，x2,xn中的每一个数都是整数，则称（x1，x2,xn）是一个n维整点（整点又称格点）。如果对所有的n维整点按每一个xi的奇偶性来分类，由于每一个位置上有奇、偶两种可能性，因此共可分为222=2n个类(鸽巢)。这是对n维整点的一种分类方法。,当n=3时，23=8，此时可以构造命题：“任意给定空间中九个整点，求证它们之中必有两点存在，使连接这两点的直线段的内部含有整点”。这就是1971年的美国普特南数学竞赛题。,例4(美国普特南数学竞赛题)任意6个人中必有3个人互相认识，或互相不认识。,这就是著名的Ramsey问题。,这个问题可转化为：对6阶完成图K6的边任着红、蓝两色，必存在同色三角形。,证明设A0,A1,A5为K6的6个顶点，从A0引出的5条边中，必有3条同色，不妨设A0A1,A0A2,A0A3为红色。,若A1A2A3有一条红边，则这条边的两个端点连同A0构成红色三角形。若A1A2A3没有红边，则这个三角形为蓝红色三角形。结论成立。,我们用6个点表示6个人,当两个人互相认识时,两个点之间连一条红边,当两个人互相不认识时,两个点之间连一条蓝边,于是,注:6为结论成立的最小数.,例5(第6届国际中学生数学奥林匹克试题),17名科学家中每名科学家都和其他科学家通信，在他们通信时，只讨论三个问题，而且任意两名科学家通信时只讨论同一个问题，证明：其中至少有三名科学家，他们相互通信时讨论的是同一个问题。,证明：视17个科学家为17个点，每两个点之间连一条线表示这两个科学家在讨论同一个问题，若讨论第一个问题则在相应两点连红线，若讨论第2个问题则在相应两点连条黄线，若讨论第3个问题则在相应两点连条蓝线。三名科学家研究同一个问题就转化为找到一个三边同颜色的三角形。即转化为证明:对17阶完成图K17的边任着红、蓝、黄三色，必存在同色三角形。,考虑科学家A，他要与另外的16位科学家每人通信讨论一个问题，相应于从A出发引出16条线段，将它们染成3种颜色，由鸽巢原理必有6条同色，不妨记为AB1，AB2，AB3，AB4，AB5，AB6同红色，若Bi（i=1，2，6）之间有红线，则出现红色三角线，命题已成立；否则B1，B2，B3，B4，B5，B6之间的连线只染有黄、蓝两色，由例4存在同色三角形，证必。,前面数例我们看到，鸽巢原理的应用多么奇妙，其关键在于恰当地制造鸽巢，就像我们前面所介绍的，利用余数分类，划分集合，分割区间，分割图形