组合数学第二章鸽巢原理VIP

三、Ramsey问题与Ramsey数,一、鸽巢原理的简单形式,二、鸽巢原理的加强形式,四、Ramsey数的推广,第二章鸽巢原理,2.1鸽巢原理的简单形式,定理2.1.1:,如果把n+1个物品放入n个盒子中，,那么至少,有一个盒子中有两个或更多的物品。,例1.,13个人中必有两人的属相相同。,例2.,在边长为1的正方形内任取5点，,则其中至少有两,点，它们之间的距离不超过,机动目录上页下页返回结束,例3：,从1到200的所有整数中任取101个，,则这101个整数,中至少有一对数，其中的一个一定能被另一个整除。,机动目录上页下页返回结束,例4.,给定m个整数,证明：必存在整数k,l,使得,例5.,一个棋手有11周时间准备锦标赛，,他决定每天至,少下一盘棋，,一周中下棋的次数不能多于12次，,证明：在此期间的连续一些天中他正好下棋21次。,例6：,（中国余数定理）,设m,n为两个互素的正整数，,a,b是满足,的整数。,证明：,存在正整数x,使得x除以m的余数为a，除以n的余数,为b，即存在p,q，使得,机动目录上页下页返回结束,2.2鸽巢原理的加强形式,定理2.2.1:,设,机动目录上页下页返回结束,都是正整数，,如果把,个物品放入n个盒子，,那么或者,第1个盒子中至少有q1个物品，,或者第2个盒子中至少,有q2个物品，,或者第n个盒子中至少有qn个物品.,推论2.2.1:,若将n(r-1)+1个物品放入n个盒子中，,则至少有一个盒子中有r个物品。,推论2.2.2:,设,机动目录上页下页返回结束,是n个整数，,而且,则,中至少有一个数不小于r。,推论2.2.3:,若将m个物品放入n个盒子中，,则至少有,一个盒子中有不少于,个物品。,例1：,设有大小两只圆盘，,每个都划分成大小相等的200,的小扇形，,机动目录上页下页返回结束,在大盘上任选100个小扇形漆成黑色，,其余的100个小扇形漆成白色，,而将小盘上的200个,小扇形任意漆成黑色或白色，,现将大小两只圆盘的,中心重合，,转动小盘使小盘上的每个小扇形含在大盘,上的小扇形之内。,证明：有一个位置使小盘上至少有,100个小扇形同大盘上相应的小扇形同色。,例2.,任意,个实数,组成的序列中，,必有一个长为n+1的递增子序列，,或必有一个长为,n+1的递降子序列。,机动目录上页下页返回结束,例3.,将1到16这16个正整数任意分成三部分，,其中必,有一部分中的一个元素是该部分某两个元素之差,（三个元素不一定互不相同）。,2.3Ramsey问题与Ramsey数,命题2.3.1:,对6个顶点的完全图K6任意进行红、蓝两色,边着色，,都存在一个红色三角形或一个蓝色三角形。,机动目录上页下页返回结束,命题2.3.2:,对6个顶点的完全图K6任意进行红、蓝两色,边着色，,都至少存在两个同色三角形。,2.3Ramsey问题与Ramsey数,机动目录上页下页返回结束,命题2.3.3:,对10个顶点的完全图K10任意进行红、蓝两色,边着色，,都或者有一个红色K4，或者有一个蓝色K3。,命题2.3.4:,对9个顶点的完全图K9任意进行红、蓝两色,边着色，,都或者有一个红色K4，或者有一个蓝色K3。,定义:,对于任意给定的两个正整数a和b，,如果存在最小,正整数r(a,b)，使得当,对KN任意进行红、,蓝两色边着色，,KN中均有红色Ka或蓝色Kb，,则称,为Ramsey数。,性质：,机动目录上页下页返回结束,定理2.3.1:,对任意的正整数,机动目录上页下页返回结束,有,若,都是偶数，,定理2.3.2:,上面不等式严格成立。,对任意的正整数,有,2.4Ramsey数的推广,机动目录上页下页返回结束,定义:,对于任意给定的正整数,n色边着色，,KN中或出现c1红色,如果存在最小,正整数,使得当,或出现c2红色,，或出现cn红色,则称,为广义Ramsey数。,2.4Ramsey数的推广,定理2.4.1:,机动目录上页下页返回结束,对任意的正整数,有,定理2.4.2:,对任意的正整数,有,定理2.4.3:,机动目录上页下页返回结束,设,是集合,且,的任一,划分，即,则存在某一个i,Si中有三个数x,y,z(不一定不同),满足,方程,其中,定理2.4.4:(Ramsey定理),机动目录上页下页返回结束,设,是正整数，且,使得当,则必存在最小的正整数,时，,设S是一集合且|S|=m，,将S的,所有t元子集任意分放到n个盒子里，,那么要么有S中的,q1个元素