资源描述
第五章抽屉原理和瑞姆赛理论,5.1抽屉原理5.2应用5.3Ramsey问题5.4Ramsey数,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.3Ramsey问题,5.3Ramsey问题,对10个顶点的完全图K10任意进行红、蓝两边着色，都或者存在一个红色K4，或者存在一个蓝色K3。,对9个顶点的完全图K9任意进行红、蓝两边着色，都或者存在一个红色K4，或者存在一个蓝色K3。,对于任意给定的两个正整数a和b，如果存在最小的正整数r(a,b)使得当N=r(a,b)时，对KN任意进行红、蓝两边着色，都或者存在一个红色Ka，或者存在一个蓝色Kb。则r(a,b)称为Ramsey数。,5.3Ramsey问题,5.3Ramsey问题,5.3Ramsey问题,5.3Ramsey问题,对于任意给定的两个正整数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.3Ramsey问题,5.3Ramsey问题,应用一篮子水果装有苹果、香蕉和橘子。为了保证篮子里或者至少有8个苹果或者至少有6个香蕉或者至少有9个橘子，则放入篮子中的水果的最小件数是多少？,
展开阅读全文