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

《組合數(shù)學(西安電子科技大學(第二版第五章抽屜原理.ppt》由會員分享，可在線閱讀，更多相關《組合數(shù)學(西安電子科技大學(第二版第五章抽屜原理.ppt（33頁珍藏版）》請在裝配圖網上搜索。

第五章抽屜原理和瑞姆賽理論,5.1抽屜原理5.2應用5.3Ramsey問題5.4Ramsey數(shù),5.1抽屜原理,5.1抽屜原理,5.1抽屜原理,5.1抽屜原理,5.2應用,5.2應用,5.2應用,5.2應用,5.2應用,5.2應用,應用一位國際象棋大師有11周的時間備戰(zhàn)一場錦標賽，他決定每天至少下一盤棋，但為了不使自己過于疲勞他還決定每周下棋不能超過12盤。證明存在連續(xù)若干天，其間這位大師恰好下了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。,對于任意給定的兩個正整數(shù)a和b，如果存在最小的正整數(shù)r(a,b)使得當N>=r(a,b)時，對KN任意進行紅、藍兩邊著色，都或者存在一個紅色Ka，或者存在一個藍色Kb。則r(a,b)稱為Ramsey數(shù)。,5.3Ramsey問題,5.3Ramsey問題,5.3Ramsey問題,5.3Ramsey問題,對于任意給定的兩個正整數(shù)a和b，有：（1）r(a,b)=r(b,a)（2）r(a,2)=a。,對于任意給定的兩個正整數(shù)a>=3和b>=3，有r(a,b)<=r(a-1,b)+r(a,b-1),5.3Ramsey問題,5.3Ramsey問題,應用一籃子水果裝有蘋果、香蕉和橘子。為了保證籃子里或者至少有8個蘋果或者至少有6個香蕉或者至少有9個橘子，則放入籃子中的水果的最小件數(shù)是多少？,