組合數(shù)學(xué)鴿巢原理

2023年2月2日第二章鴿巢原理和Ramsey定理§2.2鴿巢原理的加強形式定理2.2.1(鴿巢原理的加強形式)2023年2月2日第二章鴿巢原理和Ramsey定理推論2.2.1

若n(r－1)+1個物品放入n個盒子。則至少有一個盒子里含有r個或者更多的物品。

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

(m1+…+mn)/n>

r－1,

則

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

r推論2.2.3

設(shè)m和n都是正整數(shù)且m>n，若將m個物體放入n個盒子中，則至少有一個盒子中有大于等于個物體2023年2月2日第二章鴿巢原理和Ramsey定理

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

(m1+…+mn)/n>

r－1,

則

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

r

另外兩個平均原理：設(shè)有n個正整數(shù)m1,m2,…,mn滿足下面的不等式

(m1+…+mn)/n<

r+1,

則

m1,…,mn中至少有一個數(shù)<r+12023年2月2日第二章鴿巢原理和Ramsey定理推論2.2.3

設(shè)m和n都是正整數(shù)且m>n，若將m個物體放入n個盒子中，則至少有一個盒子中有大于等于個物體2023年2月2日第二章鴿巢原理和Ramsey定理例2.2.3設(shè)有大小兩只圓盤，每個都劃分成大小相等的200個小扇形，在大盤上任選100個小扇形涂成黑色，其余的100個小扇形涂成白色，而將小盤上的200個小扇形任意涂成黑色或白色?，F(xiàn)將大小兩只圓盤的中心重合，轉(zhuǎn)動小盤使小盤上的每個小扇形含在大盤上小扇形之內(nèi)。證明：有一個位置使小盤上至少有100個小扇形同大盤上相應(yīng)的小扇形同色。2023年2月2日第二章鴿巢原理和Ramsey定理2023年2月2日第二章鴿巢原理和Ramsey定理證明

如圖2.2.1所示，使大小兩盤中心重合，固定大盤，轉(zhuǎn)動小盤，則有200個不同位置使小盤上的每個小扇形含在大盤上的小扇形中，由于大盤上的200個小扇形中有100個涂成黑色，100個涂成白色，所以小盤上的每個小扇形無論涂成黑色或白色，在200個可能的重合位置上恰好有100次與大盤上的小扇形同色，因而小盤上的200個小扇形在200個重合位置上共同色100×200=20000次，平均每個位置同色20000÷20=100次。由推論2.2.3知，存在著某個位置，使同色的小扇形數(shù)大于等于100個。

2023年2月2日第二章鴿巢原理和Ramsey定理例2.2.4用鴿巢原理的加強形式證明證明：任意n2+1個實數(shù)組成的序列中，必有一個長度為n+1的遞增子序列，或必有一個長度為n+1的遞減子序列。

2023年2月2日第二章鴿巢原理和Ramsey定理證明：假設(shè)長為n2+1的實數(shù)序列中沒有長度為n+1的遞增子序列，下面證明其必有一長度為n+1的遞減子序列。 令mk表示從ak開始的最長遞增子序列的長度，因為實數(shù)序列中沒有長度為n+1的遞增子序列，所以有：

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

放入n個盒子1，2，…，n中，必有一個盒子i里面至少有個物體，即存在n+1個mk取值相同，有使得（2.2.1）

對應(yīng)于這些下標的實數(shù)序列必滿足

（2.2.2）

它們構(gòu)成一長為n+1的遞減序列。否則，若有某個j（）使得，那么由從開始的最長遞增子序列加上，就得到一個從開始的長度為的遞增子序列。由的定義知這與（2.2.1）式矛盾。因此（2.2.2）式成立。同理可證若沒有長度為n+1的遞減子序列，則必有一長度為n+1的遞增子序列。因此，結(jié)論成立?！?.3Ramsey定理

任何一個6人聚會，必有3個人相互認識或者相互不認識其思想可以概括為“在任何一個足夠大的結(jié)構(gòu)中必定包含一個給定大小的規(guī)則子結(jié)構(gòu)”。例2.3.1

設(shè)K6是6個頂點的完全圖，用紅、藍兩色涂色K6的邊，則存在一個紅色三角形，或存在一個藍色三角形。證明：設(shè)K6的頂點為v1,v2,v3,v4,v5,v6.對于任意一種涂色方案，根據(jù)鴿巢原理加強形式的推論3，與v1關(guān)聯(lián)的5條邊至少有條同色邊不妨設(shè)這三條邊為{v1

,v2},{v1,v3},{v1,v4}（1）若這三條邊均為紅色v1v2v3v4(a)當(dāng)v2,v3,v4

之間有一條紅邊，如{v2,v3}(b)v2,v3,v4

之間沒有紅邊，v1v2v3v4v1v2v3v4(a)(b)（2）若這三條邊均為藍色，同理可證.2023年2月2日第二章鴿巢原理和Ramsey定理例2.3.2

用紅、藍兩色涂色K9的邊，證明或者存在一個藍色的三角形或紅色的完全四邊形。Ramsey定理簡單形式定理2.3.1

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

稱R(p,q)為Ramsey數(shù)；確定精確的Ramsey數(shù)的值是相當(dāng)困難的工作。到目前為止，僅有極少數(shù)小p，q的Ramsey數(shù)被找到。

2023年2月2日第二章鴿巢原理和Ramsey定理qp3456789103691418232836404341825354149615684691159214954349588780143101216121316141442610216511129812749516978017811717205540216103123217132826828218703173583609095656588580126771079823556證明思路：歸納法歸納假設(shè)

R(p,2)≤p,R(2,q)≤q,

歸納步驟

R(p-1,q)，R(q-1,p)存在?R(p,q)≤R(p-1,q)+R(q-1,p)假設(shè)對正整數(shù)p’,q’,p’≤p,q’≤q,p’+q’<p+q為真，則R(p-1,q),R(p,q-1)存在.令n≥R(p-1,q)+R(p,q-1)，用藍紅兩色涂色Kn的邊，則case1v1關(guān)聯(lián)R(p-1,q)條藍邊，case2v1關(guān)聯(lián)R(p,q-1)條紅邊.對于case1，如為藍色Kp-1,構(gòu)成藍色Kp；如為紅色Kq，則滿足要求.對于case2可以類似分析.R(p,q)≤R(p-1,q)+R(q-1,p)

例2.3.3

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

定理2.3.2

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

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

證明：令n≥R(p,q)。對于藍、紅兩色涂色Kn的邊的任何一種方案，將藍邊換紅邊，紅邊換藍邊，則或存在一個藍色的完全p邊形，或存在一個紅色的完全q邊形。而原來的涂色方案中必存在一個紅色的完全p邊形或一個藍色的完全q邊形，即R(q,p)≥R(p,q)。同理可證R(p,q)≥R(q,p)。因此，R(p,q)=R(q,p)R(p,q)的圖表示R(p,q)的集合表述Kn

的頂點集V集合SKn

的邊集ES的2元子集的集合T用2色涂色Kn

的邊將T劃分成E1,E2存在藍色完全p邊形存在S的p子集其所有2元子集∈E1存在紅色完全q邊形存在S的q子集其所有2元子集∈E2集合表述具有更強的表達能力.定理推廣（1）

將2元子集推廣到r元子集

對于任意給定的正整數(shù)p,q,r,(p,q≥r)存在一個最小的正整數(shù)R(p,q;r)使得當(dāng)集合S的元素數(shù)大于等于R(p,q;r)時，將S的r子集族任意劃分成E1,E2，則或者S有p子集A，A的所有r元子集屬于E1,或者存在q子集B，B的所有r元子集屬于E2.定理推廣（2）

將T劃分成E1,E2,…,Ek

設(shè)r,k≥1,qi≥r,i=1,2,…,k,是給定正整數(shù)，則存在一個最小的正整數(shù)R(q1,q2,…,qk;r)，使得當(dāng)n≥R(q1,q2,…,qk;r)時,當(dāng)n元集S的所有r元子集劃分成k個子集族T1,T2,…,Tk，那么存在S的q1元子集A1,其所有的r元子集屬于T1,或者存在S的q2元子集