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

1、2024年3月19日,第二章 鴿巢原理和Ramsey定理,§2.2 鴿巢原理的加強(qiáng)形式,定理2.2.1 (鴿巢原理的加強(qiáng)形式),2024年3月19日,第二章 鴿巢原理和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 +

2、 … +mn)/n > r－1, 則 m1,…, mn中至少有一個(gè)數(shù)≥ r,推論2.2.3 設(shè)m和n都是正整數(shù)且m>n，若將m個(gè)物體放入n個(gè)盒子中，則至少有一個(gè)盒子中有大于等于 個(gè)物體,2024年3月19日,第二章 鴿巢原理和Ramsey定理,推論2.2.2 若設(shè)有n個(gè)正整數(shù)m1 , m2 , … , mn滿足下面的不等式 (m1 + … +mn

3、)/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+1,2024年3月19日,第二章 鴿巢原理和Ramsey定理,推論2.2.3 設(shè)m和n都是正整數(shù)且

4、m>n，若將m個(gè)物體放入n個(gè)盒子中，則至少有一個(gè)盒子中有大于等于 個(gè)物體,2024年3月19日,第二章 鴿巢原理和Ramsey定理,例2.2.3 設(shè)有大小兩只圓盤，每個(gè)都劃分成大小相等的200個(gè)小扇形，在大盤上任選100個(gè)小扇形涂成黑色，其余的100個(gè)小扇形涂成白色，而將小盤上的200個(gè)小扇形任意涂成黑色或白色。現(xiàn)將大小兩只圓盤的中心重合，轉(zhuǎn)動(dòng)小盤使小盤上的每個(gè)小扇形含在大盤上小扇形之內(nèi)。證明：有一個(gè)位置使小盤上

5、至少有100個(gè)小扇形同大盤上相應(yīng)的小扇形同色。,2024年3月19日,第二章 鴿巢原理和Ramsey定理,2024年3月19日,第二章 鴿巢原理和Ramsey定理,證明 如圖2.2.1所示，使大小兩盤中心重合，固定大盤，轉(zhuǎn)動(dòng)小盤，則有200個(gè)不同位置使小盤上的每個(gè)小扇形含在大盤上的小扇形中，由于大盤上的200個(gè)小扇形中有100個(gè)涂成黑色，100個(gè)涂成白色，所以小盤上的每個(gè)小扇形無論涂成黑色或白色，在200個(gè)可能的重合位置上恰好有10

6、0次與大盤上的小扇形同色，因而小盤上的200個(gè)小扇形在200個(gè)重合位置上共同色100×200=20000次，平均每個(gè)位置同色20000÷20=100次。由推論2.2.3知，存在著某個(gè)位置，使同色的小扇形數(shù)大于等于100個(gè)。,2024年3月19日,第二章 鴿巢原理和Ramsey定理,例2.2.4 用鴿巢原理的加強(qiáng)形式證明,,,證明：任意n2+1 個(gè)實(shí)數(shù)組成的序列中，必有一個(gè)長度為n+1的遞增子序列，或必有一個(gè)長度為

7、n+1的遞減子序列。,2024年3月19日,第二章 鴿巢原理和Ramsey定理,證明：假設(shè)長為n2+1的實(shí)數(shù)序列中沒有長度為n+1的遞增子序列，下面證明其必有一長度為n+1的遞減子序列。令mk表示從ak開始的最長遞增子序列的長度，因?yàn)閷?shí)數(shù)序列中沒有長度為n+1的遞增子序列，所以有：,,根據(jù)推論2.2.3，這相當(dāng)于把n2+1個(gè)物體,,放入n個(gè)盒子1，2，…，n中，必有一個(gè)盒子i里面至少有

8、 個(gè)物體，即存在n+1個(gè)mk取值相同，有使得,,（2.2.1）,對(duì)應(yīng)于這些下標(biāo)的實(shí)數(shù)序列必滿足,,（2.2.2）,它們構(gòu)成一長為n+1的遞減序列。否則，若有某個(gè)j（ ）使得 ，那么由從 開始的最長遞增子序列加上 ，就得到一個(gè)從 開始的長度為 的遞增子序列。由 的定義知這與（2.2.1）式矛盾。因此（2.2.2）式

9、成立。同理可證若沒有長度為n+1的遞減子序列，則必有一長度為n+1的遞增子序列。因此，結(jié)論成立。,,,,,,,§2.3 Ramsey定理,任何一個(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,v

10、5,v6.對(duì)于任意一種涂色方案，根據(jù)鴿巢原理加強(qiáng)形式的推論3， 與v1關(guān)聯(lián)的5條邊至少有,條同色邊,不妨設(shè)這三條邊為{v1 ,v2},{v1 ,v3},{v1 ,v4} （1）若這三條邊均為紅色,,,,v1,v2,v3,v4,(a) 當(dāng)v2 ,v3 ,v4 之間有一條紅邊，如{v2 ,v3}(b) v2 ,v3 ,v4 之間沒有紅邊，,v1,v2,v3,v4,(a),(b),（2）若這三條邊均為藍(lán)色，同理可證.,2024年3月

11、19日,第二章 鴿巢原理和Ramsey定理,例2.3.2 用紅、藍(lán)兩色涂色K9的邊，證明或者存在一個(gè)藍(lán)色的三角形或紅色的完全四邊形。,Ramsey 定理簡單形式定理 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)困

12、難的工作。到目前為止，僅有極少數(shù)小p，q的Ramsey數(shù)被找到。,2024年3月19日,第二章 鴿巢原理和Ramsey定理,證明思路：歸納法 歸納假設(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 為真，

13、則R(p-1,q), R(p,q-1) 存在. 令 n ≥ R(p-1,q) + R(p,q-1)，用藍(lán)紅兩色涂色Kn的邊，則case1 v1關(guān)聯(lián)R(p-1,q)條藍(lán)邊，case2 v1關(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),,例

14、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)

15、色的完全p邊形，或存在一個(gè)紅色的完全q邊形。而原來的涂色方案中必存在一個(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 的邊集E S 的2 元子集的集合T用2 色涂色Kn 的邊

16、 將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,

17、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í),

18、當(dāng)n元集S 的所有r 元子集劃分成k 個(gè)子集族T1, T2, … , Tk，那么存在S 的q1元子集A1, 其所有的r元子集屬于T1, 或者存在S 的q2元子集A2，A2的所有r 元子集屬于T2, … ,或者存在S 的qk 元子集Ak, 其所有的r元子集屬于Tk .,,Ramsey定理斷定Ramsey數(shù)的存在性.Ramsey數(shù)的確定是一個(gè)很困難的問題.r=1, 是鴿巢原理，R(q1,q2, …, qk ;1) = q1+q2+…+