组合数学—第二章鸽巢原理和Ramsey定理(2)

,*,*,第二章 鸽巢原理和,Ramsey,定理,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,2024年11月28日,第二章 鸽巢原理和,Ramsey,定理,2.2,鸽巢原理的加强形式,定理,2.2.1 (,鸽巢原理的加强形式,),2024年11月28日,第二章 鸽巢原理和,Ramsey,定理,推论,2.2.1,若,n(,r,1)+1,个物品,放入,n,个盒子,。,则,至少有一个,盒子里含有,r,个或者更多的物品。,推论,2.2.2,若,设有,n,个正整数,m,1,m,2,m,n,满足下面的不等式,(m,1,+m,n,)/n,r,1,则,m,1,m,n,中至少有一个数,r,推论,2.2.3,设,m,和,n,都是正整数且,m,n,，若将,m,个物体放入,n,个盒子中，则至少有一个盒子中有大于等于,个物体,2024年11月28日,第二章 鸽巢原理和,Ramsey,定理,推论,2.2.2,若,设有,n,个正整数,m,1,m,2,m,n,满足下面的不等式,(m,1,+m,n,)/n,r,1,则,m,1,m,n,中至少有一个数,r,另外两个平均原理：,设有,n,个正整数,m,1,m,2,m,n,满足下面的不等式,(m,1,+m,n,)/n,r+1,则,m,1,m,n,中至少有一个数,n,，若将,m,个物体放入,n,个盒子中，则至少有一个盒子中有大于等于,个物体,2024年11月28日,第二章 鸽巢原理和,Ramsey,定理,例,2.2.3,设有大小两只圆盘，每个都划分成大小相等的,200,个小扇形，在大盘上任选,100,个小扇形涂成黑色，其余的,100,个小扇形涂成白色，而将小盘上的,200,个小扇形任意涂成黑色或白色。现将大小两只圆盘的中心重合，转动小盘使小盘上的每个小扇形含在大盘上小扇形之内。证明：有一个位置使小盘上至少有,100,个小扇形同大盘上相应的小扇形同色。,2024年11月28日,第二章 鸽巢原理和,Ramsey,定理,2024年11月28日,第二章 鸽巢原理和,Ramsey,定理,证明,如图,2.2.1,所示，使大小两盘中心重合，固定大盘，转动小盘，则有,200,个不同位置使小盘上的每个小扇形含在大盘上的小扇形中，由于大盘上的,200,个小扇形中有,100,个涂成黑色，,100,个涂成白色，所以小盘上的每个小扇形无论涂成黑色或白色，在,200,个可能的重合位置上恰好有,100,次与大盘上的小扇形同色，因而小盘上的,200,个小扇形在,200,个重合位置上共同色,100200=20000,次，平均每个位置同色,2000020=100,次。由推论,2.2.3,知，存在着某个位置，使同色的小扇形数大于等于,100,个。,2024年11月28日,第二章 鸽巢原理和,Ramsey,定理,例,2.2.4,用鸽巢原理的加强形式证明,证明：任意,n,2,+1,个实数,组成的序列中，必有一个长度为,n,+1,的递增子序列，或必有一个长度为,n,+1,的递减子序列。,2024年11月28日,第二章 鸽巢原理和,Ramsey,定理,证明：,假设长为,n,2,+1,的实数序列中没有长度为,n,+1,的递增子序列，下面证明其必有一长度为,n,+1,的递减子序列。,令,m,k,表示从,a,k,开始的最长递增子序列的长度，因为实数序列中没有长度为,n,+1,的递增子序列，所以有：,根据推论,2.2.3,，这相当于把,n,2,+1,个物体,放入,n,个盒子,1,，,2,，,，,n,中，必有一个盒子,i,里,面至少有 个物体，即存在,n,+1,个,m,k,取值相同，有,使得,（,2.2.1,）,对应于这些下标的实数序列必满足,（,2.2.2,）,它们构成一长为,n,+1,的递减序列。,否则，若有某个,j,（）使得 ，那么由从 开始的最长递增子序列加上 ，就得到一个从 开始的长度为 的递增子序列。由 的定义知,这与（,2.2.1,）式矛盾。因此（,2.2.2,）式成立。同理可证若没有长度为,n+1,的递减子序列，则必有一长度为,n+1,的递增子序列。因此，结论成立。,2.3,Ramsey,定理,任何一个,6,人聚会，必有,3,个人相互认识或者相互不认识,其,思想,可以概括为“在任何一个足够大的结构中必定包含一个给定大小的规则子结构”。,例,2.3.1,设,K,6,是,6,个顶点的完全图，用红、蓝两色涂色,K,6,的边，则存在一个红色三角形，或存在一个蓝色三角形。,证明：,设,K,6,的顶点为,v,1,v,2,v,3,v,4,v,5,v,6,.,对于任意一种涂色方案，根据鸽巢原理加强形式的推论,3,，与,v,1,关联的,5,条边至少有,条同色边,不妨设这三条边为,v,1,v,2,v,1,v,3,v,1,v,4,（,1,）,若这三条边均为红色,v,1,v,2,v,3,v,4,(a),当,v,2,v,3,v,4,之间有一条红边，如,v,2,v,3,(b),v,2,v,3,v,4,之间没有红边，,v,1,v,2,v,3,v,4,v,1,v,2,v,3,v,4,(a),(b),（,2,）,若这三条边均为蓝色，同理可证,.,2024年11月28日,第二章 鸽巢原理和,Ramsey,定理,例,2.3.2,用红、蓝两色涂色,K,9,的边，证明或者存在一个蓝色的三角形或红色的完全四边形。,Ramsey,定理简单形式,定理,2.3.1,设,p,，,q,是正整数，,p,，,q,2,，则存在最小的正整数,R,(,p,q,),，使得当,n,R,(,p,q,),时，用红、蓝两色涂色,K,n,的边，或者存在一个蓝色的完全,p,边形,K,p,，或者存在一个红色的完全,q,边形,K,q,。,称,R(p,q),为,Ramsey,数；,确定精确的,Ramsey,数的值是相当困难的工作。到目前为止，仅有极少数小,p,，,q,的,Ramsey,数被找到。,2024年11月28日,第二章 鸽巢原理和,Ramsey,定理,q,p,3,4,5,6,7,8,9,10,3,6,9,14,18,23,28,36,40,43,4,18,25,35,41,49,61,56,84,69,115,92,149,5,43,49,58,87,80,143,101,216,121,316,141,442,6,102 165,111 298,127,495,169,780,178,1171,7,205 540,216 1031,232 1713,2826,8,282 1870,317 3583,6090,9,565 6588,580,12677,10,798,23556,证明思路：归纳法,归纳假设,R,(,p,2),p,R,(2,q,),q,归纳步骤,R,(,p,-1,q,),，,R,(,q,-1,p,),存在,R,(,p,q,),R,(,p,-1,q,)+,R,(,q,-1,p,),假设对正整数,p,q,p,p,q,q,p,+,q,5,。因此,R,(3,3)=6,。,定理,2.3.2,设,p,q,是正整数，,p,，,q,2,，则,R,(,p,q,)=,R,(,q,p,),证明：,令,n,R,(,p,q,),。对于蓝、红两色涂色,K,n,的边的任何一种方案，将蓝边换红边，红边换蓝边，则或存在一个蓝色的完全,p,边形，或存在一个红色的完全,q,边形。而原来的涂色方案中必存在一个红色的完全,p,边形或一个蓝色的完全,q,边形，即,R,(,q,p,),R,(,p,q,),。同理可证,R,(,p,q,),R,(,q,p,),。因此，,R,(,p,q,)=,R,(,q,p,),R,(,p,q,),的图表示,R,(,p,q,),的集合表述,K,n,的顶点集,V,集合,S,K,n,的边集,E S,的,2,元子集的集合,T,用,2,色涂色,K,n,的边 将,T,划分成,E,1,E,2,存在蓝色完全,p,边形 存在,S,的,p,子集其所有,2,元子集,E,1,存在红色完全,q,边形 存在,S,的,q,子集其所有,2,元子集,E,2,集合表述具有更强的表达能力,.,定理推广（,1,）,将,2,元子集推广到,r,元子集,对于任意给定的正整数,p,q,r,(,p,q,r,),存在一个最小的正整数,R,(,p,q,;,r,),使得当集合,S,的元素数大于等于,R,(,p,q,;,r,),时，将,S,的,r,子集族任意划分成,E,1,E,2,，则或者,S,有,p,子集,A,，,A,的所有,r,元子集属于,E,1,或者存在,q,子集,B,，,B,的所有,r,元子集属于,E,2,.,定理推广（,2,）,将,T,划分成,E,1,E,2,E,k,设,r,k,1,q,i,r,i,=1,2,k,是给定正整数，则存在一个最小的正整数,R,(,q,1,q,2,q,k,;,r,),，使得当,n,R,(,q,1,q,2,q,k,;,r,),时,当,n,元集,S,的所有,r,元子集划分成,k,个子集族,T,1,T,2,T,k,，那么存在,S,的,q,1,元子集,A,1,其所有的,r,元子集属于,T,1,或者存在,S,的,q,2,元子集,A,2,，,A,2,的所有,r,元子集属于,T,2,或者存在,S,的,q,k,元子集,A,k,其所有的,r,元子集属于,T,k,.,Ramsey,定理断定,Ramsey,数的存在性,.,Ramsey,数的确定是一个很困难的问题,.,r,=1,是鸽巢原理，,R,(,q,1,q,2,q,k,;1)=,q,1,+,q,2,+,q,k,k,+1,r,=2,k,=2,是简单的,Ramsey,定理,.,结果：,9,个,Ramsey,数的精确值，部分上界、下界,作业,