计算机2009组合数学—第二章鸽巢原理和Ramsey定理 (2).ppt

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

2、,2020年7月27日,第二章 鸽巢原理和Ramsey定理,2.1 鸽巢原理的最简单形式,鸽巢原理是组合学中最简单、最基本原理 也叫抽屉原理 (又称为或重叠原理或狄利克雷原理）。,定理2.1.1 若把n+1个物体放入n个盒子中， 则至少有一个盒子中有2个或更多的物体,2020年7月27日,第二章 鸽巢原理和Ramsey定理,证明 如果每个盒子中至多有一个物体，那么n个盒子中至多有n个物体，而我们共有n+1个物体，矛盾。 故定理成立。,鸽巢原理的集合描述形式： 设有限集合A有n+1个元素，将A分划成n个不相交子集的并，则至少有一个子集含有两个或两个以上的元素。 定理是用群体的整体性表现出个体的某

3、些特性，属于从宏观到微观的理论研究成果 注意 应用时要分清物品与盒子以及物体数与盒子总数。 这个原理只能用来证明某种安排的存在性，而却不能找到具体满足要求的安排 不能被推广到只存在n个(或更少)物体的情形。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,例2.1.1 共有12个属相，今有13个人，则必有两人的属相相同,几个例子,例2.1.2 有5双不同的袜子混在一个抽屉里，我们至少从中选出多少只袜子才能保证找到1双袜子？,2020年7月27日,第二章 鸽巢原理和Ramsey定理,解 应用定理2.1.1，共有5个盒子，每个盒子对应1双袜子。 如果选择5+1=6只袜子分别放到它所属那双

4、袜子的盒子中，则必有两只袜子落入同一个盒子中，即为一双袜子。因此我们至少从中选出6只袜子才能保证找到1双袜子。,本例实际上是知道n个盒子，而找n+1个物体的问题。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,例2.1.3对任意给定的52个整数，证明：其中必存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,1、已知：52个整数， 2、目标：找被100整数的两个数 3、解题途径：把52个物体放到51个盒子中，需要构造51个盒子 4、根据题干中要求的两个整数必须具备的性质构造盒子 5、是否能够被100整除的

5、关键在余数，那么一个整数除以100的余数为0，1，2，99 两个整数的和可以被100整除，则二者的余数的和是100 两个整数的差可以被100整除，则二者的余数相同,分析：,证明：对于任意一个整数，它除以100的余数显然只能有如下100种情况， 0，1，2，3，99 而现在有任意给定的52个整数，我们需要构造51个盒子，即对这100个余数进行分组，共51组： 0，1，99，2，98，3，97，49，51，50,根据定理2.1.1，这52个整数，必有两个整数除以100的余数落入上面51组中的同一组中， 若是0或50则说明它们的和及差都能被100整除； 若是剩下的49组的话，因为一组有两个余数，余数

6、相同则它们的差能被100整除，余数不同则它们的和能被100整除。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,例2.1.4 一名象棋大师有11周时间准备一场锦标赛，她决定每天至少下一盘棋，为了不能太累一周中下棋的次数不能多于12盘。证明：她一定在此期间的连续若干天中恰好下棋21盘。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,1、题干提供的信息：一共11周2、约束条件： 每周最多下12盘棋 每天至少下1盘棋 3、目标：连续若干天共下棋21盘 4、解题途径：构造下棋盘数的部分,分析：,2020年7月27日,第二章 鸽巢原理和Ramsey定理,证明:令b1，b2，b77

7、分别为这11周中他每天下棋的次数，并作部分和 a1=b1, a2=b1+b2, ， a77=b1+b2+b77.,2020年7月27日,第二章 鸽巢原理和Ramsey定理,所以有 1a1a2a3a771211=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),2020年7月27日,第二章 鸽巢原理和Ramsey定理,由（2.1.1）式知a1,a2,，a77这77项互不相等，从而a1+

8、21,a2+21,，a77+21这77项也互不相等，所以一定存在1ij77，使得 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盘棋。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,例2.1.5 将一个矩形分成4行19列的网格，每个单元格涂1种颜色，有3种颜色可以选择，证明：无论怎样涂色，其中必有一个由单元格构成的矩形的4个角上的格子被涂上同一种颜色。,1、题干提供的信息是给方格着色 2、目标：找一个由单元格构成的矩形的4个角上的格

9、子被涂上同一种颜色。需要翻译 3、两列中方格的涂色方案相同，即构造18个盒子放19列涂色方案 4、解题途径： 看每列情况，4个单元格涂3中颜色，必有两个涂同色，且同色的方案数为（4，2）=6种， 每种颜色6种，共3种颜色，18=6*3,分析：,2020年7月27日,第二章 鸽巢原理和Ramsey定理,证明：首先对每一列而言，因为有4行，但只有3种颜色选择。根据定理2.1.1，则必有两个单元格的颜色相同。另外，每列中两个单元格的不同位置组合有=6种，这样一列中两个同色单元格的位置组合共有18种情况，,而现在共有19列，根据定理2.1.1，无论怎样涂色，则必有两列与图中的某一列相同，即各自所包含的

10、两个同色单元格的位置相同、颜色相同。即结论成立。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,例2.1.6 证明：任意n2+1 个实数 组成的序列中，必有一个长度为n+1的递增子序列，或必有一个长度为n+1的递减子序列。,1、子序列概念如果 是一个序列，那么， 是一个子序列，其中， 2、递增子序列概念 若满足 3、递减子序列概念 若满足 4、分析题干：递增或递减子序列的长度n+1,分析：,2020年7月27日,第二章 鸽巢原理和Ramsey定理,证明：由题意，设Li是从ai开始的递减子序列的最大长度，Mi是从ai开始的递增子序列的最大长度，则对于i从1到n2 + 1的每个i的取值

11、，都有（Li, Mi）与之对应。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,（1）若ai aj，则ai与从aj开始的最长递减子序列合并，组成的子序列的长度Li Lj+1 Lj；这与Li = Lj矛盾；,反证法。假设既不存在长度为n+1的递增子序列，也不存在长度为n+1的递减子序列即1Lin 且 1Min，其中1in2 + 1，由集合论的知识知道集合(Li, Mi)的元素数为n2，根据定理2.1.1，必然有（Li, Mi） = (Lj, Mj)（i j），当然Li = Lj，而且Mi = Mj。对于序列中的元素ai, aj，分两种情况：,2020年7月27日,第二章 鸽巢原理和R

12、amsey定理,（2）若ai Mj，这又与Mi = Mj矛盾。 所以假设1Lin 且 1Min不成立。原结论成立。,这个例子的结论是1935年由数学家保罗艾狄胥（Erds）和乔治塞克尔斯（Szekeres）首先给出的，它还有更为有趣的表述：n2+1个人肩并肩地站成一排，则总能选除n+1个人，让他们向前迈出一步，所形成新一排的身高是递增或递减的。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,2.2 鸽巢原理的加强形式,定理2.2.1 (鸽巢原理的加强形式),2020年7月27日,第二章 鸽巢原理和Ramsey定理,定理2.2.1的证明 (反证法) 对于i1，2，n，假设第i个盒子里

13、至多含有qi-1个物品，则n个盒子里物品数的总和不超过 q1+q2+qn - n 这与已知条件中的 物品总数为(q1+q2+qn n+1)相矛盾。 故假设不真，原结论成立。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,与简单形式的关系 上节的鸽巢原理的简单形式是这一原理的特殊情况，即q1 = q2 = = qn= 2，有 q1 + q2 + +qnn + 1 = n + 1,2020年7月27日,第二章 鸽巢原理和Ramsey定理,定理2.2.1的推论,推论2.2.1若 n(r1) + 1个物品放入n个盒子。则至少有一个盒子里含有r个或者更多的物品。,证明 在定理2.2.1中取q

14、1=q2=qn=r即可。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,推论2.2.2 若设有n个正整数m1 , m2 , , mn满足下面的不等式 (m1 + +mn)/n r1, 则 m1, mn中至少有一个数 r,证明 由上面的不等式得 m1 + +mn (r1)n+1， 由推论2.2.1， 存在mi，使得mir。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,推论2.2.3 设m和n都是正整数且mn，若将m个物体放入n个盒子中，则至少有一个盒子中有大于等于 个物体,表示取天棚运算是大于等于 的最小正整数,证明：根据 的定义有：,反证法。假定每个盒子里的物体都小于

15、 个。 ，则至多是 个，那么n个盒子里的物体总数 n ( )n =m，与m个物体矛盾。 因此原结论成立。,例2.2.1 一个袋子里装了10个苹果，11个橘子，12个香蕉，至少取出多少个水果才能保证已经取出10个相同种类的水果,解 根据定推论2.2.1，若将3(10-1)+1=28个物体放入3个盒子中，则至少有一个盒子中有10个物体。显然物体就是三种水果，而盒子就是三类水果，结论是保证已经取出10个相同种类的水果等价于或者取出10个苹果或者取出10个橘子或者取出10个香蕉。因此答案是至少取28个水果才能保证已经取出10个相同种类的水果。,例2.2.2 一家汽车租赁公司共有105辆汽车，共有座位6

16、00个，证明至少有一辆6座以上的汽车？,证明：根据推论2.2.3， 所以至少有一辆6座以上的汽车。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,例2.2.3 设有大小两只圆盘，每个都划分成大小相等的200个小扇形，在大盘上任选100个小扇形涂成黑色，其余的100个小扇形涂成白色，而将小盘上的200个小扇形任意涂成黑色或白色。现将大小两只圆盘的中心重合，转动小盘使小盘上的每个小扇形含在大盘上小扇形之内。证明：有一个位置使小盘上至少有100个小扇形同大盘上相应的小扇形同色。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,2020年7月27日,第二章 鸽巢原理和Ramsey

17、定理,证明 如图2.2.1所示，使大小两盘中心重合，固定大盘，转动小盘，则有200个不同位 置使小盘上的每个小扇形含在大盘上的小扇形中，由于大盘上的200个小扇形中有100个涂成黑色，100个涂成白色，所以小盘上的每个小扇形无论涂成黑色或白色，在200个可能的重合位置上恰好有100次与大盘上的小扇形同色，因而小盘上的200个小扇形在200个重合位置上共同色100200=20000次，平均每个位置同色2000020=100次。由推论2.2.3知，存在着某个位置，使同色的小扇形数大于等于100个。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,例2.2.4 用鸽巢原理的加强形式证明,证

18、明：任意n2+1 个实数 组成的序列中，必有一个长度为n+1的递增子序列，或必有一个长度为n+1的递减子序列。,2020年7月27日,第二章 鸽巢原理和Ramsey定理,例2.2.4 用鸽巢原理的加强形式证明,证明：假设长为n2+1的实数序列中没有长度为n+1的递增子序列，下面证明其必有一长度为n+1的递减子序列。 令mk表示从ak开始的最长递增子序列的长度，因为实数序列中没有长度为n+1的递增子序列，所以有：,根据推论2.2.3，这相当于把n2+1个物体,放入n个盒子1，2，n中，必有一个盒子i里 面至少有 个物体，即存在n+1 个mk取值相同，有 使得,（2.2.1）,对应于这些下标的实数

19、序列必满足,（2.2.2）,它们构成一长为n+1的递减序列。 否则，若有某个j（ ）使得 ，那么由从 开始的最长递增子序列加上 ，就得到一个从 开始的长度为 的递增子序列。由 的定义知 这与（2.2.1）式矛盾。因此（2.2.2）式成立。同理可证若没有长度为n+1的递减子序列，则必有一长度为n+1的递增子序列。因此，结论成立。,2.3 Ramsey定理,任何一个6人聚会，必有3个人相互认识或者相互不认识,其思想可以概括为“在任何一个足够大的结构中必定包含一个给定大小的规则子结构”。,例2.3.1 设K6是6个顶点的完全图，用红、蓝两色涂色K6的边，则存在一个红色三角形，或存在一个蓝色三角形。,

20、证明：设K6的顶点为v1,v2,v6。对于K6的任何一 种涂色方案，由推论2.2.3.，v1关联的边中必有 条同色边。不妨设这三条边为v1 ,v2,v1 ,v3,v1 ,v4,若这三边为红色，当v2 ,v3 ,v4之间有一条红边，比如说是v2 ,v3,则v1v2v3构成一个红三角形；当v2 ,v3 ,v4之间没有红边，则v2 v3 v4构成一个蓝三角形。 若这三边为蓝色时，同理可证。 因此，结论成立。,定理 2.3.1 设p，q是正整数，p，q2，则存在最小的正整数R(p,q)，使得当nR(p,q)时，用红、蓝两色涂色Kn的边，或者存在一个蓝色的完全p边形Kp，或者存在一个红色的完全q边形Kq。,证明：采用数学归纳法。 设p为任意正整数，q=2。用红、蓝两色涂色Kp的边，若没有一条红边，则存在一个蓝色的完全p边形；若有一条红边，则构成一个完全红2边形，因此R(p,2)p。同理可证R(2,q) q。,假设对一切正整数p,q