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

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

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

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

(m1+…+mn)/n>

r－1,

則

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

r推論2.2.3

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

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

(m1+…+mn)/n>

r－1,

則

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

r

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

(m1+…+mn)/n<

r+1,

則

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

設(shè)m和n都是正整數(shù)且m>n，若將m個(gè)物體放入n個(gè)盒子中，則至少有一個(gè)盒子中有大于等于個(gè)物體2023年2月2日第二章鴿巢原理和Ramsey定理例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)的小扇形同色。2023年2月2日第二章鴿巢原理和Ramsey定理2023年2月2日第二章鴿巢原理和Ramsey定理證明

如圖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÷20=100次。由推論2.2.3知，存在著某個(gè)位置，使同色的小扇形數(shù)大于等于100個(gè)。

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

2023年2月2日第二章鴿巢原理和Ramsey定理證明：假設(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è)物體

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

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

（2.2.2）

它們構(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é)論成立?！?.3Ramsey定理

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

設(shè)K6是6個(gè)頂點(diǎn)的完全圖，用紅、藍(lán)兩色涂色K6的邊，則存在一個(gè)紅色三角形，或存在一個(gè)藍(lán)色三角形。證明：設(shè)K6的頂點(diǎn)為v1,v2,v3,v4,v5,v6.對(duì)于任意一種涂色方案，根據(jù)鴿巢原理加強(qiáng)形式的推論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

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

用紅、藍(lán)兩色涂色K9的邊，證明或者存在一個(gè)藍(lán)色的三角形或紅色的完全四邊形。Ramsey定理簡(jiǎn)單形式定理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。

稱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è)對(duì)正整數(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)，用藍(lán)紅兩色涂色Kn的邊，則case1v1關(guān)聯(lián)R(p-1,q)條藍(lán)邊，case2v1關(guān)聯(lián)R(p,q-1)條紅邊.對(duì)于case1，如為藍(lán)色Kp-1,構(gòu)成藍(lán)色Kp；如為紅色Kq，則滿足要求.對(duì)于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中的實(shí)線代表藍(lán)色的邊，虛線代表紅色的邊，則這個(gè)的涂色方案既不包含藍(lán)三角形，也不包含紅三角形。所以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)。對(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)R(p,q)的圖表示R(p,q)的集合表述Kn

的頂點(diǎn)集V集合SKn

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

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

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

對(duì)于任意給定的正整數(shù)p,q,r,(p,q≥r)存在一個(gè)最小的正整數(shù)R(p,q;r)使得當(dāng)集合S的元素?cái)?shù)大于等于R(p,q;r)時(shí)，將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ù)，則存在一個(gè)最小的正整數(shù)R(q1,q2,…,qk;r)，使得當(dāng)n≥R(q1,q2,…,qk;r)時(shí),當(dāng)n元集S的所有r元子集劃分成k個(gè)子集族T1,T2,…,Tk，那么存在S的q1元子集A1,其所有的r元子集屬于T1,或者存在S的q2元子集