组合数学(张永刚)吉林大学-第二章-鸽巢原理和ramsey定理课件

1第二章鸽巢原理和Ramsey定理组合存在性定理Ramsey定理（鸽巢原理为其最简形式）偏序集分解定理（Dilworth定理）相异代表系存在定理（Hall定理）1928年英国数学家、哲学家兼经济学家Frank，Ramsey(1903-1930)在伦敦数学会上宣读一篇“论形式逻辑中的一个问题”的论文，奠定Ramsey理论的基础。核心思想是：“任何一个足够大的结构中必定包含一个给定大小的规则子结构”1第二章鸽巢原理和Ramsey定理组合存在性定理2第二章鸽巢原理和Ramsey定理

§2.1鸽巢原理的最简单形式§2.2鸽巢原理的加强形式§2.3Ramsey定理2第二章鸽巢原理和Ramsey定理

3§2.1鸽巢原理的最简单形式鸽巢原理(Pigeonholeprinciple)是组合学中最简单、最基本原理.也叫抽屉原理、重叠原理、狄利克雷原理。定理2.1.1若把n+1个物体放入n个盒子中，则至少有一个盒子中有2个或更多的物体3§2.1鸽巢原理的最简单形式鸽巢原理(Pigeonhol4证明：（反证法）

若不然，假定每个盒子中至多有一个物体，那么n个盒子中至多有n个物体，而我们共有n+1个物体，矛盾。故定理成立。

4证明：（反证法）5鸽巢原理的集合描述形式：

设有限集合A有n+1个元素，将A分划成n个不相交子集的并，则至少有一个子集含有两个或两个以上的元素。注意！应用时要分清物品与盒子以及物体数与盒子总数。这个原理只能用来证明某种安排的存在性，而却不能找到具体满足要求的安排

不能被推广到只存在n个(或更少)物体的情形。5鸽巢原理的集合描述形式：6例2.1.1

共有12个属相，今有13个人，则必有两人的属相相同。

几个例子例2.1.2

有5双不同的袜子混在一个抽屉里，我们至少从中选出多少只袜子才能保证找到1双袜子？

6例2.1.1共有12个属相，今有13个人，则必有两人的属7解

应用定理2.1.1，共有5个盒子，每个盒子对应1双袜子。如果选择5+1=6只袜子分别放到它所属那双袜子的盒子中，则必有两只袜子落入同一个盒子中，即为一双袜子。因此我们至少从中选出6只袜子才能保证找到1双袜子。本例实际上是知道n个盒子，而找n+1个物体的问题。

7解应用定理2.1.1，共有5个盒子，每个盒子对应1双8例2.1.3 对任意给定的52个整数，证明：其中必存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。

8例2.1.3 对任意给定的52个整数，证明：其中必存在两个9思路：把52个物体放到51个盒子中，需要构造51个盒子，根据题目要求的两个整数必须具备的性质构造盒子；是否能够被100整除的关键在余数，那么一个整数除以100的余数为0，1，2，…，99两个整数的和可以被100整除，则二者的余数的和是100两个整数的差可以被100整除，则二者的余数相同分析：9思路：分析：证明：对于任意一个整数，它除以100的余数显然只能有如下100种情况，0，1，2，3，……，99而现在有任意给定的52个整数，我们需要构造51个盒子，即对这100个余数进行分组，共51组：{0},{1，99},{2，98},{3，97},……，{49，51}，{50}10证明：对于任意一个整数，它除以100的余数显然只能有如下10根据定理2.1.1，这52个整数，必有两个整数除以100的余数落入上面51组中的同一组中，若是{0}或{50}则说明它们的和及差都能被100整除；若是剩下的49组的话，因为一组有两个余数，余数相同则它们的差能被100整除，余数不同则它们的和能被100整除。11根据定理2.1.1，这52个整数，必有两个整数除以100的余12

例2.1.4

一名象棋大师有11周时间准备一场锦标赛，她决定每天至少下一盘棋，为了不能太累，一周中下棋的次数不能多于12盘。证明：她一定在此期间的连续若干天中恰好下棋21盘。

12例2.1.4一名象棋大师有11周时间准备一场锦标13证明:令b1，b2，…，b77分别为这11周中他每天下棋的次数，并作部分和a1=b1,a2=b1+b2,…，a77=b1+b2+…+b77.13证明:令b1，b2，…，b77分别为这11周中他每天下棋14所以有1≤a1<a2<a3<…<a77≤12×11=132(2.1.1)考虑数列a1,a2,…，a77，a1+21,a2+21,…，a77+21,它们都在1与132+21=153之间，共有154项，由定理2.1.1知，其中必有两项相等根据题意，有bi≥1(1≤i≤77),且bi+bi+1+…+bi+6≤12(1≤i≤71),14所以有根据题意，有bi≥1(1≤i≤77),且bi+bi15由（2.1.1）式知a1,a2,…，a77这77项互不相等，从而a1+21,a2+21,…，a77+21这77项也互不相等，所以一定存在1≤i<j≤77，使得aj=ai+21.因此21=aj-ai=(b1+b2+…+bi+bi+1+…+bj)-(b1+b2+…+bi)=bi+1+bi+2+…+bj.这说明从第i+1天到第j天这连续j-i天中，她刚好下了21盘棋。15由（2.1.1）式知a1,a2,…，a77这77项互不相16例2.1.5

将一个矩形分成4行19列的网格，每个单元格涂1种颜色，有3种颜色可以选择。证明：无论怎样涂色，其中必有一个由单元格构成的矩形的4个角上的格子被涂上同一种颜色。16例2.1.5将一个矩形分成4行19列的网格，每个单元17证明：首先对每一列而言，因为有4行，但只有3种颜色选择。根据定理2.1.1，则必有两个单元格的颜色相同。另外，每列中两个单元格的不同位置组合有=6种，这样一列中两个同色单元格的位置组合共有18种情况，

17证明：首先对每一列而言，因为有4行，但只有3种颜色选择。而现在共有19列，根据定理2.1.1，无论怎样涂色，则必有两列与图中的某一列相同，即各自所包含的两个同色单元格的位置相同、颜色相同。即结论成立。

18而现在共有19列，根据定理2.1.1，无论怎样涂色，则必有两19例2.1.6

证明：任意n2+1个实数组成的序列中，必有一个长度为n+1的递增子序列，或必有一个长度为n+1的递减子序列。

19例2.1.6证明：任意n2+1个实数1、子序列概念

如果是一个序列，那么，是一个子序列，其中，2、递增子序列概念若满足3、递减子序列概念若满足20分析：1、子序列概念

如果21证明：由题意，设Li是从ai开始的递减子序列的最大长度，Mi是从ai开始的递增子序列的最大长度，则对于i从1到n2

+1的每个i的取值，都有（Li,Mi）与之对应。21证明：由题意，设Li是从ai开始的递减子序列的最大长度，22（1）若ai>aj，则ai与从aj开始的最长递减子序列合并，组成的子序列的长度Li

≥Lj+1

>Lj；这与Li

=Lj矛盾；反证法。假设既不存在长度为n+1的递增子序列，也不存在长度为n+1的递减子序列即1≤Li≤n

且1≤Mi≤n，其中1≤i≤n2+1，由集合论的知识知：集合{(Li,Mi)}的元素数最多为n2，根据定理2.1.1，必然有（Li,Mi）=(Lj,Mj)（i<j），当然Li

=Lj，而且Mi

=Mj。对于序列中的元素ai,aj，分两种情况：

22（1）若ai>aj，则ai与从aj开始的最长递减子序23（2）若ai<aj，则ai与从aj开始的最长递增子序列合并，组成的子序列的长度Mi

≥Mj+1>Mj，这又与Mi=Mj矛盾。所以假设1≤Li≤n

且1≤Mi≤n不成立。原结论成立。这个例子的结论是1935年由数学家保罗·艾狄胥（Erdös）和乔治·塞克尔斯（Szekeres）首先给出的，它还有更为有趣的表述：n2+1个人肩并肩地站成一排，则总能选除n+1个人，让他们向前迈出一步，所形成新一排的身高是递增或递减的。23（2）若ai<aj，则ai与从aj开始的最长递增子序24§2.2鸽巢原理的加强形式定理2.2.1(鸽巢原理的加强形式)24§2.2鸽巢原理的加强形式定理2.2.1(鸽巢原25证明：(反证法)

对于i＝1，2，…，n，假设第i个盒子里至多含有qi-1个物体，则n个盒子里物体数的总和不超过

q1+q2+…+qn-

n这与已知条件中的物体总数为(q1+q2+…+qn–

n+1)相矛盾。故假设不对，原结论成立。25证明：(反证法)26

与简单形式的关系

上节的鸽巢原理的简单形式是这一原理的特殊情况，即q1=q2=…=qn=2，有

q1+q2+…+qn－n+1=n+126与简单形式的关系27推论2.2.1

若n(r-1)+1个物体放入n个盒子。则至少有一个盒子里含有r个或者更多的物体。证明在定理2.2.1中取q1=q2=…=qn=r即可。27推论2.2.1若n(r-1)+1个物体放入n个盒28

推论2.2.2

若设有n个正整数m1,m2,…,mn满足下面的不等式

(m1+…+mn)/n>

r－1,

则

m1,…,mn中至少有一个数≥

r证明

由上面的不等式得

m1+…+mn≥

n(r－1)+1，由推论2.2.1，存在mi，使得mi≥r。28推论2.2.2若设有n个正整数m1,m2,29推论2.2.3

设m和n都是正整数且m>n，若将m个物体放入n个盒子中，则至少有一个盒子中含有大于等于个物体。表示取天棚运算是大于等于的最小正整数

证明：根据的定义有：

29推论2.2.3设m和n都是正整数且m>n，若将m个物体30反证法。假定每个盒子里的物体都小于个。，则至多是个，那么n个盒子里的物体总数≤n()<n×

=m，与m个物体矛盾。因此原结论成立。

30反证法。假定每个盒子里的物体都小于个。31例2.2.1一个袋子里装了10个苹果，11个橘子，12个香蕉，至少取出多少个水果才能保证已经取出10个相同种类的水果。解根据定推论2.2.1，若将3×(10-1)+1=28个物体放入3个盒子中，则至少有一个盒子中有10个物体。显然物体就是三种水果，而盒子就是三类水果，结论是保证已经取出10个相同种类的水果等价于或者取出10个苹果或者取出10个橘子或者取出10个香蕉。因此答案是至少取28个水果才能保证已经取出10个相同种类的水果。

31例2.2.1一个袋子里装了10个苹果，11个橘子，1232例2.2.2

一家汽车租赁公司共有105辆汽车，共有座位600个，证明至少有一辆6座以上的汽车？

证明：根据推论2.2.3，所以至少有一辆6座以上的汽车。32例2.2.2一家汽车租赁公司共有105辆汽车，共有座位33例2.2.3

设有大小两只圆盘，每个都划分成大小相等的200个小扇形，在大盘上任选100个小扇形涂成黑色，其余的100个小扇形涂成白色，而将小盘上的200个小扇形任意涂成黑色或白色。现将大小两只圆盘的中心重合，转动小盘使小盘上的每个小扇形含在大盘上小扇形之内。证明：有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色。33例2.2.3设有大小两只圆盘，每个都划分成大小相等343435证明

如图2.2.1所示，使大小两盘中心重合，固定大盘，转动小盘，则有200个不同位置使小盘上的每个小扇形含在大盘上的小扇形中，由于大盘上的200个小扇形中有100个涂成黑色，100个涂成白色，所以小盘上的每个小扇形无论涂成黑色或白色，在200个可能的重合位置上恰好有100次与大盘上的小扇形同色，因而小盘上的200个小扇形在200个重合位置上共同色100×200=20000次，平均每个位置同色20000÷200=100次。由推论2.2.3知，存在着某个位置，使同色的小扇形数大于等于100个。35证明36例2.2.4证明：任意n2+1个实数组成的序列中，必有一个长度为n+1的递增子序列，或必有一个长度为n+1的递减子序列。

36例2.2.4证明：任意n2+1个实数组成的序列中，37例2.2.4用鸽巢原理的加强形式证明证明：假设长为n2+1的实数序列中没有长度为n+1的递增子序列，下面证明其必有一长度为n+1的递减子序列。 令mk表示从ak开始的最长递增子序列的长度，因为实数序列中没有长度为n+1的递增子序列，所以有：

根据推论2.2.3，这相当于把n2+1个物体

37例2.2.4用鸽巢原理的加强形式证明证明：假设长为n238放入n个盒子1，2，…，n中，必有一个盒子i里面至少有个物体，即存在n+1个mk取值相同，有使得（2.2.1）

对应于这些下标的实数序列必满足

（2.2.2）

38放入n个盒子1，2，…，n中，必有一个盒子i里（2.2.39它们构成一长为n+1的递减序列。否则，若有某个j（）使得，那么由从开始的最长递增子序列加上，就得到一个从开始的长度为的递增子序列。由的定义知这与（2.2.1）式矛盾。因此（2.2.2）式成立。同理可证若没有长度为n+1的递减子序列，则必有一长度为n+1的递增子序列。因此，结论成立。39它们构成一长为n+1的递减序列。任何一个6人聚会，必有3个人相互认识或者相互不认识40§2.3Ramsey定理

其思想可以概括为“在任何一个足够大的结构中必定包含一个给定大小的规则子结构”。

任何一个6人聚会，必有3个人相互认识或者相互不认识40§241例2.3.1

设K6是6个顶点的完全图，用红、蓝两色涂色K6的边，则存在一个红色三角形，或存在一个蓝色三角形。证明：设K6的顶点为v1,v2,…,v6。对于K6的任何一种涂色方案，由推论2.2.3.，v1关联的边中必有条同色边。不妨设这三条边为{v1

,v2},{v1

,v3},{v1,v4}

41例2.3.1设K6是6个顶点的完全图，用红、蓝两色涂色42若这三边为红色，当v2,v3,v4之间有一条红边，比如说是{v2,v3},则v1v2v3构成一个红三角形；当v2,v3

,v4之间没有红边，则v2v3v4构成一个蓝三角形。若这三边为蓝色时，同理可证。因此，结论成立。

v2

v3

v4v142若这三边为红色，当v2,v3,v4之间有一条红边，定理2.3.1

设p，q是正整数，p，q≥2，则存在最小的正整数R(p,q)，使得当n≥R(p,q)时，用红、蓝两色涂色Kn的边，或者存在一个蓝色的完全p边形Kp，或者存在一个红色的完全q边形Kq。

43证明：采用数学归纳法。 设p为任意正整数，q=2。用红、蓝两色涂色Kp的边，若没有一条红边，则存在一个蓝色的完全p边形；若有一条红边，则构成一个完全红2边形，因此R(p,2)≤p。同理可证R(2,q)≤q。定理2.3.1设p，q是正整数，p，q≥2，则存在最小44假设对一切正整数p,q(p+q<p+q)命题为真。令n≥R(p-1,q)+R(p,q-1)。用红、蓝两色涂色Kn的边，则v1或关联R(p-1,q)条蓝边或关联R(p,q-1)条红边。如若不然，v1至多关联R(p-1,q)-1+R(p,q-1)-1=R(p-1,q)+R(p,q-1)-2条边，与n≥R(p-1,q)+R(p,q-1)矛盾。若v1关联R(p-1,q)条蓝边，由归纳假设这R(p-1,q)个顶点中或含有一个蓝色的完全p-1边形，或含有一个红色的完全q边形。如为前者，则这个p-1边形加上v1构成一个蓝色的完全p边形，命题为真；如为后者，命题也为真。

44假设对一切正整数p,q(p+q<p+q)命题为45若v1关联R(p,q-1)条红边，同理可证Kn中必含有一个蓝色的完全p边形或红色的完全q边形，从而证明了R(p,q)≤R(p-1,q)+R(p,q-1).因此结论成立。

例2.3.2

证明：R(3,3)=6

证明：由例2.3.1知R(3,3)≤6。而图2.3.2中的实线代表蓝色的边，虚线代表红色的边，则这个的涂色方案既不包含蓝三角形，也不包含红三角形。所以R(3,3)>5。因此R(3,3)=6。

45若v1关联R(p,q-1)条红边，同理可证Kn中必含有一464647定理2.3.2

设p,q是正整数，p，q≥2，则

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

证明：令n≥R(p,q)。对于蓝、红两色涂色Kn的边的任何一种方案，将蓝边换红边，红边换蓝边，则或存在一个蓝色的完全p边形，或存在一个红色的完全q边形。而原来的涂色方案中必存在一个红色的完全p边形或一个蓝色的完全q边形，即R(q,p)≥R(p,q)。同理可证R(p,q)≥R(q,p)。因此，R(p,q)=R(q,p)47定理2.3.2设p,q是正整数，p，q≥2，则

(22February1903–19January1930)wasaBritish

mathematicianwho,inadditiontomathematics,madesignificantandprecociouscontributionsinphilosophyandeconomicsbeforehisdeathattheageof26.HewasaclosefriendofLudwigWittgenstein,andwasinstrumentalintranslatingWittgenstein'sTractatusLogico-PhilosophicusintoEnglish,andinpersuadingWittgensteintoreturntophilosophyandCambridge.48FrankPlumptonRamsey(22February1903–19January生于剑桥，其父亲是麦格达伦学院的校长，其弟弟迈克尔·拉姆齐是第100任坎特伯里大主教。拉姆齐于温切斯特公学学习，后来进入剑桥大学三一学院学习数学。他涉猎了很多领域。在政治上，他有左翼的倾向；宗教上，其妻指他是个态度坚定的无神论者。他和查尔斯·凯·奥格顿聊天时，说他想学德语。奥格顿便给他一本文法书、字典和一篇深奥的心理学论文并告诉他：使用那本文法书和字典，告诉我们你的想法。约一星期后，他不止学会了德语，还对语法书中一些理论提出了反对意见。他阅读了维根斯坦的TractatusLogico-Philosophicus。这本书深深影响了他，1923年他去奥地利跟维根斯坦讨论。1924年21岁的他成为国王学院的研究员。拉姆齐为治疗慢性肝疾而接受腹部手术，但术后并发黄疸，于1930年1月19日病逝于伦敦盖氏医院（Guy'sHospital），得年仅26岁又11个月。49弗兰克·拉姆齐(FrankPlumptonRamsey,1903.2.22-1930.1.19)生于剑桥，其父亲是麦格达伦学院的校长，其弟弟迈克尔·拉姆齐是5050保罗·埃尔德什（ErdősPál，在英语中作PaulErdős）（1913年3月26日－1996年9月20日），其音读作air-dish，匈牙利语中的意思是来自山林。匈牙利籍犹太人，发表论文高达1475篇（包括与人合写的），为现时发表论文数最多产的数学家（其次是欧拉）；曾和511人合写论文。爱多士遗传了来自数学教师父母优异的数学天赋，三岁时就能轻松心算一个人一生所活的秒数，并每日在客人面前表演四位数的乘法心算。他年仅二十一岁即被厄特沃什·罗兰大学(即布达佩斯大学)授予数学博士学位，师从数学家LipótFejér(他也是冯纽曼的导师)。之后爱多士为了逃离纳粹的追捕，历任曼彻斯特大学教授与普林斯顿大学之研究人员。爱多士热爱自由，十分讨厌权威，尤其是法西斯。他四处游历，探访当地的数学家，与他们一起工作，合写论文。他很重视数学家的培训，遇到有天份的孩子，会鼓励他们继续研究。爱多士经常沉思于数学问题，视数学为生命，在母亲死后，他开始经常服食精神药物。他经常长时间工作，老年仍每日工作19小时，酷爱饮咖啡，曾说“数学家是将咖啡转换成定理的机器”。因为爱多士和别人合写的论文实在太多了，所以有人定义了埃尔德什数，简称埃数。爱多士的爱多士数为0，与他直接合作写论文的人的埃数为1，与埃数为1的人合写论文的人埃数为2，依此类推。爱多士十分独持。除了衣食住行这些生活基本要知道的事之外，他对很多问题都毫不关心，终生未婚，年轻时甚至被人误以为是同性恋者，但其实他无论对异性或是同性都没有什么兴趣。事实上，他是一个博学的人，对历史了如指掌，但长大后只专注数学，任何其他事情也不管。爱多士说话有自己的一套“密语”，用各种有趣的名词来代替神、美国、孩子和婚姻等，如上帝被叫SF（SupremeFascist，最大的法西斯的简称），小孩子被叫作epsilon（希腊语字母ε，数学中用于表示小量），美国被叫作山姆（Sam），苏联被叫作乔（Joe）。51PaulErdős保罗·埃尔德什（ErdősPál，在英语中作PaulEr525253第二章鸽巢原理和Ramsey定理组合存在性定理Ramsey定理（鸽巢原理为其最简形式）偏序集分解定理（Dilworth定理）相异代表系存在定理（Hall定理）1928年英国数学家、哲学家兼经济学家Frank，Ramsey(1903-1930)在伦敦数学会上宣读一篇“论形式逻辑中的一个问题”的论文，奠定Ramsey理论的基础。核心思想是：“任何一个足够大的结构中必定包含一个给定大小的规则子结构”1第二章鸽巢原理和Ramsey定理组合存在性定理54第二章鸽巢原理和Ramsey定理

§2.1鸽巢原理的最简单形式§2.2鸽巢原理的加强形式§2.3Ramsey定理2第二章鸽巢原理和Ramsey定理

55§2.1鸽巢原理的最简单形式鸽巢原理(Pigeonholeprinciple)是组合学中最简单、最基本原理.也叫抽屉原理、重叠原理、狄利克雷原理。定理2.1.1若把n+1个物体放入n个盒子中，则至少有一个盒子中有2个或更多的物体3§2.1鸽巢原理的最简单形式鸽巢原理(Pigeonhol56证明：（反证法）

若不然，假定每个盒子中至多有一个物体，那么n个盒子中至多有n个物体，而我们共有n+1个物体，矛盾。故定理成立。

4证明：（反证法）57鸽巢原理的集合描述形式：

设有限集合A有n+1个元素，将A分划成n个不相交子集的并，则至少有一个子集含有两个或两个以上的元素。注意！应用时要分清物品与盒子以及物体数与盒子总数。这个原理只能用来证明某种安排的存在性，而却不能找到具体满足要求的安排

不能被推广到只存在n个(或更少)物体的情形。5鸽巢原理的集合描述形式：58例2.1.1

共有12个属相，今有13个人，则必有两人的属相相同。

几个例子例2.1.2

有5双不同的袜子混在一个抽屉里，我们至少从中选出多少只袜子才能保证找到1双袜子？

6例2.1.1共有12个属相，今有13个人，则必有两人的属59解

应用定理2.1.1，共有5个盒子，每个盒子对应1双袜子。如果选择5+1=6只袜子分别放到它所属那双袜子的盒子中，则必有两只袜子落入同一个盒子中，即为一双袜子。因此我们至少从中选出6只袜子才能保证找到1双袜子。本例实际上是知道n个盒子，而找n+1个物体的问题。

7解应用定理2.1.1，共有5个盒子，每个盒子对应1双60例2.1.3 对任意给定的52个整数，证明：其中必存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。

8例2.1.3 对任意给定的52个整数，证明：其中必存在两个61思路：把52个物体放到51个盒子中，需要构造51个盒子，根据题目要求的两个整数必须具备的性质构造盒子；是否能够被100整除的关键在余数，那么一个整数除以100的余数为0，1，2，…，99两个整数的和可以被100整除，则二者的余数的和是100两个整数的差可以被100整除，则二者的余数相同分析：9思路：分析：证明：对于任意一个整数，它除以100的余数显然只能有如下100种情况，0，1，2，3，……，99而现在有任意给定的52个整数，我们需要构造51个盒子，即对这100个余数进行分组，共51组：{0},{1，99},{2，98},{3，97},……，{49，51}，{50}62证明：对于任意一个整数，它除以100的余数显然只能有如下10根据定理2.1.1，这52个整数，必有两个整数除以100的余数落入上面51组中的同一组中，若是{0}或{50}则说明它们的和及差都能被100整除；若是剩下的49组的话，因为一组有两个余数，余数相同则它们的差能被100整除，余数不同则它们的和能被100整除。63根据定理2.1.1，这52个整数，必有两个整数除以100的余64

例2.1.4

一名象棋大师有11周时间准备一场锦标赛，她决定每天至少下一盘棋，为了不能太累，一周中下棋的次数不能多于12盘。证明：她一定在此期间的连续若干天中恰好下棋21盘。

12例2.1.4一名象棋大师有11周时间准备一场锦标65证明:令b1，b2，…，b77分别为这11周中他每天下棋的次数，并作部分和a1=b1,a2=b1+b2,…，a77=b1+b2+…+b77.13证明:令b1，b2，…，b77分别为这11周中他每天下棋66所以有1≤a1<a2<a3<…<a77≤12×11=132(2.1.1)考虑数列a1,a2,…，a77，a1+21,a2+21,…，a77+21,它们都在1与132+21=153之间，共有154项，由定理2.1.1知，其中必有两项相等根据题意，有bi≥1(1≤i≤77),且bi+bi+1+…+bi+6≤12(1≤i≤71),14所以有根据题意，有bi≥1(1≤i≤77),且bi+bi67由（2.1.1）式知a1,a2,…，a77这77项互不相等，从而a1+21,a2+21,…，a77+21这77项也互不相等，所以一定存在1≤i<j≤77，使得aj=ai+21.因此21=aj-ai=(b1+b2+…+bi+bi+1+…+bj)-(b1+b2+…+bi)=bi+1+bi+2+…+bj.这说明从第i+1天到第j天这连续j-i天中，她刚好下了21盘棋。15由（2.1.1）式知a1,a2,…，a77这77项互不相68例2.1.5

将一个矩形分成4行19列的网格，每个单元格涂1种颜色，有3种颜色可以选择。证明：无论怎样涂色，其中必有一个由单元格构成的矩形的4个角上的格子被涂上同一种颜色。16例2.1.5将一个矩形分成4行19列的网格，每个单元69证明：首先对每一列而言，因为有4行，但只有3种颜色选择。根据定理2.1.1，则必有两个单元格的颜色相同。另外，每列中两个单元格的不同位置组合有=6种，这样一列中两个同色单元格的位置组合共有18种情况，

17证明：首先对每一列而言，因为有4行，但只有3种颜色选择。而现在共有19列，根据定理2.1.1，无论怎样涂色，则必有两列与图中的某一列相同，即各自所包含的两个同色单元格的位置相同、颜色相同。即结论成立。

70而现在共有19列，根据定理2.1.1，无论怎样涂色，则必有两71例2.1.6

证明：任意n2+1个实数组成的序列中，必有一个长度为n+1的递增子序列，或必有一个长度为n+1的递减子序列。

19例2.1.6证明：任意n2+1个实数1、子序列概念

如果是一个序列，那么，是一个子序列，其中，2、递增子序列概念若满足3、递减子序列概念若满足72分析：1、子序列概念

如果73证明：由题意，设Li是从ai开始的递减子序列的最大长度，Mi是从ai开始的递增子序列的最大长度，则对于i从1到n2

+1的每个i的取值，都有（Li,Mi）与之对应。21证明：由题意，设Li是从ai开始的递减子序列的最大长度，74（1）若ai>aj，则ai与从aj开始的最长递减子序列合并，组成的子序列的长度Li

≥Lj+1

>Lj；这与Li

=Lj矛盾；反证法。假设既不存在长度为n+1的递增子序列，也不存在长度为n+1的递减子序列即1≤Li≤n

且1≤Mi≤n，其中1≤i≤n2+1，由集合论的知识知：集合{(Li,Mi)}的元素数最多为n2，根据定理2.1.1，必然有（Li,Mi）=(Lj,Mj)（i<j），当然Li

=Lj，而且Mi

=Mj。对于序列中的元素ai,aj，分两种情况：

22（1）若ai>aj，则ai与从aj开始的最长递减子序75（2）若ai<aj，则ai与从aj开始的最长递增子序列合并，组成的子序列的长度Mi

≥Mj+1>Mj，这又与Mi=Mj矛盾。所以假设1≤Li≤n

且1≤Mi≤n不成立。原结论成立。这个例子的结论是1935年由数学家保罗·艾狄胥（Erdös）和乔治·塞克尔斯（Szekeres）首先给出的，它还有更为有趣的表述：n2+1个人肩并肩地站成一排，则总能选除n+1个人，让他们向前迈出一步，所形成新一排的身高是递增或递减的。23（2）若ai<aj，则ai与从aj开始的最长递增子序76§2.2鸽巢原理的加强形式定理2.2.1(鸽巢原理的加强形式)24§2.2鸽巢原理的加强形式定理2.2.1(鸽巢原77证明：(反证法)

对于i＝1，2，…，n，假设第i个盒子里至多含有qi-1个物体，则n个盒子里物体数的总和不超过

q1+q2+…+qn-

n这与已知条件中的物体总数为(q1+q2+…+qn–

n+1)相矛盾。故假设不对，原结论成立。25证明：(反证法)78

与简单形式的关系

上节的鸽巢原理的简单形式是这一原理的特殊情况，即q1=q2=…=qn=2，有

q1+q2+…+qn－n+1=n+126与简单形式的关系79推论2.2.1

若n(r-1)+1个物体放入n个盒子。则至少有一个盒子里含有r个或者更多的物体。证明在定理2.2.1中取q1=q2=…=qn=r即可。27推论2.2.1若n(r-1)+1个物体放入n个盒80

推论2.2.2

若设有n个正整数m1,m2,…,mn满足下面的不等式

(m1+…+mn)/n>

r－1,

则

m1,…,mn中至少有一个数≥

r证明

由上面的不等式得

m1+…+mn≥

n(r－1)+1，由推论2.2.1，存在mi，使得mi≥r。28推论2.2.2若设有n个正整数m1,m2,81推论2.2.3

设m和n都是正整数且m>n，若将m个物体放入n个盒子中，则至少有一个盒子中含有大于等于个物体。表示取天棚运算是大于等于的最小正整数

证明：根据的定义有：

29推论2.2.3设m和n都是正整数且m>n，若将m个物体82反证法。假定每个盒子里的物体都小于个。，则至多是个，那么n个盒子里的物体总数≤n()<n×

=m，与m个物体矛盾。因此原结论成立。

30反证法。假定每个盒子里的物体都小于个。83例2.2.1一个袋子里装了10个苹果，11个橘子，12个香蕉，至少取出多少个水果才能保证已经取出10个相同种类的水果。解根据定推论2.2.1，若将3×(10-1)+1=28个物体放入3个盒子中，则至少有一个盒子中有10个物体。显然物体就是三种水果，而盒子就是三类水果，结论是保证已经取出10个相同种类的水果等价于或者取出10个苹果或者取出10个橘子或者取出10个香蕉。因此答案是至少取28个水果才能保证已经取出10个相同种类的水果。

31例2.2.1一个袋子里装了10个苹果，11个橘子，1284例2.2.2

一家汽车租赁公司共有105辆汽车，共有座位600个，证明至少有一辆6座以上的汽车？

证明：根据推论2.2.3，所以至少有一辆6座以上的汽车。32例2.2.2一家汽车租赁公司共有105辆汽车，共有座位85例2.2.3

设有大小两只圆盘，每个都划分成大小相等的200个小扇形，在大盘上任选100个小扇形涂成黑色，其余的100个小扇形涂成白色，而将小盘上的200个小扇形任意涂成黑色或白色。现将大小两只圆盘的中心重合，转动小盘使小盘上的每个小扇形含在大盘上小扇形之内。证明：有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色。33例2.2.3设有大小两只圆盘，每个都划分成大小相等863487证明

如图2.2.1所示，使大小两盘中心重合，固定大盘，转动小盘，则有200个不同位置使小盘上的每个小扇形含在大盘上的小扇形中，由于大盘上的200个小扇形中有100个涂成黑色，100个涂成白色，所以小盘上的每个小扇形无论涂成黑色或白色，在200个可能的重合位置上恰好有100次与大盘上的小扇形同色，因而小盘上的200个小扇形在200个重合位置上共同色100×200=20000次，平均每个位置同色20000÷200=100次。由推论2.2.3知，存在着某个位置，使同色的小扇形数大于等于100个。35证明88例2.2.4证明：任意n2+1个实数组成的序列中，必有一个长度为n+1的递增子序列，或必有一个长度为n+1的递减子序列。

36例2.2.4证明：任意n2+1个实数组成的序列中，89例2.2.4用鸽巢原理的加强形式证明证明：假设长为n2+1的实数序列中没有长度为n+1的递增子序列，下面证明其必有一长度为n+1的递减子序列。 令mk表示从ak开始的最长递增子序列的长度，因为实数序列中没有长度为n+1的递增子序列，所以有：

根据推论2.2.3，这相当于把n2+1个物体

37例2.2.4用鸽巢原理的加强形式证明证明：假设长为n290放入n个盒子1，2，…，n中，必有一个盒子i里面至少有个物体，即存在n+1个mk取值相同，有使得（2.2.1）

对应于这些下标的实数序列必满足

（2.2.2）

38放入n个盒子1，2，…，n中，必有一个盒子i里（2.2.91它们构成一长为n+1的递减序列。否则，若有某个j（）使得，那么由从开始的最长递增子序列加上，就得到一个从开始的长度为的递增子序列。由的定义知这与（2.2.1）式矛盾。因此（2.2.2）式成立。同理可证若没有长度为n+1的递减子序列，则必有一长度为n+1的递增子序列。因此，结论成立。39它们构成一长为n+1的递减序列。任何一个6人聚会，必有3个人相互认识或者相互不认识92§2.3Ramsey定理

其思想可以概括为“在任何一个足够大的结构中必定包含一个给定大小的规则子结构”。

任何一个6人聚会，必有3个人相互认识或者相互不认识40§293例2.3.1

设K6是6个顶点的完全图，用红、蓝两色涂色K6的边，则存在一个红色三角形，或存在一个蓝色三角形。证明：设K6的顶点为v1,v2,…,v6。对于K6的任何一种涂色方案，由推论2.2.3.，v1关联的边中必有条同色边。不妨设这三条边为{v1

,v2},{v1

,v3},{v1,v4}

41例2.3.1设K6是6个顶点的完全图，用红、蓝两色涂色94若这三边为红色，当v2,v3,v4之间有一条红边，比如说是{v2,v3},则v1v2v3构成一个红三角形；当v2,v3

,v4之间没有红边，则v2v3v4构成一个蓝三角形。若这三边为蓝色时，同理可证。因此，结论成立。

v2

v3

v4v142若这三边为红色，当v2,v3,v4之间有一条红边，定理2.3.1

设p，q是正整数，p，q≥2，则存在最小的正整数R(p,q)，使得当n≥R(p,q)时，用红、蓝两色涂色Kn的边，或者存在一个蓝色的完全p边形Kp，或者存在一个红色的完全q边形Kq。

95证明：采用数学归纳法。 设p为任意正整数，q=2。用红、蓝两色涂色Kp的边，若没有一条红边，则存在一个蓝色的完全p边形；若有一条红边，则构成一个完全红2边形，因此R(p,2)≤p。同理可证R(2,q)≤q。定理2.3.1设p，q是正整数，p，q≥2，则存在最小96假设对一切正整数p,q(p+q<p+q)命题为真。令n≥R(p-1,q)+R(p,q-1)。用红、蓝两色涂色Kn的边，则v1或关联R(p-1,q)条蓝边或关联R(p,q-1)条红边。如若不然，v1至多关联R(p-1,q)-1+R(p,q-1)-1=R(p-1,q)+R(p,q-1)-2条边，与n≥R(p-1,q)+R(p,q-1)矛盾。若v1关联R(p-1,q)条蓝边，由归纳假设这R(p-1,q)个顶点中或含有一个蓝色的完全p-1边形，或含有一个红色的完全q边形。如为前者，则这个p-1边形加上v1构成一个蓝色的完全p边形，命题为真；如为后者，命题也为真。

44假设对一切正整数p,q(p+q<p+q)命题为97若v1关联R(p,q-1)条红边，同理可证Kn中必含有一个蓝色的完全p边形或红色的完全q边形，从而证明了R(p,q)≤R(p-1,q)+R(p,q-1).因此结论成立。

例2.3.2

证明：R(3,3)=6

证明：由例2.3.1知R(3,3)≤6。而图2.3.2中的实线代表蓝色的边，虚线代表红色的边，则这个的涂色方案既不包含蓝三角形，也不包含红三角形。所以R(3,3)>5。因此R(3,3)=6。

45若v1关联R(p,q-1)条红边，同理可证Kn中必含有一984699定理2.3.2

设p,q是正整数，p，q≥2，则

R(p,q)=R(q