組合數(shù)學(xué)(張永剛)吉林大學(xué)-第二章-鴿巢原理和ramsey定理課件

1第二章鴿巢原理和Ramsey定理組合存在性定理Ramsey定理（鴿巢原理為其最簡(jiǎn)形式）偏序集分解定理（Dilworth定理）相異代表系存在定理（Hall定理）1928年英國(guó)數(shù)學(xué)家、哲學(xué)家兼經(jīng)濟(jì)學(xué)家Frank，Ramsey(1903-1930)在倫敦?cái)?shù)學(xué)會(huì)上宣讀一篇“論形式邏輯中的一個(gè)問(wèn)題”的論文，奠定Ramsey理論的基礎(chǔ)。核心思想是：“任何一個(gè)足夠大的結(jié)構(gòu)中必定包含一個(gè)給定大小的規(guī)則子結(jié)構(gòu)”1第二章鴿巢原理和Ramsey定理組合存在性定理2第二章鴿巢原理和Ramsey定理

§2.1鴿巢原理的最簡(jiǎn)單形式§2.2鴿巢原理的加強(qiáng)形式§2.3Ramsey定理2第二章鴿巢原理和Ramsey定理

3§2.1鴿巢原理的最簡(jiǎn)單形式鴿巢原理(Pigeonholeprinciple)是組合學(xué)中最簡(jiǎn)單、最基本原理.也叫抽屜原理、重疊原理、狄利克雷原理。定理2.1.1若把n+1個(gè)物體放入n個(gè)盒子中，則至少有一個(gè)盒子中有2個(gè)或更多的物體3§2.1鴿巢原理的最簡(jiǎn)單形式鴿巢原理(Pigeonhol4證明：（反證法）

若不然，假定每個(gè)盒子中至多有一個(gè)物體，那么n個(gè)盒子中至多有n個(gè)物體，而我們共有n+1個(gè)物體，矛盾。故定理成立。

4證明：（反證法）5鴿巢原理的集合描述形式：

設(shè)有限集合A有n+1個(gè)元素，將A分劃成n個(gè)不相交子集的并，則至少有一個(gè)子集含有兩個(gè)或兩個(gè)以上的元素。注意！應(yīng)用時(shí)要分清物品與盒子以及物體數(shù)與盒子總數(shù)。這個(gè)原理只能用來(lái)證明某種安排的存在性，而卻不能找到具體滿(mǎn)足要求的安排

不能被推廣到只存在n個(gè)(或更少)物體的情形。5鴿巢原理的集合描述形式：6例2.1.1

共有12個(gè)屬相，今有13個(gè)人，則必有兩人的屬相相同。

幾個(gè)例子例2.1.2

有5雙不同的襪子混在一個(gè)抽屜里，我們至少?gòu)闹羞x出多少只襪子才能保證找到1雙襪子？

6例2.1.1共有12個(gè)屬相，今有13個(gè)人，則必有兩人的屬7解

應(yīng)用定理2.1.1，共有5個(gè)盒子，每個(gè)盒子對(duì)應(yīng)1雙襪子。如果選擇5+1=6只襪子分別放到它所屬那雙襪子的盒子中，則必有兩只襪子落入同一個(gè)盒子中，即為一雙襪子。因此我們至少?gòu)闹羞x出6只襪子才能保證找到1雙襪子。本例實(shí)際上是知道n個(gè)盒子，而找n+1個(gè)物體的問(wèn)題。

7解應(yīng)用定理2.1.1，共有5個(gè)盒子，每個(gè)盒子對(duì)應(yīng)1雙8例2.1.3 對(duì)任意給定的52個(gè)整數(shù)，證明：其中必存在兩個(gè)整數(shù)，要么兩者的和能被100整除，要么兩者的差能被100整除。

8例2.1.3 對(duì)任意給定的52個(gè)整數(shù)，證明：其中必存在兩個(gè)9思路：把52個(gè)物體放到51個(gè)盒子中，需要構(gòu)造51個(gè)盒子，根據(jù)題目要求的兩個(gè)整數(shù)必須具備的性質(zhì)構(gòu)造盒子；是否能夠被100整除的關(guān)鍵在余數(shù)，那么一個(gè)整數(shù)除以100的余數(shù)為0，1，2，…，99兩個(gè)整數(shù)的和可以被100整除，則二者的余數(shù)的和是100兩個(gè)整數(shù)的差可以被100整除，則二者的余數(shù)相同分析：9思路：分析：證明：對(duì)于任意一個(gè)整數(shù)，它除以100的余數(shù)顯然只能有如下100種情況，0，1，2，3，……，99而現(xiàn)在有任意給定的52個(gè)整數(shù)，我們需要構(gòu)造51個(gè)盒子，即對(duì)這100個(gè)余數(shù)進(jìn)行分組，共51組：{0},{1，99},{2，98},{3，97},……，{49，51}，{50}10證明：對(duì)于任意一個(gè)整數(shù)，它除以100的余數(shù)顯然只能有如下10根據(jù)定理2.1.1，這52個(gè)整數(shù)，必有兩個(gè)整數(shù)除以100的余數(shù)落入上面51組中的同一組中，若是{0}或{50}則說(shuō)明它們的和及差都能被100整除；若是剩下的49組的話，因?yàn)橐唤M有兩個(gè)余數(shù)，余數(shù)相同則它們的差能被100整除，余數(shù)不同則它們的和能被100整除。11根據(jù)定理2.1.1，這52個(gè)整數(shù)，必有兩個(gè)整數(shù)除以100的余12

例2.1.4

一名象棋大師有11周時(shí)間準(zhǔn)備一場(chǎng)錦標(biāo)賽，她決定每天至少下一盤(pán)棋，為了不能太累，一周中下棋的次數(shù)不能多于12盤(pán)。證明：她一定在此期間的連續(xù)若干天中恰好下棋21盤(pán)。

12例2.1.4一名象棋大師有11周時(shí)間準(zhǔn)備一場(chǎng)錦標(biāo)13證明:令b1，b2，…，b77分別為這11周中他每天下棋的次數(shù)，并作部分和a1=b1,a2=b1+b2,…，a77=b1+b2+…+b77.13證明:令b1，b2，…，b77分別為這11周中他每天下棋14所以有1≤a1<a2<a3<…<a77≤12×11=132(2.1.1)考慮數(shù)列a1,a2,…，a77，a1+21,a2+21,…，a77+21,它們都在1與132+21=153之間，共有154項(xiàng)，由定理2.1.1知，其中必有兩項(xiàng)相等根據(jù)題意，有bi≥1(1≤i≤77),且bi+bi+1+…+bi+6≤12(1≤i≤71),14所以有根據(jù)題意，有bi≥1(1≤i≤77),且bi+bi15由（2.1.1）式知a1,a2,…，a77這77項(xiàng)互不相等，從而a1+21,a2+21,…，a77+21這77項(xiàng)也互不相等，所以一定存在1≤i<j≤77，使得aj=ai+21.因此21=aj-ai=(b1+b2+…+bi+bi+1+…+bj)-(b1+b2+…+bi)=bi+1+bi+2+…+bj.這說(shuō)明從第i+1天到第j天這連續(xù)j-i天中，她剛好下了21盤(pán)棋。15由（2.1.1）式知a1,a2,…，a77這77項(xiàng)互不相16例2.1.5

將一個(gè)矩形分成4行19列的網(wǎng)格，每個(gè)單元格涂1種顏色，有3種顏色可以選擇。證明：無(wú)論怎樣涂色，其中必有一個(gè)由單元格構(gòu)成的矩形的4個(gè)角上的格子被涂上同一種顏色。16例2.1.5將一個(gè)矩形分成4行19列的網(wǎng)格，每個(gè)單元17證明：首先對(duì)每一列而言，因?yàn)橛?行，但只有3種顏色選擇。根據(jù)定理2.1.1，則必有兩個(gè)單元格的顏色相同。另外，每列中兩個(gè)單元格的不同位置組合有=6種，這樣一列中兩個(gè)同色單元格的位置組合共有18種情況，

17證明：首先對(duì)每一列而言，因?yàn)橛?行，但只有3種顏色選擇。而現(xiàn)在共有19列，根據(jù)定理2.1.1，無(wú)論怎樣涂色，則必有兩列與圖中的某一列相同，即各自所包含的兩個(gè)同色單元格的位置相同、顏色相同。即結(jié)論成立。

18而現(xiàn)在共有19列，根據(jù)定理2.1.1，無(wú)論怎樣涂色，則必有兩19例2.1.6

證明：任意n2+1個(gè)實(shí)數(shù)組成的序列中，必有一個(gè)長(zhǎng)度為n+1的遞增子序列，或必有一個(gè)長(zhǎng)度為n+1的遞減子序列。

19例2.1.6證明：任意n2+1個(gè)實(shí)數(shù)1、子序列概念

如果是一個(gè)序列，那么，是一個(gè)子序列，其中，2、遞增子序列概念若滿(mǎn)足3、遞減子序列概念若滿(mǎn)足20分析：1、子序列概念

如果21證明：由題意，設(shè)Li是從ai開(kāi)始的遞減子序列的最大長(zhǎng)度，Mi是從ai開(kāi)始的遞增子序列的最大長(zhǎng)度，則對(duì)于i從1到n2

+1的每個(gè)i的取值，都有（Li,Mi）與之對(duì)應(yīng)。21證明：由題意，設(shè)Li是從ai開(kāi)始的遞減子序列的最大長(zhǎng)度，22（1）若ai>aj，則ai與從aj開(kāi)始的最長(zhǎng)遞減子序列合并，組成的子序列的長(zhǎng)度Li

≥Lj+1

>Lj；這與Li

=Lj矛盾；反證法。假設(shè)既不存在長(zhǎng)度為n+1的遞增子序列，也不存在長(zhǎng)度為n+1的遞減子序列即1≤Li≤n

且1≤Mi≤n，其中1≤i≤n2+1，由集合論的知識(shí)知：集合{(Li,Mi)}的元素?cái)?shù)最多為n2，根據(jù)定理2.1.1，必然有（Li,Mi）=(Lj,Mj)（i<j），當(dāng)然Li

=Lj，而且Mi

=Mj。對(duì)于序列中的元素ai,aj，分兩種情況：

22（1）若ai>aj，則ai與從aj開(kāi)始的最長(zhǎng)遞減子序23（2）若ai<aj，則ai與從aj開(kāi)始的最長(zhǎng)遞增子序列合并，組成的子序列的長(zhǎng)度Mi

≥Mj+1>Mj，這又與Mi=Mj矛盾。所以假設(shè)1≤Li≤n

且1≤Mi≤n不成立。原結(jié)論成立。這個(gè)例子的結(jié)論是1935年由數(shù)學(xué)家保羅·艾狄胥（Erd?s）和喬治·塞克爾斯（Szekeres）首先給出的，它還有更為有趣的表述：n2+1個(gè)人肩并肩地站成一排，則總能選除n+1個(gè)人，讓他們向前邁出一步，所形成新一排的身高是遞增或遞減的。23（2）若ai<aj，則ai與從aj開(kāi)始的最長(zhǎng)遞增子序24§2.2鴿巢原理的加強(qiáng)形式定理2.2.1(鴿巢原理的加強(qiáng)形式)24§2.2鴿巢原理的加強(qiáng)形式定理2.2.1(鴿巢原25證明：(反證法)

對(duì)于i＝1，2，…，n，假設(shè)第i個(gè)盒子里至多含有qi-1個(gè)物體，則n個(gè)盒子里物體數(shù)的總和不超過(guò)

q1+q2+…+qn-

n這與已知條件中的物體總數(shù)為(q1+q2+…+qn–

n+1)相矛盾。故假設(shè)不對(duì)，原結(jié)論成立。25證明：(反證法)26

與簡(jiǎn)單形式的關(guān)系

上節(jié)的鴿巢原理的簡(jiǎn)單形式是這一原理的特殊情況，即q1=q2=…=qn=2，有

q1+q2+…+qn－n+1=n+126與簡(jiǎn)單形式的關(guān)系27推論2.2.1

若n(r-1)+1個(gè)物體放入n個(gè)盒子。則至少有一個(gè)盒子里含有r個(gè)或者更多的物體。證明在定理2.2.1中取q1=q2=…=qn=r即可。27推論2.2.1若n(r-1)+1個(gè)物體放入n個(gè)盒28

推論2.2.2

若設(shè)有n個(gè)正整數(shù)m1,m2,…,mn滿(mǎn)足下面的不等式

(m1+…+mn)/n>

r－1,

則

m1,…,mn中至少有一個(gè)數(shù)≥

r證明

由上面的不等式得

m1+…+mn≥

n(r－1)+1，由推論2.2.1，存在mi，使得mi≥r。28推論2.2.2若設(shè)有n個(gè)正整數(shù)m1,m2,29推論2.2.3

設(shè)m和n都是正整數(shù)且m>n，若將m個(gè)物體放入n個(gè)盒子中，則至少有一個(gè)盒子中含有大于等于個(gè)物體。表示取天棚運(yùn)算是大于等于的最小正整數(shù)

證明：根據(jù)的定義有：

29推論2.2.3設(shè)m和n都是正整數(shù)且m>n，若將m個(gè)物體30反證法。假定每個(gè)盒子里的物體都小于個(gè)。，則至多是個(gè)，那么n個(gè)盒子里的物體總數(shù)≤n()<n×

=m，與m個(gè)物體矛盾。因此原結(jié)論成立。

30反證法。假定每個(gè)盒子里的物體都小于個(gè)。31例2.2.1一個(gè)袋子里裝了10個(gè)蘋(píng)果，11個(gè)橘子，12個(gè)香蕉，至少取出多少個(gè)水果才能保證已經(jīng)取出10個(gè)相同種類(lèi)的水果。解根據(jù)定推論2.2.1，若將3×(10-1)+1=28個(gè)物體放入3個(gè)盒子中，則至少有一個(gè)盒子中有10個(gè)物體。顯然物體就是三種水果，而盒子就是三類(lèi)水果，結(jié)論是保證已經(jīng)取出10個(gè)相同種類(lèi)的水果等價(jià)于或者取出10個(gè)蘋(píng)果或者取出10個(gè)橘子或者取出10個(gè)香蕉。因此答案是至少取28個(gè)水果才能保證已經(jīng)取出10個(gè)相同種類(lèi)的水果。

31例2.2.1一個(gè)袋子里裝了10個(gè)蘋(píng)果，11個(gè)橘子，1232例2.2.2

一家汽車(chē)租賃公司共有105輛汽車(chē)，共有座位600個(gè)，證明至少有一輛6座以上的汽車(chē)？

證明：根據(jù)推論2.2.3，所以至少有一輛6座以上的汽車(chē)。32例2.2.2一家汽車(chē)租賃公司共有105輛汽車(chē)，共有座位33例2.2.3

設(shè)有大小兩只圓盤(pán)，每個(gè)都劃分成大小相等的200個(gè)小扇形，在大盤(pán)上任選100個(gè)小扇形涂成黑色，其余的100個(gè)小扇形涂成白色，而將小盤(pán)上的200個(gè)小扇形任意涂成黑色或白色。現(xiàn)將大小兩只圓盤(pán)的中心重合，轉(zhuǎn)動(dòng)小盤(pán)使小盤(pán)上的每個(gè)小扇形含在大盤(pán)上小扇形之內(nèi)。證明：有一個(gè)位置使小盤(pán)上至少有100個(gè)小扇形同大盤(pán)上相應(yīng)的小扇形同色。33例2.2.3設(shè)有大小兩只圓盤(pán)，每個(gè)都劃分成大小相等343435證明

如圖2.2.1所示，使大小兩盤(pán)中心重合，固定大盤(pán)，轉(zhuǎn)動(dòng)小盤(pán)，則有200個(gè)不同位置使小盤(pán)上的每個(gè)小扇形含在大盤(pán)上的小扇形中，由于大盤(pán)上的200個(gè)小扇形中有100個(gè)涂成黑色，100個(gè)涂成白色，所以小盤(pán)上的每個(gè)小扇形無(wú)論涂成黑色或白色，在200個(gè)可能的重合位置上恰好有100次與大盤(pán)上的小扇形同色，因而小盤(pán)上的200個(gè)小扇形在200個(gè)重合位置上共同色100×200=20000次，平均每個(gè)位置同色20000÷200=100次。由推論2.2.3知，存在著某個(gè)位置，使同色的小扇形數(shù)大于等于100個(gè)。35證明36例2.2.4證明：任意n2+1個(gè)實(shí)數(shù)組成的序列中，必有一個(gè)長(zhǎng)度為n+1的遞增子序列，或必有一個(gè)長(zhǎng)度為n+1的遞減子序列。

36例2.2.4證明：任意n2+1個(gè)實(shí)數(shù)組成的序列中，37例2.2.4用鴿巢原理的加強(qiáng)形式證明證明：假設(shè)長(zhǎng)為n2+1的實(shí)數(shù)序列中沒(méi)有長(zhǎng)度為n+1的遞增子序列，下面證明其必有一長(zhǎng)度為n+1的遞減子序列。 令mk表示從ak開(kāi)始的最長(zhǎng)遞增子序列的長(zhǎng)度，因?yàn)閷?shí)數(shù)序列中沒(méi)有長(zhǎng)度為n+1的遞增子序列，所以有：

根據(jù)推論2.2.3，這相當(dāng)于把n2+1個(gè)物體

37例2.2.4用鴿巢原理的加強(qiáng)形式證明證明：假設(shè)長(zhǎng)為n238放入n個(gè)盒子1，2，…，n中，必有一個(gè)盒子i里面至少有個(gè)物體，即存在n+1個(gè)mk取值相同，有使得（2.2.1）

對(duì)應(yīng)于這些下標(biāo)的實(shí)數(shù)序列必滿(mǎn)足

（2.2.2）

38放入n個(gè)盒子1，2，…，n中，必有一個(gè)盒子i里（2.2.39它們構(gòu)成一長(zhǎng)為n+1的遞減序列。否則，若有某個(gè)j（）使得，那么由從開(kāi)始的最長(zhǎng)遞增子序列加上，就得到一個(gè)從開(kāi)始的長(zhǎng)度為的遞增子序列。由的定義知這與（2.2.1）式矛盾。因此（2.2.2）式成立。同理可證若沒(méi)有長(zhǎng)度為n+1的遞減子序列，則必有一長(zhǎng)度為n+1的遞增子序列。因此，結(jié)論成立。39它們構(gòu)成一長(zhǎng)為n+1的遞減序列。任何一個(gè)6人聚會(huì)，必有3個(gè)人相互認(rèn)識(shí)或者相互不認(rèn)識(shí)40§2.3Ramsey定理

其思想可以概括為“在任何一個(gè)足夠大的結(jié)構(gòu)中必定包含一個(gè)給定大小的規(guī)則子結(jié)構(gòu)”。

任何一個(gè)6人聚會(huì)，必有3個(gè)人相互認(rèn)識(shí)或者相互不認(rèn)識(shí)40§241例2.3.1

設(shè)K6是6個(gè)頂點(diǎn)的完全圖，用紅、藍(lán)兩色涂色K6的邊，則存在一個(gè)紅色三角形，或存在一個(gè)藍(lán)色三角形。證明：設(shè)K6的頂點(diǎn)為v1,v2,…,v6。對(duì)于K6的任何一種涂色方案，由推論2.2.3.，v1關(guān)聯(lián)的邊中必有條同色邊。不妨設(shè)這三條邊為{v1

,v2},{v1

,v3},{v1,v4}

41例2.3.1設(shè)K6是6個(gè)頂點(diǎn)的完全圖，用紅、藍(lán)兩色涂色42若這三邊為紅色，當(dāng)v2,v3,v4之間有一條紅邊，比如說(shuō)是{v2,v3},則v1v2v3構(gòu)成一個(gè)紅三角形；當(dāng)v2,v3

,v4之間沒(méi)有紅邊，則v2v3v4構(gòu)成一個(gè)藍(lán)三角形。若這三邊為藍(lán)色時(shí)，同理可證。因此，結(jié)論成立。

v2

v3

v4v142若這三邊為紅色，當(dāng)v2,v3,v4之間有一條紅邊，定理2.3.1

設(shè)p，q是正整數(shù)，p，q≥2，則存在最小的正整數(shù)R(p,q)，使得當(dāng)n≥R(p,q)時(shí)，用紅、藍(lán)兩色涂色Kn的邊，或者存在一個(gè)藍(lán)色的完全p邊形Kp，或者存在一個(gè)紅色的完全q邊形Kq。

43證明：采用數(shù)學(xué)歸納法。 設(shè)p為任意正整數(shù)，q=2。用紅、藍(lán)兩色涂色Kp的邊，若沒(méi)有一條紅邊，則存在一個(gè)藍(lán)色的完全p邊形；若有一條紅邊，則構(gòu)成一個(gè)完全紅2邊形，因此R(p,2)≤p。同理可證R(2,q)≤q。定理2.3.1設(shè)p，q是正整數(shù)，p，q≥2，則存在最小44假設(shè)對(duì)一切正整數(shù)p,q(p+q<p+q)命題為真。令n≥R(p-1,q)+R(p,q-1)。用紅、藍(lán)兩色涂色Kn的邊，則v1或關(guān)聯(lián)R(p-1,q)條藍(lán)邊或關(guān)聯(lián)R(p,q-1)條紅邊。如若不然，v1至多關(guān)聯(lián)R(p-1,q)-1+R(p,q-1)-1=R(p-1,q)+R(p,q-1)-2條邊，與n≥R(p-1,q)+R(p,q-1)矛盾。若v1關(guān)聯(lián)R(p-1,q)條藍(lán)邊，由歸納假設(shè)這R(p-1,q)個(gè)頂點(diǎn)中或含有一個(gè)藍(lán)色的完全p-1邊形，或含有一個(gè)紅色的完全q邊形。如為前者，則這個(gè)p-1邊形加上v1構(gòu)成一個(gè)藍(lán)色的完全p邊形，命題為真；如為后者，命題也為真。

44假設(shè)對(duì)一切正整數(shù)p,q(p+q<p+q)命題為45若v1關(guān)聯(lián)R(p,q-1)條紅邊，同理可證Kn中必含有一個(gè)藍(lán)色的完全p邊形或紅色的完全q邊形，從而證明了R(p,q)≤R(p-1,q)+R(p,q-1).因此結(jié)論成立。

例2.3.2

證明：R(3,3)=6

證明：由例2.3.1知R(3,3)≤6。而圖2.3.2中的實(shí)線代表藍(lán)色的邊，虛線代表紅色的邊，則這個(gè)的涂色方案既不包含藍(lán)三角形，也不包含紅三角形。所以R(3,3)>5。因此R(3,3)=6。

45若v1關(guān)聯(lián)R(p,q-1)條紅邊，同理可證Kn中必含有一464647定理2.3.2

設(shè)p,q是正整數(shù)，p，q≥2，則

R(p,q)=R(q,p)

證明：令n≥R(p,q)。對(duì)于藍(lán)、紅兩色涂色Kn的邊的任何一種方案，將藍(lán)邊換紅邊，紅邊換藍(lán)邊，則或存在一個(gè)藍(lán)色的完全p邊形，或存在一個(gè)紅色的完全q邊形。而原來(lái)的涂色方案中必存在一個(gè)紅色的完全p邊形或一個(gè)藍(lán)色的完全q邊形，即R(q,p)≥R(p,q)。同理可證R(p,q)≥R(q,p)。因此，R(p,q)=R(q,p)47定理2.3.2設(shè)p,q是正整數(shù)，p，q≥2，則

(22February1903–19January1930)wasaBritish

mathematicianwho,inadditiontomathematics,madesignificantandprecociouscontributionsinphilosophyandeconomicsbeforehisdeathattheageof26.HewasaclosefriendofLudwigWittgenstein,andwasinstrumentalintranslatingWittgenstein'sTractatusLogico-PhilosophicusintoEnglish,andinpersuadingWittgensteintoreturntophilosophyandCambridge.48FrankPlumptonRamsey(22February1903–19January生于劍橋，其父親是麥格達(dá)倫學(xué)院的校長(zhǎng)，其弟弟邁克爾·拉姆齊是第100任坎特伯里大主教。拉姆齊于溫切斯特公學(xué)學(xué)習(xí)，后來(lái)進(jìn)入劍橋大學(xué)三一學(xué)院學(xué)習(xí)數(shù)學(xué)。他涉獵了很多領(lǐng)域。在政治上，他有左翼的傾向；宗教上，其妻指他是個(gè)態(tài)度堅(jiān)定的無(wú)神論者。他和查爾斯·凱·奧格頓聊天時(shí)，說(shuō)他想學(xué)德語(yǔ)。奧格頓便給他一本文法書(shū)、字典和一篇深?yuàn)W的心理學(xué)論文并告訴他：使用那本文法書(shū)和字典，告訴我們你的想法。約一星期后，他不止學(xué)會(huì)了德語(yǔ)，還對(duì)語(yǔ)法書(shū)中一些理論提出了反對(duì)意見(jiàn)。他閱讀了維根斯坦的TractatusLogico-Philosophicus。這本書(shū)深深影響了他，1923年他去奧地利跟維根斯坦討論。1924年21歲的他成為國(guó)王學(xué)院的研究員。拉姆齊為治療慢性肝疾而接受腹部手術(shù)，但術(shù)后并發(fā)黃疸，于1930年1月19日病逝于倫敦蓋氏醫(yī)院（Guy'sHospital），得年僅26歲又11個(gè)月。49弗蘭克·拉姆齊(FrankPlumptonRamsey,1903.2.22-1930.1.19)生于劍橋，其父親是麥格達(dá)倫學(xué)院的校長(zhǎng)，其弟弟邁克爾·拉姆齊是5050保羅·埃爾德什（Erd?sPál，在英語(yǔ)中作PaulErd?s）（1913年3月26日－1996年9月20日），其音讀作air-dish，匈牙利語(yǔ)中的意思是來(lái)自山林。匈牙利籍猶太人，發(fā)表論文高達(dá)1475篇（包括與人合寫(xiě)的），為現(xiàn)時(shí)發(fā)表論文數(shù)最多產(chǎn)的數(shù)學(xué)家（其次是歐拉）；曾和511人合寫(xiě)論文。愛(ài)多士遺傳了來(lái)自數(shù)學(xué)教師父母優(yōu)異的數(shù)學(xué)天賦，三歲時(shí)就能輕松心算一個(gè)人一生所活的秒數(shù)，并每日在客人面前表演四位數(shù)的乘法心算。他年僅二十一歲即被厄特沃什·羅蘭大學(xué)(即布達(dá)佩斯大學(xué))授予數(shù)學(xué)博士學(xué)位，師從數(shù)學(xué)家LipótFejér(他也是馮紐曼的導(dǎo)師)。之后愛(ài)多士為了逃離納粹的追捕，歷任曼徹斯特大學(xué)教授與普林斯頓大學(xué)之研究人員。愛(ài)多士熱愛(ài)自由，十分討厭權(quán)威，尤其是法西斯。他四處游歷，探訪當(dāng)?shù)氐臄?shù)學(xué)家，與他們一起工作，合寫(xiě)論文。他很重視數(shù)學(xué)家的培訓(xùn)，遇到有天份的孩子，會(huì)鼓勵(lì)他們繼續(xù)研究。愛(ài)多士經(jīng)常沉思于數(shù)學(xué)問(wèn)題，視數(shù)學(xué)為生命，在母親死后，他開(kāi)始經(jīng)常服食精神藥物。他經(jīng)常長(zhǎng)時(shí)間工作，老年仍每日工作19小時(shí)，酷愛(ài)飲咖啡，曾說(shuō)“數(shù)學(xué)家是將咖啡轉(zhuǎn)換成定理的機(jī)器”。因?yàn)閻?ài)多士和別人合寫(xiě)的論文實(shí)在太多了，所以有人定義了埃爾德什數(shù)，簡(jiǎn)稱(chēng)埃數(shù)。愛(ài)多士的愛(ài)多士數(shù)為0，與他直接合作寫(xiě)論文的人的埃數(shù)為1，與埃數(shù)為1的人合寫(xiě)論文的人埃數(shù)為2，依此類(lèi)推。愛(ài)多士十分獨(dú)持。除了衣食住行這些生活基本要知道的事之外，他對(duì)很多問(wèn)題都毫不關(guān)心，終生未婚，年輕時(shí)甚至被人誤以為是同性戀者，但其實(shí)他無(wú)論對(duì)異性或是同性都沒(méi)有什么興趣。事實(shí)上，他是一個(gè)博學(xué)的人，對(duì)歷史了如指掌，但長(zhǎng)大后只專(zhuān)注數(shù)學(xué)，任何其他事情也不管。愛(ài)多士說(shuō)話有自己的一套“密語(yǔ)”，用各種有趣的名詞來(lái)代替神、美國(guó)、孩子和婚姻等，如上帝被叫SF（SupremeFascist，最大的法西斯的簡(jiǎn)稱(chēng)），小孩子被叫作epsilon（希臘語(yǔ)字母ε，數(shù)學(xué)中用于表示小量），美國(guó)被叫作山姆（Sam），蘇聯(lián)被叫作喬（Joe）。51PaulErd?s保羅·埃爾德什（Erd?sPál，在英語(yǔ)中作PaulEr525253第二章鴿巢原理和Ramsey定理組合存在性定理Ramsey定理（鴿巢原理為其最簡(jiǎn)形式）偏序集分解定理（Dilworth定理）相異代表系存在定理（Hall定理）1928年英國(guó)數(shù)學(xué)家、哲學(xué)家兼經(jīng)濟(jì)學(xué)家Frank，Ramsey(1903-1930)在倫敦?cái)?shù)學(xué)會(huì)上宣讀一篇“論形式邏輯中的一個(gè)問(wèn)題”的論文，奠定Ramsey理論的基礎(chǔ)。核心思想是：“任何一個(gè)足夠大的結(jié)構(gòu)中必定包含一個(gè)給定大小的規(guī)則子結(jié)構(gòu)”1第二章鴿巢原理和Ramsey定理組合存在性定理54第二章鴿巢原理和Ramsey定理

§2.1鴿巢原理的最簡(jiǎn)單形式§2.2鴿巢原理的加強(qiáng)形式§2.3Ramsey定理2第二章鴿巢原理和Ramsey定理

55§2.1鴿巢原理的最簡(jiǎn)單形式鴿巢原理(Pigeonholeprinciple)是組合學(xué)中最簡(jiǎn)單、最基本原理.也叫抽屜原理、重疊原理、狄利克雷原理。定理2.1.1若把n+1個(gè)物體放入n個(gè)盒子中，則至少有一個(gè)盒子中有2個(gè)或更多的物體3§2.1鴿巢原理的最簡(jiǎn)單形式鴿巢原理(Pigeonhol56證明：（反證法）

若不然，假定每個(gè)盒子中至多有一個(gè)物體，那么n個(gè)盒子中至多有n個(gè)物體，而我們共有n+1個(gè)物體，矛盾。故定理成立。

4證明：（反證法）57鴿巢原理的集合描述形式：

設(shè)有限集合A有n+1個(gè)元素，將A分劃成n個(gè)不相交子集的并，則至少有一個(gè)子集含有兩個(gè)或兩個(gè)以上的元素。注意！應(yīng)用時(shí)要分清物品與盒子以及物體數(shù)與盒子總數(shù)。這個(gè)原理只能用來(lái)證明某種安排的存在性，而卻不能找到具體滿(mǎn)足要求的安排

不能被推廣到只存在n個(gè)(或更少)物體的情形。5鴿巢原理的集合描述形式：58例2.1.1

共有12個(gè)屬相，今有13個(gè)人，則必有兩人的屬相相同。

幾個(gè)例子例2.1.2

有5雙不同的襪子混在一個(gè)抽屜里，我們至少?gòu)闹羞x出多少只襪子才能保證找到1雙襪子？

6例2.1.1共有12個(gè)屬相，今有13個(gè)人，則必有兩人的屬59解

應(yīng)用定理2.1.1，共有5個(gè)盒子，每個(gè)盒子對(duì)應(yīng)1雙襪子。如果選擇5+1=6只襪子分別放到它所屬那雙襪子的盒子中，則必有兩只襪子落入同一個(gè)盒子中，即為一雙襪子。因此我們至少?gòu)闹羞x出6只襪子才能保證找到1雙襪子。本例實(shí)際上是知道n個(gè)盒子，而找n+1個(gè)物體的問(wèn)題。

7解應(yīng)用定理2.1.1，共有5個(gè)盒子，每個(gè)盒子對(duì)應(yīng)1雙60例2.1.3 對(duì)任意給定的52個(gè)整數(shù)，證明：其中必存在兩個(gè)整數(shù)，要么兩者的和能被100整除，要么兩者的差能被100整除。

8例2.1.3 對(duì)任意給定的52個(gè)整數(shù)，證明：其中必存在兩個(gè)61思路：把52個(gè)物體放到51個(gè)盒子中，需要構(gòu)造51個(gè)盒子，根據(jù)題目要求的兩個(gè)整數(shù)必須具備的性質(zhì)構(gòu)造盒子；是否能夠被100整除的關(guān)鍵在余數(shù)，那么一個(gè)整數(shù)除以100的余數(shù)為0，1，2，…，99兩個(gè)整數(shù)的和可以被100整除，則二者的余數(shù)的和是100兩個(gè)整數(shù)的差可以被100整除，則二者的余數(shù)相同分析：9思路：分析：證明：對(duì)于任意一個(gè)整數(shù)，它除以100的余數(shù)顯然只能有如下100種情況，0，1，2，3，……，99而現(xiàn)在有任意給定的52個(gè)整數(shù)，我們需要構(gòu)造51個(gè)盒子，即對(duì)這100個(gè)余數(shù)進(jìn)行分組，共51組：{0},{1，99},{2，98},{3，97},……，{49，51}，{50}62證明：對(duì)于任意一個(gè)整數(shù)，它除以100的余數(shù)顯然只能有如下10根據(jù)定理2.1.1，這52個(gè)整數(shù)，必有兩個(gè)整數(shù)除以100的余數(shù)落入上面51組中的同一組中，若是{0}或{50}則說(shuō)明它們的和及差都能被100整除；若是剩下的49組的話，因?yàn)橐唤M有兩個(gè)余數(shù)，余數(shù)相同則它們的差能被100整除，余數(shù)不同則它們的和能被100整除。63根據(jù)定理2.1.1，這52個(gè)整數(shù)，必有兩個(gè)整數(shù)除以100的余64

例2.1.4

一名象棋大師有11周時(shí)間準(zhǔn)備一場(chǎng)錦標(biāo)賽，她決定每天至少下一盤(pán)棋，為了不能太累，一周中下棋的次數(shù)不能多于12盤(pán)。證明：她一定在此期間的連續(xù)若干天中恰好下棋21盤(pán)。

12例2.1.4一名象棋大師有11周時(shí)間準(zhǔn)備一場(chǎng)錦標(biāo)65證明:令b1，b2，…，b77分別為這11周中他每天下棋的次數(shù)，并作部分和a1=b1,a2=b1+b2,…，a77=b1+b2+…+b77.13證明:令b1，b2，…，b77分別為這11周中他每天下棋66所以有1≤a1<a2<a3<…<a77≤12×11=132(2.1.1)考慮數(shù)列a1,a2,…，a77，a1+21,a2+21,…，a77+21,它們都在1與132+21=153之間，共有154項(xiàng)，由定理2.1.1知，其中必有兩項(xiàng)相等根據(jù)題意，有bi≥1(1≤i≤77),且bi+bi+1+…+bi+6≤12(1≤i≤71),14所以有根據(jù)題意，有bi≥1(1≤i≤77),且bi+bi67由（2.1.1）式知a1,a2,…，a77這77項(xiàng)互不相等，從而a1+21,a2+21,…，a77+21這77項(xiàng)也互不相等，所以一定存在1≤i<j≤77，使得aj=ai+21.因此21=aj-ai=(b1+b2+…+bi+bi+1+…+bj)-(b1+b2+…+bi)=bi+1+bi+2+…+bj.這說(shuō)明從第i+1天到第j天這連續(xù)j-i天中，她剛好下了21盤(pán)棋。15由（2.1.1）式知a1,a2,…，a77這77項(xiàng)互不相68例2.1.5

將一個(gè)矩形分成4行19列的網(wǎng)格，每個(gè)單元格涂1種顏色，有3種顏色可以選擇。證明：無(wú)論怎樣涂色，其中必有一個(gè)由單元格構(gòu)成的矩形的4個(gè)角上的格子被涂上同一種顏色。16例2.1.5將一個(gè)矩形分成4行19列的網(wǎng)格，每個(gè)單元69證明：首先對(duì)每一列而言，因?yàn)橛?行，但只有3種顏色選擇。根據(jù)定理2.1.1，則必有兩個(gè)單元格的顏色相同。另外，每列中兩個(gè)單元格的不同位置組合有=6種，這樣一列中兩個(gè)同色單元格的位置組合共有18種情況，

17證明：首先對(duì)每一列而言，因?yàn)橛?行，但只有3種顏色選擇。而現(xiàn)在共有19列，根據(jù)定理2.1.1，無(wú)論怎樣涂色，則必有兩列與圖中的某一列相同，即各自所包含的兩個(gè)同色單元格的位置相同、顏色相同。即結(jié)論成立。

70而現(xiàn)在共有19列，根據(jù)定理2.1.1，無(wú)論怎樣涂色，則必有兩71例2.1.6

證明：任意n2+1個(gè)實(shí)數(shù)組成的序列中，必有一個(gè)長(zhǎng)度為n+1的遞增子序列，或必有一個(gè)長(zhǎng)度為n+1的遞減子序列。

19例2.1.6證明：任意n2+1個(gè)實(shí)數(shù)1、子序列概念

如果是一個(gè)序列，那么，是一個(gè)子序列，其中，2、遞增子序列概念若滿(mǎn)足3、遞減子序列概念若滿(mǎn)足72分析：1、子序列概念

如果73證明：由題意，設(shè)Li是從ai開(kāi)始的遞減子序列的最大長(zhǎng)度，Mi是從ai開(kāi)始的遞增子序列的最大長(zhǎng)度，則對(duì)于i從1到n2

+1的每個(gè)i的取值，都有（Li,Mi）與之對(duì)應(yīng)。21證明：由題意，設(shè)Li是從ai開(kāi)始的遞減子序列的最大長(zhǎng)度，74（1）若ai>aj，則ai與從aj開(kāi)始的最長(zhǎng)遞減子序列合并，組成的子序列的長(zhǎng)度Li

≥Lj+1

>Lj；這與Li

=Lj矛盾；反證法。假設(shè)既不存在長(zhǎng)度為n+1的遞增子序列，也不存在長(zhǎng)度為n+1的遞減子序列即1≤Li≤n

且1≤Mi≤n，其中1≤i≤n2+1，由集合論的知識(shí)知：集合{(Li,Mi)}的元素?cái)?shù)最多為n2，根據(jù)定理2.1.1，必然有（Li,Mi）=(Lj,Mj)（i<j），當(dāng)然Li

=Lj，而且Mi

=Mj。對(duì)于序列中的元素ai,aj，分兩種情況：

22（1）若ai>aj，則ai與從aj開(kāi)始的最長(zhǎng)遞減子序75（2）若ai<aj，則ai與從aj開(kāi)始的最長(zhǎng)遞增子序列合并，組成的子序列的長(zhǎng)度Mi

≥Mj+1>Mj，這又與Mi=Mj矛盾。所以假設(shè)1≤Li≤n

且1≤Mi≤n不成立。原結(jié)論成立。這個(gè)例子的結(jié)論是1935年由數(shù)學(xué)家保羅·艾狄胥（Erd?s）和喬治·塞克爾斯（Szekeres）首先給出的，它還有更為有趣的表述：n2+1個(gè)人肩并肩地站成一排，則總能選除n+1個(gè)人，讓他們向前邁出一步，所形成新一排的身高是遞增或遞減的。23（2）若ai<aj，則ai與從aj開(kāi)始的最長(zhǎng)遞增子序76§2.2鴿巢原理的加強(qiáng)形式定理2.2.1(鴿巢原理的加強(qiáng)形式)24§2.2鴿巢原理的加強(qiáng)形式定理2.2.1(鴿巢原77證明：(反證法)

對(duì)于i＝1，2，…，n，假設(shè)第i個(gè)盒子里至多含有qi-1個(gè)物體，則n個(gè)盒子里物體數(shù)的總和不超過(guò)

q1+q2+…+qn-

n這與已知條件中的物體總數(shù)為(q1+q2+…+qn–

n+1)相矛盾。故假設(shè)不對(duì)，原結(jié)論成立。25證明：(反證法)78

與簡(jiǎn)單形式的關(guān)系

上節(jié)的鴿巢原理的簡(jiǎn)單形式是這一原理的特殊情況，即q1=q2=…=qn=2，有

q1+q2+…+qn－n+1=n+126與簡(jiǎn)單形式的關(guān)系79推論2.2.1

若n(r-1)+1個(gè)物體放入n個(gè)盒子。則至少有一個(gè)盒子里含有r個(gè)或者更多的物體。證明在定理2.2.1中取q1=q2=…=qn=r即可。27推論2.2.1若n(r-1)+1個(gè)物體放入n個(gè)盒80

推論2.2.2

若設(shè)有n個(gè)正整數(shù)m1,m2,…,mn滿(mǎn)足下面的不等式

(m1+…+mn)/n>

r－1,

則

m1,…,mn中至少有一個(gè)數(shù)≥

r證明

由上面的不等式得

m1+…+mn≥

n(r－1)+1，由推論2.2.1，存在mi，使得mi≥r。28推論2.2.2若設(shè)有n個(gè)正整數(shù)m1,m2,81推論2.2.3

設(shè)m和n都是正整數(shù)且m>n，若將m個(gè)物體放入n個(gè)盒子中，則至少有一個(gè)盒子中含有大于等于個(gè)物體。表示取天棚運(yùn)算是大于等于的最小正整數(shù)

證明：根據(jù)的定義有：

29推論2.2.3設(shè)m和n都是正整數(shù)且m>n，若將m個(gè)物體82反證法。假定每個(gè)盒子里的物體都小于個(gè)。，則至多是個(gè)，那么n個(gè)盒子里的物體總數(shù)≤n()<n×

=m，與m個(gè)物體矛盾。因此原結(jié)論成立。

30反證法。假定每個(gè)盒子里的物體都小于個(gè)。83例2.2.1一個(gè)袋子里裝了10個(gè)蘋(píng)果，11個(gè)橘子，12個(gè)香蕉，至少取出多少個(gè)水果才能保證已經(jīng)取出10個(gè)相同種類(lèi)的水果。解根據(jù)定推論2.2.1，若將3×(10-1)+1=28個(gè)物體放入3個(gè)盒子中，則至少有一個(gè)盒子中有10個(gè)物體。顯然物體就是三種水果，而盒子就是三類(lèi)水果，結(jié)論是保證已經(jīng)取出10個(gè)相同種類(lèi)的水果等價(jià)于或者取出10個(gè)蘋(píng)果或者取出10個(gè)橘子或者取出10個(gè)香蕉。因此答案是至少取28個(gè)水果才能保證已經(jīng)取出10個(gè)相同種類(lèi)的水果。

31例2.2.1一個(gè)袋子里裝了10個(gè)蘋(píng)果，11個(gè)橘子，1284例2.2.2

一家汽車(chē)租賃公司共有105輛汽車(chē)，共有座位600個(gè)，證明至少有一輛6座以上的汽車(chē)？

證明：根據(jù)推論2.2.3，所以至少有一輛6座以上的汽車(chē)。32例2.2.2一家汽車(chē)租賃公司共有105輛汽車(chē)，共有座位85例2.2.3

設(shè)有大小兩只圓盤(pán)，每個(gè)都劃分成大小相等的200個(gè)小扇形，在大盤(pán)上任選100個(gè)小扇形涂成黑色，其余的100個(gè)小扇形涂成白色，而將小盤(pán)上的200個(gè)小扇形任意涂成黑色或白色?，F(xiàn)將大小兩只圓盤(pán)的中心重合，轉(zhuǎn)動(dòng)小盤(pán)使小盤(pán)上的每個(gè)小扇形含在大盤(pán)上小扇形之內(nèi)。證明：有一個(gè)位置使小盤(pán)上至少有100個(gè)小扇形同大盤(pán)上相應(yīng)的小扇形同色。33例2.2.3設(shè)有大小兩只圓盤(pán)，每個(gè)都劃分成大小相等863487證明

如圖2.2.1所示，使大小兩盤(pán)中心重合，固定大盤(pán)，轉(zhuǎn)動(dòng)小盤(pán)，則有200個(gè)不同位置使小盤(pán)上的每個(gè)小扇形含在大盤(pán)上的小扇形中，由于大盤(pán)上的200個(gè)小扇形中有100個(gè)涂成黑色，100個(gè)涂成白色，所以小盤(pán)上的每個(gè)小扇形無(wú)論涂成黑色或白色，在200個(gè)可能的重合位置上恰好有100次與大盤(pán)上的小扇形同色，因而小盤(pán)上的200個(gè)小扇形在200個(gè)重合位置上共同色100×200=20000次，平均每個(gè)位置同色20000÷200=100次。由推論2.2.3知，存在著某個(gè)位置，使同色的小扇形數(shù)大于等于100個(gè)。35證明88例2.2.4證明：任意n2+1個(gè)實(shí)數(shù)組成的序列中，必有一個(gè)長(zhǎng)度為n+1的遞增子序列，或必有一個(gè)長(zhǎng)度為n+1的遞減子序列。

36例2.2.4證明：任意n2+1個(gè)實(shí)數(shù)組成的序列中，89例2.2.4用鴿巢原理的加強(qiáng)形式證明證明：假設(shè)長(zhǎng)為n2+1的實(shí)數(shù)序列中沒(méi)有長(zhǎng)度為n+1的遞增子序列，下面證明其必有一長(zhǎng)度為n+1的遞減子序列。 令mk表示從ak開(kāi)始的最長(zhǎng)遞增子序列的長(zhǎng)度，因?yàn)閷?shí)數(shù)序列中沒(méi)有長(zhǎng)度為n+1的遞增子序列，所以有：

根據(jù)推論2.2.3，這相當(dāng)于把n2+1個(gè)物體

37例2.2.4用鴿巢原理的加強(qiáng)形式證明證明：假設(shè)長(zhǎng)為n290放入n個(gè)盒子1，2，…，n中，必有一個(gè)盒子i里面至少有個(gè)物體，即存在n+1個(gè)mk取值相同，有使得（2.2.1）

對(duì)應(yīng)于這些下標(biāo)的實(shí)數(shù)序列必滿(mǎn)足

（2.2.2）

38放入n個(gè)盒子1，2，…，n中，必有一個(gè)盒子i里（2.2.91它們構(gòu)成一長(zhǎng)為n+1的遞減序列。否則，若有某個(gè)j（）使得，那么由從開(kāi)始的最長(zhǎng)遞增子序列加上，就得到一個(gè)從開(kāi)始的長(zhǎng)度為的遞增子序列。由的定義知這與（2.2.1）式矛盾。因此（2.2.2）式成立。同理可證若沒(méi)有長(zhǎng)度為n+1的遞減子序列，則必有一長(zhǎng)度為n+1的遞增子序列。因此，結(jié)論成立。39它們構(gòu)成一長(zhǎng)為n+1的遞減序列。任何一個(gè)6人聚會(huì)，必有3個(gè)人相互認(rèn)識(shí)或者相互不認(rèn)識(shí)92§2.3Ramsey定理

其思想可以概括為“在任何一個(gè)足夠大的結(jié)構(gòu)中必定包含一個(gè)給定大小的規(guī)則子結(jié)構(gòu)”。

任何一個(gè)6人聚會(huì)，必有3個(gè)人相互認(rèn)識(shí)或者相互不認(rèn)識(shí)40§293例2.3.1

設(shè)K6是6個(gè)頂點(diǎn)的完全圖，用紅、藍(lán)兩色涂色K6的邊，則存在一個(gè)紅色三角形，或存在一個(gè)藍(lán)色三角形。證明：設(shè)K6的頂點(diǎn)為v1,v2,…,v6。對(duì)于K6的任何一種涂色方案，由推論2.2.3.，v1關(guān)聯(lián)的邊中必有條同色邊。不妨設(shè)這三條邊為{v1

,v2},{v1

,v3},{v1,v4}

41例2.3.1設(shè)K6是6個(gè)頂點(diǎn)的完全圖，用紅、藍(lán)兩色涂色94若這三邊為紅色，當(dāng)v2,v3,v4之間有一條紅邊，比如說(shuō)是{v2,v3},則v1v2v3構(gòu)成一個(gè)紅三角形；當(dāng)v2,v3

,v4之間沒(méi)有紅邊，則v2v3v4構(gòu)成一個(gè)藍(lán)三角形。若這三邊為藍(lán)色時(shí)，同理可證。因此，結(jié)論成立。

v2

v3

v4v142若這三邊為紅色，當(dāng)v2,v3,v4之間有一條紅邊，定理2.3.1

設(shè)p，q是正整數(shù)，p，q≥2，則存在最小的正整數(shù)R(p,q)，使得當(dāng)n≥R(p,q)時(shí)，用紅、藍(lán)兩色涂色Kn的邊，或者存在一個(gè)藍(lán)色的完全p邊形Kp，或者存在一個(gè)紅色的完全q邊形Kq。

95證明：采用數(shù)學(xué)歸納法。 設(shè)p為任意正整數(shù)，q=2。用紅、藍(lán)兩色涂色Kp的邊，若沒(méi)有一條紅邊，則存在一個(gè)藍(lán)色的完全p邊形；若有一條紅邊，則構(gòu)成一個(gè)完全紅2邊形，因此R(p,2)≤p。同理可證R(2,q)≤q。定理2.3.1設(shè)p，q是正整數(shù)，p，q≥2，則存在最小96假設(shè)對(duì)一切正整數(shù)p,q(p+q<p+q)命題為真。令n≥R(p-1,q)+R(p,q-1)。用紅、藍(lán)兩色涂色Kn的邊，則v1或關(guān)聯(lián)R(p-1,q)條藍(lán)邊或關(guān)聯(lián)R(p,q-1)條紅邊。如若不然，v1至多關(guān)聯(lián)R(p-1,q)-1+R(p,q-1)-1=R(p-1,q)+R(p,q-1)-2條邊，與n≥R(p-1,q)+R(p,q-1)矛盾。若v1關(guān)聯(lián)R(p-1,q)條藍(lán)邊，由歸納假設(shè)這R(p-1,q)個(gè)頂點(diǎn)中或含有一個(gè)藍(lán)色的完全p-1邊形，或含有一個(gè)紅色的完全q邊形。如為前者，則這個(gè)p-1邊形加上v1構(gòu)成一個(gè)藍(lán)色的完全p邊形，命題為真；如為后者，命題也為真。

44假設(shè)對(duì)一切正整數(shù)p,q(p+q<p+q)命題為97若v1關(guān)聯(lián)R(p,q-1)條紅邊，同理可證Kn中必含有一個(gè)藍(lán)色的完全p邊形或紅色的完全q邊形，從而證明了R(p,q)≤R(p-1,q)+R(p,q-1).因此結(jié)論成立。

例2.3.2

證明：R(3,3)=6

證明：由例2.3.1知R(3,3)≤6。而圖2.3.2中的實(shí)線代表藍(lán)色的邊，虛線代表紅色的邊，則這個(gè)的涂色方案既不包含藍(lán)三角形，也不包含紅三角形。所以R(3,3)>5。因此R(3,3)=6。

45若v1關(guān)聯(lián)R(p,q-1)條紅邊，同理可證Kn中必含有一984699定理2.3.2

設(shè)p,q是正整數(shù)，p，q≥2，則

R(p,q)=R(q