组合数学(西安电子科技大学(第二版))第五章抽屉原理.ppt

第五 章抽屉原理和瑞姆赛理论,5,.1,抽屉原理,5,.2,应用,5.3 Ramsey,问题,5.4 Ramsey,数,5,.1,抽屉原理,5,.1,抽屉原理,5,.1,抽屉原理,5,.1,抽屉原理,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,2,应用,应用,一位国际象棋大师有,11,周的时间备战一场锦标赛，他决定每天至少下一盘棋，但为了不使自己过于疲劳他还决定每周下棋不能超过,12,盘。证明存在连续若干天，其间这位大师恰好下了,21,盘棋。,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,2,应用,5,.,3,Ramsey,问题,5,.,3,Ramsey,问题,对,10,个顶点的完全图,K,10,任意进行红、蓝两边着色，都或者存在一个红色,K,4,，或者存在一个蓝色,K,3,。,对,9,个顶点的完全图,K,9,任意进行红、蓝两边着色，都或者存在一个红色,K,4,，或者存在一个蓝色,K,3,。,对于任意给定的两个正整数,a,和,b,，如果存在最小的正整数,r,(,a,b,),使得当,N,=,r,(,a,b,),时，对,K,N,任意进行红、蓝两边着色，都或者存在一个红色,K,a,，或者存在一个蓝色,K,b,。则,r,(,a,b,),称为,Ramsey,数。,5,.,3,Ramsey,问题,5,.,3,Ramsey,问题,2,3,4,5,6,7,8,9,2,2,3,4,5,6,7,8,9,3,3,6,9,14,18,23,28,36,4,4,9,18,25,5,5,14,25,6,6,18,7,7,23,8,8,28,9,9,36,5,.,3,Ramsey,问题,5,.,3,Ramsey,问题,对于任意给定的两个正整数,a,和,b,，有：,（,1,）,r,(,a,b,)=,r,(,b,a,),（,2,）,r,(,a,2,)=,a,。,对于任意给定的两个正整数,a,=3,和,b,=3,，有,r,(,a,b,)=,r,(,a,-1,b,)+,r,(,a,b,-1),5,.,3,Ramsey,问题,5,.,3,Ramsey,问题,应用,一篮子水果装有苹果、香蕉和橘子。为了保证篮子里或,者至少有,8,个苹果或者至少有,6,个香蕉或者至少有,9,个橘子，则,放入篮子中的水果的最小件数是多少？,