組合數(shù)學(xué)(西安電子科技大學(xué)(第二版第五章抽屜原理.ppt

《組合數(shù)學(xué)(西安電子科技大學(xué)(第二版第五章抽屜原理.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《組合數(shù)學(xué)(西安電子科技大學(xué)(第二版第五章抽屜原理.ppt（33頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第五章抽屜原理和瑞姆賽理論,5.1抽屜原理5.2應(yīng)用5.3Ramsey問(wèn)題5.4Ramsey數(shù),5.1抽屜原理,5.1抽屜原理,5.1抽屜原理,5.1抽屜原理,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,應(yīng)用一位國(guó)際象棋大師有11周的時(shí)間備戰(zhàn)一場(chǎng)錦標(biāo)賽，他決定每天至少下一盤(pán)棋，但為了不使自己過(guò)于疲勞他還決定每周下棋不能超過(guò)12盤(pán)。證明存在連續(xù)若干天，其間這位大師恰好下了21盤(pán)棋。,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.2應(yīng)用,5.3Ramsey問(wèn)題,5.3Ramsey問(wèn)題,對(duì)10個(gè)頂點(diǎn)的完全圖K10任意進(jìn)行紅、藍(lán)兩邊著色，都或者存在一個(gè)紅色K4，或者存在一個(gè)藍(lán)色K3。,對(duì)9個(gè)頂點(diǎn)的完全圖K9任意進(jìn)行紅、藍(lán)兩邊著色，都或者存在一個(gè)紅色K4，或者存在一個(gè)藍(lán)色K3。,對(duì)于任意給定的兩個(gè)正整數(shù)a和b，如果存在最小的正整數(shù)r(a,b)使得當(dāng)N>=r(a,b)時(shí)，對(duì)KN任意進(jìn)行紅、藍(lán)兩邊著色，都或者存在一個(gè)紅色Ka，或者存在一個(gè)藍(lán)色Kb。則r(a,b)稱為Ramsey數(shù)。,5.3Ramsey問(wèn)題,5.3Ramsey問(wèn)題,5.3Ramsey問(wèn)題,5.3Ramsey問(wèn)題,對(duì)于任意給定的兩個(gè)正整數(shù)a和b，有：（1）r(a,b)=r(b,a)（2）r(a,2)=a。,對(duì)于任意給定的兩個(gè)正整數(shù)a>=3和b>=3，有r(a,b)<=r(a-1,b)+r(a,b-1),5.3Ramsey問(wèn)題,5.3Ramsey問(wèn)題,應(yīng)用一籃子水果裝有蘋(píng)果、香蕉和橘子。為了保證籃子里或者至少有8個(gè)蘋(píng)果或者至少有6個(gè)香蕉或者至少有9個(gè)橘子，則放入籃子中的水果的最小件數(shù)是多少？,