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

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

2、子结构一个给定大小的规则子结构”23鸽巢鸽巢原理原理(Pigeonhole principle)是是组合学中最组合学中最简单、最简单、最基本原理基本原理.也叫也叫抽屉原理、重叠原理抽屉原理、重叠原理、狄利克雷原理狄利克雷原理。定理定理2.1.1若把n+1个物体放入n个盒子中，则至少有一个盒子中有2个或更多的物体4证明：证明：（反证法）（反证法）若不然，假定若不然，假定每个盒子中至多有一每个盒子中至多有一个物体，那么个物体，那么n个盒子中至多有个盒子中至多有n个物体，个物体，而我们共有而我们共有n+1个物体，矛盾。个物体，矛盾。故定理成立。故定理成立。5 鸽巢原理的鸽巢原理的集合描述形式集合描述

3、形式：设有限集合设有限集合A有有n+1个元素，将个元素，将A分划成分划成n个不个不相交子集的并，则至少有一个子集含有两个或两相交子集的并，则至少有一个子集含有两个或两个以上的元素。个以上的元素。注意！注意！应用时要分清物品与盒子以及物体数与盒子应用时要分清物品与盒子以及物体数与盒子 总数。总数。这个原理只能用来证明某种安排的这个原理只能用来证明某种安排的存在性存在性，而，而 却不能找到具体满足要求的安排却不能找到具体满足要求的安排 不能被推广到只存在不能被推广到只存在n个个(或更少或更少)物体的情形。物体的情形。6例例2.1.1 共有共有12个属相，今有个属相，今有13个人，则个人，则必有两人

4、的属相相同。必有两人的属相相同。几个例子几个例子例例2.1.2 有有5双不同的袜子混在一个抽屉双不同的袜子混在一个抽屉里，我们至少从中选出多少只袜子才能里，我们至少从中选出多少只袜子才能保证找到保证找到1双袜子？双袜子？7解解 应用定理应用定理2.1.1，共有，共有5个盒子，每个个盒子，每个盒子对应盒子对应1双袜子。双袜子。如果选择如果选择5+1=6只袜子分别放到它所只袜子分别放到它所属那双袜子的盒子中，则必有两只袜子落属那双袜子的盒子中，则必有两只袜子落入同一个盒子中，即为一双袜子。因此我入同一个盒子中，即为一双袜子。因此我们至少从中选出们至少从中选出6只袜子才能保证找到只袜子才能保证找到1

5、双双袜子。袜子。本例实际上是知道本例实际上是知道n个盒子，而找个盒子，而找n+1个个物体的问题。物体的问题。8例例2.1.3对任意给定的对任意给定的52个整数，证明：个整数，证明：其中必存在两个整数，要么两者的和能其中必存在两个整数，要么两者的和能被被100整除，要么两者的差能被整除，要么两者的差能被100整除。整除。9思路：思路：把把5252个物体放到个物体放到5151个盒子中，需要构造个盒子中，需要构造5151个盒子，个盒子，根据题目要求的两个整数必须具备的性质构造盒子；根据题目要求的两个整数必须具备的性质构造盒子；是否能够被是否能够被100100整除的关键在余数，那么一个整数除整除的关键

6、在余数，那么一个整数除以以100100的余数为的余数为0 0，1 1，2 2，9999 两个整数的和可以被两个整数的和可以被100100整除，则二者的整除，则二者的余数的和是余数的和是100100 两个整数的差可以被两个整数的差可以被100100整除，则二者的整除，则二者的余数相同余数相同证明：证明：对于任意一个整数，它除以对于任意一个整数，它除以100100的余数显然只的余数显然只能有如下能有如下100100种情况，种情况，0 0，1 1，2 2，3 3，9999 而现在有任意给定的而现在有任意给定的5252个整数，我们需要构造个整数，我们需要构造5151个个盒子，即对这盒子，即对这1001

7、00个余数进行分组，共个余数进行分组，共5151组：组：0,10,1，99,299,2，98,398,3，97,97,，4949，5151，505010根据根据定理定理2.1.12.1.1，这，这5252个整数，必有两个整数除以个整数，必有两个整数除以100100的余数落入上面的余数落入上面5151组中的同一组中，组中的同一组中，若是若是00或或5050则说明它们的和及差都能被则说明它们的和及差都能被100100整除；整除；若是剩下的若是剩下的4949组的话，因为一组有两个余数，余数相组的话，因为一组有两个余数，余数相同则它们的差能被同则它们的差能被100100整除，余数不同则它们的和能整除，

8、余数不同则它们的和能被被100100整除。整除。1112 例例2.1.4 一名象棋大师有一名象棋大师有11周时间准备一场锦标赛，她周时间准备一场锦标赛，她决定每天至少下一盘棋，为了不能太累，一周中下棋决定每天至少下一盘棋，为了不能太累，一周中下棋的次数不能多于的次数不能多于12盘。盘。证明：她一定在此期间的连续若干天中恰好下棋证明：她一定在此期间的连续若干天中恰好下棋21盘盘。13证明:令令b1，b2，b77分别为这分别为这11周中他每天周中他每天下棋的次数，并作部分和下棋的次数，并作部分和a1=b1,a2=b1+b2,，a77=b1+b2+b77.14所以有所以有1a1a2a3a771211

9、=132(2.1.1)考虑数列考虑数列a1,a2,，a77，a1+21,a2+21,，a77+21,它们都在它们都在1与与132+21=153之间，共有之间，共有154项，项，由定理由定理2.1.1知，其中必有两项相等知，其中必有两项相等根据题意，有bi1(1i77),且bi+bi+1+bi+612(1i71),15由（由（2.1.12.1.1）式知）式知a a1 1,a a2 2,，a a7777这这7777项互不相等，从而项互不相等，从而a a1 1+21,+21,a a2 2+21,+21,，a a7777+21+21这这7777项也互不相等，所以项也互不相等，所以一定存在一定存在11i

10、 i aj，则，则ai与从与从aj开始的最长递减子序开始的最长递减子序列合并，组成的子序列的长度列合并，组成的子序列的长度Li Lj+1 Lj；这；这与与Li=Lj矛盾；矛盾；23（2）若）若ai Mj，这又与这又与Mi=Mj矛盾。矛盾。所以假设所以假设1Lin 且且 1Min不成立。原结论成立。不成立。原结论成立。n2+1个人肩并肩地站成一排，则总能选除n+1个人，让他们向前迈出一步，所形成新一排的身高是递增或递减的。24定理定理2.2.1 (2.2.1 (鸽巢原理的加强形式鸽巢原理的加强形式)。个物体个盒子里至少含有第或者.,，个物体个盒子里至少含有二第或者，个物体第一个盒子里至少含有或者

11、则，个盒子里放入个物体1.若把都是正整数，,.,设212121nnnqnqqnnqqqqqq25证明：证明：(反证法反证法)对于对于i i1 1，2 2，n n，假设第，假设第i i个盒子个盒子里至多含有里至多含有q qi i-1-1个个物体，物体，则则n n个盒子里个盒子里物物体数体数的总和不超过的总和不超过 q q1 1+q+q2 2+q qn n -n n这与已知条件中的这与已知条件中的物体总数物体总数为为(q(q1 1+q+q2 2+q qn n n+1)n+1)相矛盾。相矛盾。故假设不对，故假设不对，原结论成立原结论成立。26 与简单形式的关系与简单形式的关系 上节的鸽巢原理的简单形

12、式是这一原理的上节的鸽巢原理的简单形式是这一原理的特殊情况，即特殊情况，即，有，有 q1+q2+qnn+1=n+127推论推论2.2.1若若 n(r-1)+1个个物体物体放放入入n个盒个盒子子。则则至少有一个至少有一个盒子里含有盒子里含有r个或者更个或者更多的多的物体。物体。证明证明 在定理在定理2.2.1中取中取q1=q2=qn=r即可。即可。28 推论推论2.2.2 若若设有设有n个正整数个正整数m1,m2,mn满足下面的不等式满足下面的不等式 (m1+mn)/n r1,则则 m1,mn中至少有一个数中至少有一个数 r证明证明 由上面的不等式得 m1+mn n(r1)+1，由推论2.2.1

13、，存在mi，使得mir。29推论推论2.2.3 设m和n都是正整数且mn，若将m个物体放入n个盒子中，则至少有一个盒子中含有大于等于 个物体。nm表示取天棚运算是大于等于 的最小正整数 nmnm证明：证明：根据 的定义有：nmnmnmnm130反证法。反证法。假定每个盒子里的物体都小于假定每个盒子里的物体都小于 个。个。，则至多是，则至多是 个，那么个，那么n个盒子里的物体总数个盒子里的物体总数n()n =m，与，与m个物体矛盾。个物体矛盾。因此原结论成立。因此原结论成立。nm1nm1nmnm31解解 根据定推论根据定推论2.2.1，若将，若将3(10-1)+1=28个物体个物体放入放入3个盒

14、子中，则至少有一个盒子中有个盒子中，则至少有一个盒子中有10个物个物体。显然物体就是三种水果，而盒子就是三类水体。显然物体就是三种水果，而盒子就是三类水果，结论是保证已经取出果，结论是保证已经取出10个相同种类的水果等个相同种类的水果等价于或者取出价于或者取出10个苹果或者取出个苹果或者取出10个橘子或者取个橘子或者取出出10个香蕉。因此答案是至少取个香蕉。因此答案是至少取28个水果才能保个水果才能保证已经取出证已经取出10个相同种类的水果。个相同种类的水果。32证明：证明：根据推论2.2.3，所以至少有一辆6座以上的汽车。610560033例例2.2.3 设有大小两只圆盘，每个都划分成大小设

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

16、12.2.1所示，使大小两盘中心重合，固定大盘，转所示，使大小两盘中心重合，固定大盘，转动小盘，则有动小盘，则有200200个不同位置使小盘上的每个小扇形个不同位置使小盘上的每个小扇形含在大盘上的小扇形中，由于大盘上的含在大盘上的小扇形中，由于大盘上的200200个小扇形个小扇形中有中有100100个涂成黑色，个涂成黑色，100100个涂成白色，所以小盘上个涂成白色，所以小盘上的每个小扇形无论涂成黑色或白色，在的每个小扇形无论涂成黑色或白色，在200200个可能的个可能的重合位置上恰好有重合位置上恰好有100100次与大盘上的小扇形同色，因次与大盘上的小扇形同色，因而小盘上的而小盘上的2002

17、00个小扇形在个小扇形在200200个重合位置上共同色个重合位置上共同色100100200=20000200=20000次，平均每个位置同色次，平均每个位置同色2000020000200=100200=100次。由推论次。由推论2.2.32.2.3知，存在着某个知，存在着某个位置，使同色的小扇形数大于等于位置，使同色的小扇形数大于等于100100个。个。36例例2.2.4 证明证明：任意n2+1 个实数组成的序列中，必有一个长度为n+1的递增子序列，或必有一个长度为n+1的递减子序列。1212,.,naaa37例例2.2.4 用鸽巢原理的加强形式证明用鸽巢原理的加强形式证明证明：证明：假设长为

18、假设长为n2+1的实数序列中没有长度为的实数序列中没有长度为n+1的递增子序列，下面证明其必有一长度为的递增子序列，下面证明其必有一长度为n+1的递减子序列。的递减子序列。令令mk表示从表示从ak开始的最长递增子序列的长开始的最长递增子序列的长度，因为实数序列中没有长度为度，因为实数序列中没有长度为n+1的递增子的递增子序列，所以有：序列，所以有：).1,2,1(12nknmk根据推论根据推论2.2.3，这相当于把，这相当于把n2+1个物体个物体 1212,nmmm38放入n个盒子1，2，n中，必有一个盒子i里面至少有 个物体，即存在n+1个mk取值相同，有使得1112nnnnn121nkkk

19、,1ni.121immmnkkk（2.2.1）对应于这些下标的实数序列必满足,121nkkkaaa（2.2.2）39它们构成一长为它们构成一长为n+1的递减序列。的递减序列。否则，若有某个否则，若有某个j（）使得）使得 ，那么由从那么由从 开始的最长递增子序列加上开始的最长递增子序列加上 ，就得到一个从就得到一个从 开始的长度为开始的长度为 的递增的递增子序列。由子序列。由 的定义知的定义知这与（这与（2.2.1）式矛盾。因此（）式矛盾。因此（2.2.2）式成立。）式成立。同理可证若没有长度为同理可证若没有长度为n+1的递减子序列，则的递减子序列，则必有一长度为必有一长度为n+1的递增子序列。

20、因此，结论的递增子序列。因此，结论成立。成立。nj11jjkkaa1jkajkajka11jkmjkm,11jjkkmm任何一个任何一个6 6人聚会，必有人聚会，必有3 3个人相互认个人相互认识或者相互不认识识或者相互不认识 40其其思想思想可以概括为可以概括为“在任何一个足够大的结构在任何一个足够大的结构中必定包含一个给定大小的规则子结构中必定包含一个给定大小的规则子结构”。41证明：证明：设K6的顶点为v1,v2,v6。对于K6的任何一种涂色方案，由推论2.2.3.，v1关联的边中必有 条同色边。不妨设这三条边为v1,v2,v1,v3,v1,v4 32542 若这三边为红色，当若这三边为红

21、色，当v2,v3,v4之间有一条红边之间有一条红边，比如说是，比如说是v2,v3,则则v1v2v3构成一个红三角形；构成一个红三角形；当当v2,v3,v4之间没有红边，则之间没有红边，则v2 v3 v4构成一个蓝构成一个蓝三角形。三角形。若这三边为蓝色时，同理可证。若这三边为蓝色时，同理可证。因此，结论成立。因此，结论成立。v2 v3 v4v1定理定理 2.3.1 设p，q是正整数，p，q2，则存在最小的正整数R(p,q)，使得当nR(p,q)时，用红、蓝两色涂色Kn的边，或者存在一个蓝色的完全p边形Kp，或者存在一个红色的完全q边形Kq。43证明：证明：采用数学归纳法。设p为任意正整数，q=

22、2。用红、蓝两色涂色Kp的边，若没有一条红边，则存在一个蓝色的完全p边形；若有一条红边，则构成一个完全红2边形，因此R(p,2)p。同理可证R(2,q)q。44假设对一切正整数p,q(p+q5。因此R(3,3)=6。4647证明：证明：令nR(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)(22 February 1903 19 January

23、1930)was a British mathematician who,in addition to mathematics,made significant and precocious contributions in philosophy and economics before his death at the age of 26.He was a close friend of Ludwig Wittgenstein,and was instrumental in translating Wittgensteins Tractatus Logico-Philosophicus in

24、to English,and in persuading Wittgenstein to return to philosophy and Cambridge.48生于剑桥，其父亲是麦格达伦学院的校长，其弟弟迈克尔拉姆齐是第100任坎特伯里大主教。拉姆齐于温切斯特公学学习，后来进入剑桥大学三一学院学习数学。他涉猎了很多领域。在政治上，他有左翼的倾向；宗教上，其妻指他是个态度坚定的无神论者。他和查尔斯凯奥格顿聊天时，说他想学德语。奥格顿便给他一本文法书、字典和一篇深奥的心理学论文并告诉他：使用那本文法书和字典，告诉我们你的想法。约一星期后，他不止学会了德语，还对语法书中一些理论提出了反对意见。他

25、阅读了维根斯坦的Tractatus Logico-Philosophicus。这本书深深影响了他，1923年他去奥地利跟维根斯坦讨论。1924年21岁的他成为国王学院的研究员。拉姆齐为治疗慢性肝疾而接受腹部手术，但术后并发黄疸，于1930年1月19日病逝于伦敦盖氏医院（Guys Hospital），得年仅26岁又11个月。4950保罗保罗 埃尔德什埃尔德什（Erds PlErds Pl，在英语中作Paul ErdsPaul Erds）（1913年3月26日1996年9月20日），其音读作air-dish，匈牙利语中的意思是来自山林。匈牙利籍犹太人，发表论文高达1475篇（包括与人合写的），为现

26、时发表论文数最多产的数学家（其次是欧拉）；曾和511人合写论文。爱多士遗传了来自数学教师父母优异的数学天赋，三岁时就能轻松心算一个人一生所活的秒数，并每日在客人面前表演四位数的乘法心算。他年仅二十一岁即被厄特沃什罗兰大学(即布达佩斯大学)授予数学博士学位，师从数学家Lipt Fejr(他也是冯纽曼的导师)。之后爱多士为了逃离纳粹的追捕，历任曼彻斯特大学教授与普林斯顿大学之研究人员。爱多士热爱自由，十分讨厌权威，尤其是法西斯。他四处游历，探访当地的数学家，与他们一起工作，合写论文。他很重视数学家的培训，遇到有天份的孩子，会鼓励他们继续研究。爱多士经常沉思于数学问题，视数学为生命，在母亲死后，他开

27、始经常服食精神药物。他经常长时间工作，老年仍每日工作19小时，酷爱饮咖啡，曾说“数学家是将咖啡转换成定理的机器”。因为爱多士和别人合写的论文实在太多了，所以有人定义了埃尔德什数，简称埃数。爱多士的爱多士数为0，与他直接合作写论文的人的埃数为1，与埃数为1的人合写论文的人埃数为2，依此类推。爱多士十分独持。除了衣食住行这些生活基本要知道的事之外，他对很多问题都毫不关心，终生未婚，年轻时甚至被人误以为是同性恋者，但其实他无论对异性或是同性都没有什么兴趣。事实上，他是一个博学的人，对历史了如指掌，但长大后只专注数学，任何其他事情也不管。爱多士说话有自己的一套“密语”，用各种有趣的名词来代替神、美国、孩子和婚姻等，如上帝被叫SF（Supreme Fascist，最大的法西斯的简称），小孩子被叫作epsilon（希腊语字母，数学中用于表示小量），美国被叫作山姆（Sam），苏联被叫作乔（Joe）。5152