第2章 鸽巢原理

第二章鸽巢原理内容提要鸽巢原理：简单形式鸽巢原理：加强形式Ramsey定理鸽巢原理又称抽屉原理或鞋盒原理,这个原理最早是由Dirichlet提出的.鸽巢原理是解决组合论中一些存在性问题的基本而又有力的工具.它是组合数学中最简单也是最基本的原理之一,从这个原理出发,可以导出许多有趣结果,而这些结果常常是令人惊奇的.Ramsey理论对组合数学发展产生过重要的影响.

1928年,年仅24岁的英国杰出数学家Ramsey发表了著名论文《论形式逻辑中的一个问题》,他在这篇论文中,提出并证明了关于集合论的一个重大研究成果,现称为Ramsey定理.尽管两年后他不幸去世,但是他开拓的这一新领域至今仍十分活跃,而且近年来在科技领域获得了成功的应用.本讲主要介绍鸽巢原理、Ramsey数及性质、

Ramsey定理及应用.鸽巢原理定理1

若有n+1只鸽子飞回n个鸽巢,则至少有两只鸽子飞入了同一个鸽巢.这个原理的证明非常容易,只要使用反证法马上就可以得到结论.这个原理也可以表述为:

如果把n+1件东西放入n个盒子中,则至少有一个盒子里面有不少于两件的东西.

鸽巢原理不能用来寻找究竟是哪个盒子含有两件或更多件东西.该原理只能证明某种安排或某种现象存在,而并未指出怎样构造这种安排或怎样寻找这种现象出现的场合.从鸽巢原理出发,对于许多实际问题,我们可以导出非常有趣的结果.利用鸽巢原理解决实际问题的关键是要看出这是一个鸽巢问题,建立“鸽巢”，寻找“鸽子”.例1.

如果有13个人其中必然有两个人出生在同一个月.例2.

如果鞋架上放10双鞋,从中任意取11只,其中至少有两只恰好是配对的.例3.

从整数1,2,…,100中选51个数,证明在所选的数中间必然存在两个整数,其中之一可以被另一个整除.证明对于任何一个整数x,总可以把x写成x=2na形式,其中a是奇数,n0.

1到100之间一共有50个奇数,由所选的51个数利用上述方式可以得到51个奇数,其中必然有两个相同,设这两个数为:x=2ra,y=2sa,如果rs,那么x|y;

如果r>s,

那么y|x.

本例中:鸽子=去掉2因子得到的奇数;

鸽巢=1到100之间奇数.这个例子可以推广到从1,2,…,2n中任意取n+1个数,其中必然存在两个数,其中一个整除另外一个,证法类似.例4.

在一个边长为1的正三角形中任意取5个点,必然有两个点之间距离不超过1/2.在边长为1的正六边形中,任意选取7个点,必然有两个点之间的距离不超过1.只要通过画图,找出相应的鸽子和鸽巢就可以解决问题.利用鸽巢原理解决问题的关键在于:

辨认问题,建立鸽巢,寻找鸽子.证明：设所取n+1个数是a1,a2,…,an,an+1，对该序列中的每一个数去掉一切2的因子，直至剩下一个奇数为止，即ri=ai/2x

，x=0,1,2,…。结果得由奇数组成的序列R：r1,r2,…,rn,rn+1。1到2n中只有n个奇数，故序列R中至少有两个数是相同的。设为 ，对应的有，则ai是aj的倍数。例5、从1到2n的正整数中任取n+1个，则这n+1个数中至少有一对数，其中一个数是另一个数的倍数（n≥1）。

证明：构造一个序列则此时有两种可能：（1）若这m个和中有一个sh(1≤h≤m)是m的倍数，则结论成立。（2）若这m个和中没有一个

是m的倍数，则这些和被m除时必有1,2,…,m-1这样的余数。由于有m个和，且只有m-1个余数，于是我们可以构造m-1个盒子，第i个“盒子”是被m除余数为i的数，(i=1,2,…,m-1)。由鸽笼原理知，用m除各和时，至少有两个和的余数是相同的。则存在整数k和l(k＜l)，使得sk和sl

被m除有相同的余数，即sk≡sl

modm。故例6、设a1a2…am是正整数的序列，则至少存在整数k和l，1≤k＜l≤m，使得和ak+1+ak+2+…+al是m的倍数。（m≥2）例7、证明：把5个顶点放到边长为2的正方形中，至少存在两个顶点，它们之间的距离小于或等于。证明：把边长为2的正方形分成四个全等的边长为1的小正方形，则每个小正方形的对角线长为。如果把每个小正方形当作一个盒子，由鸽笼原理知，把5个顶点放到4个盒子中，必有一个盒子中放入了两个顶点。即必有一个小正方形中有2个顶点；而小正方形的对角线长为，也就是说小正方形中任意两点的最大距离为。这就证明了本题。一般形式鸽巢原理定理2

设m1,m2,,mn均为正整数,如果有m1+m2++mn-n+1只鸽子飞回n个鸽巢,则或者第1个鸽巢至少有m1只鸽子,或者第2个鸽巢至少有m2只鸽子,,或者第n个鸽巢至少有mn只鸽子. 证明用反证法.假若第1鸽巢少于m1只鸽子,第2鸽巢少于m2个鸽子,…,第n鸽巢少于mn只鸽子,则鸽子总数至多为:(m1-1)+(m2-1)+…+(mn-1)=m1+m2+…+mn-n,这比假定的鸽子数少了一个,矛盾.

从定理2可得出以下推论：推论1

如果m1=m2==mn=r,若将n(r-1)+1个球放入n个盒子中,则至少有一个盒子含有不少于r个球.推论2

如果n个正整数m1,m2,,mn的平均数(m1+m2++mn)/n>r-1,则m1,m2,,mn中至少有一个正整数不会小于r.推论3

有m个球放入n个盒子,则至少有一个盒子中有不少于[(m-1)/n]+1个球.例8.

随意给一个正十边形的10个顶点标上号码1,2,…,10,

求证:必然有一个顶点,该顶点及与之相邻的两个顶点的标号之和不小于17.

证明设v1,v2,…,v10是正十边形的10个顶点,ai表示顶点vi及与vi相邻的两个顶点标号之和,则

a1+a2+…+a10=(1+2+…+10)3=165>(17-1)10+1

这样必然有某个ak17.定理3(Erdös)由n2+1个不同实数构成的序列中,至少存在由n+1个实数组成一个单调递增子序列或单调递减子序列.证设原序列为:令mi表示从ai开始最长递增子序列的长度.若有某个min+1,则定理得证.

因为给定的序列有n2+1个实数,故可产生n2+1个长度:如果全部的mi<n+1,则这些整数必定在1到n之间,相当于把n2+1个球放入n个盒子.由定理2的推论1可知,这是r=n+1的特殊情况,这n2+1个mi中至少有n+1个数相等.不妨设且1i1<i2<<in+1n2+1,则可以得到下面的长度为n+1的递减序列:例题例9、将两个大小不一的圆盘分别分成200个相等的扇形。在大圆盘上任取100个扇形染成红色，另外的100个扇形染成蓝色，并将小圆盘上的扇形任意染成红色或蓝色，然后将小圆盘放在大圆盘上且中心重合时，转动小圆盘可使其每一扇形都叠放于大圆盘的某一扇形内。证明：当适当转动小圆盘可使叠放的扇形对中，同色者至少100对。

证明：设使大小两盘中心重合，固定大盘，转动小盘，则有200个不同的位置使小盘上的每个小扇形含在大盘上的小扇形中，（将这200种可能的位置看作200个不同的盒子）。由于大盘上的200个小扇形中有100个染成红色，100个染成蓝色，所以小盘上的每个小扇形在转动过程中，无论染成红色或蓝色，在200个可能的重合位置上恰好有100次与大盘上的小扇形同色（将同色的扇形看作放入盒子的物体）。因而小盘上的200个小扇形在200个重合位置上共同色100200=20000次。而20000＞200(100-1)+1，由推论2.2.2知，存在着某个位置，使同色的小扇形数大于等于100个。例10、将[1,67]划分为４个子集，必有一个子集中有一数是同子集中的两数之差（或和）。证明：设从1到67的整数任意分成4部分p1,p2,p3,p4，作如下分析：①由鸽笼原理知，1到67的整数中必有一部分，不妨设为p1,至少有(67-1)/4+1=17个元素。并设这17个元素为a1＜a2＜…＜a17，若ai中存在一个元素是某两个元素之差，则命题得证。否则，令b1=a2-a1,b2=a3-a1,…,b16=a17-a1，显然1≤bi＜67，故bi不属于p1，属于p2,p3或p4。②同理，bi中至少有(17-1)/3+1=6个元素属于p2，设这6个元素为c1＜c2＜…＜c6，若ci中存在一个元素是某两个元素之差，则命题得证。否则，令d1=c2-c1,d2=c3-c1,…,d5=c6-c1，显然1≤di＜67，且存在1≤l,m≤17,di=ci-c1=al-am,i=1,2,…,5，故di不属于p1,p2，属于p3,p4。③di中至少有(6-1)/2+1=3个元素属于p3，设这3个元素为f1＜f2＜f3，若fi中存在一个元素是某两个元素之差，则命题得证。否则，令g1=f2-f1,g2=f3-f1，显然1≤gi＜67，且存在1≤l,m≤17,gi=fi-f1=al-am,i=1,2

，故fi不属于p1,p2,p3，属于p4。④若g1=g2-g1，则命题得证。否则，令h=g2-g1，显然1≤h＜67，且同上可以证明h不属于p1,p2,p3,p4中任一个，与已知矛盾。例11、证明：在每个包含n2+1个不同的实数的序列中，存在一个长度为n+1的递增子序列，或者存在一个长度为n+1的递减子序列。（一个序列的长度是指该序列的元素个数）。证明：设 是一个实数序列，并假设在这个序列中没有长度为n+1的递增子序列，则要证明一定有一个长度为n+1的递减子序列。令表示以为首项的最长递增子序列的长度 则对每个k

，由假设知道这相当于把个物品放入个盒子中，由推论2.2.2知，必有一个盒子里面至少有个物品，即存在及 ，使得对应于这些下标的实数序列必满足它们构成一长为的递减子序列。否则，若有某个使得 ，那么以 为首项的最长递增子序列加上 ，就得到一个以为首项的递增子序列，由定义知，这与 矛盾。因此， 成立。

这是一个长度为n+1的递减子序列，故结论成立。例12、将1,2,…,10随机地摆成一圆，则必有某相邻三数之和至少是17。

证明：设 表示该圆上相邻三个数之和（i居中）。这样的和共有10个。而1,2,…,10中的每一个都出现在这十个和的三个之中，故由推论2.2.3知，存在一个i

，使。Ramsey数在引出Ramsey数之前,先给出几个引理.引理1

若集合S由6个人组成,那么S中或者存在至少3个人互相认识,或者存在至少3个人互不认识.证明在6个人中,任意固定一个人A,则其余的5人可以分成两部分,一部分是由与A认识的人组成的F,另外一部分是由与A不认识的人组成的T,由鸽巢原理,这两部分至少有一部分含有3个人.|F|=3.

这时候,如果F中3个人都互相不认识,自然命题得证;如果其中至少有2个人互相认识,则这两个人与A一起组成互相认识的3个人.|T|=3.

如果T中3个人互相认识,命题得证;如果其中至少有2个人互相不认识,再添加上A即可得三个互相不认识的人.引理可以叙述为:如果对一个6个顶点的完全图的边用红、蓝两种颜色去染色,则一定存在一个单色的三角形.引理2

若集合S由10人组成,那么S中存在至少4个人互相认识,或存在至少3个人互不认识.证明在这10个人当中任意固定一个人A,则其余人可以分成两类：图1F：与A相互认识的人的集合

T:

与A相互不认识的人的集合由鸽巢原理,至少有一类含有不少于5个的人.证明可以分情况得到.若|T|3,则|F|6,由引理2,F中有3个互相认识的或者互相不认识的.如果有3个互相不认识的,引理得证;如果有3个互相认识的,再加上A就是4个互相认识的,引理成立.(2)

若|T|4,如果T中所有人都是互相认识的,引理得证;如果T中至少有两个人互相不认识,再加上A就是3个互相不认识的,引理也成立.类似方法可以证明:引理3

由10人组成的集合中或者有4人互不认识,或者至少有3人互相认识.引理4

由20人组成集合中或者有4人互相认识,或者有4人互不认识.定义1

设p,q是任意给定的正整数,而且p2,q2.

如果存在一个最小的正整数R,使得任意R个人组成的集合S,下面两件事中有一件必然成立：(1)

S中至少有p个人互相认识；(2)

S中至少有q个人互相不认识;

则称R是具有参数p,q;2的Ramsey数,并记作R(p,q;2),可省略2,而简记作R(p,q).这里我们采用了一个通俗的定义.由引理1,R(3,3)=6.关于Ramsey数的几点注释：(1)

Ramsey数可以用完全图边的2-染色来解释.

用Kn来表示n阶完全图,显然Kn共有

n(n-1)/2条边.如果用r(r2)

种颜色去染Kn的边,每条边染一种颜色,所得到的每条边都染了色的Kn称为r-染色Kn.

可以用顶点表示人,边色表示关系.

R(p,q)=nKn的任意红、蓝染色必然出现红色Kp,或者蓝色的Kq,

但是Kn-1不具备这样的性质.(2)

Ramsey数也可以用图中的独立集和团来解释.

R(p,q)=n任意n个顶点的图包含Kp

或者有一个q个点的独立集,但是存在不具备这样的性质的n-1阶图.

这时候可以理解为互相认识的人连边,

互相不认识的不连边.

Ramsey数的决定非常非常困难.要得到R(p,q)=n,须完成下面两步:(a)

Kn的任意(红,蓝)-染色必然有红色Kp或蓝色Kq;(b)

构造Kn-1的一个(红,蓝)-染色,使得其中既没有红色Kp也没有蓝色Kq.下面的表格给出目前已知的部分结果,完全的结果可以见:/Surveys/ds1/sur.ps3456789103691418232836[40,43]41825[35,41][49,61][56,84][73,115][92,149]5[43,49][58,87][80,143][101,216][125,316][143,442]6[102,165][113,298][127,495][169,780][179,1171]7[205,540][216,1031][233,1713][289,2826]8[282,1870][317,3583][317,6090]9[565,6588][580,12677]10[798,23556]Ramsey数的性质定理4

Ramsey数具下列简单性质:(1)

R(p,q)=R(q,p)(2)

R(p,2)=p,R(2,q)=q(3)

R(p,q;1)=p+q-1证明(1),(2)结论明显.(3)p+q-1=p+q-2+1,

利用鸽巢原理,元素为p+q-1的集合的任意2-划分,要么第1个集合含有不少于p个元素,要么第2个集合中含有不少于q个元素.定理5

设p,q都是大于2的正整数,则

R(p,q)R(p-1,q)+R(p,q-1).证明令R(p-1,q)+R(p,q-1)=n.

在n个人中间,任意固定一个人A,其余n-1个人可以分成两类:F:

与A相互认识的人的集合;T:

与A互相不认识的人的集合.由于n-1=R(p-1,q)+R(p,q-1)-1,

由鸽巢原理,|F|R(p-1,q)或者|T|R(p,q-1).(1)

|F|R(p-1,q).

此时由R(p-1,q)的定义,F中或者有p-1个人互相认识,加上A就得到p个互相认识的人;或者有q个人互相不认识.(2)

|T|R(p,q-1).此时由R(p,q-1)的定义,T中或者有p个人互相认识;或者有q-1个互相不认识的,再加上A就得到q个互相不认识的人.因此任意n个人中间一定有p个互相认识,或者有q个人互相不认识.定理6

设p,q都是大于2的正整数,当R(p-1,q)和R(p,q-1)都是偶数时,有

R(p,q)R(p-1,q)+R(p,q-1)-1.推论1

R(3,4)=9.证明因为R(2,4)=4,R(3,3)=6,所以由定理6,有R(3,4)R(2,4)+R(3,3)-1=4+6-1=9.由下图中构造一个(红,蓝)-着色K8不含有蓝色K3也不含有红色K4.R(3,4)>8,从而可得R(3,4)=9.图2推论2

R(3,5)=14.证明

因为R(2,5)=5,R(3,4)=9,由定理5,R(3,5)R(2,5)+R(3,4)=5+9=14.然后构造一个红、蓝染色的K13,其中没有红色的K3,也没有蓝色的K5.(图略)推论3

设p,q是大于1的正整数,则

R(p,q)C(p+q-2,p-1)。[证明:

利用定理5对p+q作归纳.]推论4R(n,n)C(2n-2,n-1)n-1/222n-2。猜想(Erdös,500$)

R(n,n)=2cn+o(n)。(c=1?)Ramsey定理Ramsey定理（蕴涵了Ramsey数的存在性）是由英国青年数学家F.P.Ramsey从鸽巢原理出发,于1928年给出的一个重要定理,因此把它称为Ramsey定理.Ramsey定理设p1,p2,,pn,t是正整数,且p1t,p2t,,pnt,

那么存在一个最小的正整数R(p1,p2,,pn;t),它仅依赖于p1,p2,,pn和t,并具有下面性质:如果S是m个元素的集合:当mR(p1,p2,,pn;t)时,把S的t元子集分布在n个盒子中,那么或者有p1个元素使它们的全部t元子集都分布在第一个盒子中,或者有p2个元素使它们的全部t元子集分布在第二个盒子中,,或者第n个盒子中有pn个元素使它们的全部t元子集分布在第n个盒子中.上述定理中的R(p1,p2,,pn;t)称为推广的Ramsey数.当t=1时,定理必定存在一个最小的正整数R(p1,p2,,pn;1),并具有如下性质：如果mR(p1,p2,,pn;1),将一个m元集合S的元素分布在n个盒子中,那么或者第一个盒子含有p1个元素,或者第二个盒子含有p2个元素,,或者第n个盒子含有pn个元素.这正是鸽巢原理的推广形式:R(p1,p2,,pn;1)=(p1+p2++pn)-n+1下面这种特殊形式有时候更有用.推论2

对于任意给定的三个正整数p,q,r(pr,qr),总存在一个仅依赖p,q,r的最小正整数R(p,q;r).当有限集合S的元素个数N

R(p,q;r)时,对于Tr(S)的任意一个2-划分:Tr(S)=(=),则S有一个p元子集,其一切r元子集都属于,或者S有一个q元子集其一切r元子集都属于.例13

证明:R(3,3,3;2)=17.证设完全图K17的顶点集为{v1,v2,,v17},其边用红、蓝、黄三色任意着色.任取一点v1,则与v1相关联的边至少有6条边是同色的,不妨记为(v1,v2),(v1,v3),(v1,v4),(v1,v5),(v1,v6),(v1,v7)这6条边是红色的.考虑v2,v3,v4,v5,v6,v7这六个点组成的完全子图K6,它共有C(6,2)=15条边,其中只要有一条红色边,这条红色边的两端点加上v1就成了红边的K3子图,结论成立.

若这15条边中无红色,则6点完全子图的边用蓝、黄两色任意着色,由R(3,3)=6可知,或者有蓝色的K3,或者有黄色的K3,故结论成立.因此,R(3,3,3;2)17.

当有16个顶点的完全图K16用红、蓝、黄三色着色时,存在一种着色方法,可使

K16中不出现同色K3子图,可以自己试一试.这说明R(3,3,3;2)>16,