組合數(shù)學講義

1、1,《組合數(shù)學》,第八講,鴿巢原理?Ramsey數(shù),,,,djwang math.tsinghua.edu.cn,王殿軍,2003.11.12.,2,第八講: 內(nèi)容提要,III. 一般形式的鴿巢原理,IV. Ramsey 數(shù),V*. Ramsey 定理,II. 鴿巢原理,I. 本講引言,VI*. Ramsey 數(shù)的應用,3,I. 本講引言,鴿巢原理又稱抽屜原理或鞋盒原理, 這個原理最早是由Dirichlet提出的. 鴿巢原理

2、是解決組合論中一些存在性問題的基本而又有力的工具. 它是組合數(shù)學中最簡單也是最基本的原理之一, 從這個原理出發(fā), 可以導出許多有趣結果,而這些結果常常是令人驚奇的.Ramsey理論它對組合數(shù)學發(fā)展產(chǎn)生過重要的影響.,4,1928年, 年僅24歲的英國杰出數(shù)學家Ramsey發(fā)表了著名論文《論形式邏輯中的一個問題》, 他在這篇論文中, 提出并證明了關于集合論的一個重大研究成果, 現(xiàn)稱為Ramsey定理.盡管兩年后他不幸去世, 但是他開拓

3、的這一新領域至今仍十分活躍, 而且近年來在科技領域獲得了成功的應用.本講主要介紹鴿巢原理、Ramsey數(shù)及性質(zhì)、 Ramsey定理及應用.,5,II. 鴿巢原理,定理1 若有n+1只鴿子飛回n個鴿巢,則至少有兩只鴿子飛入了同一個鴿巢.這個原理的證明非常容易, 只要使用反證法馬上就可以得到結論. 這個原理也可以表述為: 如果把n+1件東西放入n個盒子中, 則至少有一個盒子里面有不少于兩件的東西.,6,鴿巢原理不能用來

4、尋找究竟是哪個盒子含有兩件或更多件東西.該原理只能證明某種安排或某種現(xiàn)象存在,而并未指出怎樣構造這種安排或怎樣尋找這種現(xiàn)象出現(xiàn)的場合.從鴿巢原理出發(fā), 對于許多實際問題, 我們可以導出非常有趣的結果. 利用鴿巢原理解決實際問題的關鍵是要看出這是一個鴿巢問題, 建立“鴿巢”，尋找“鴿子”.,7,例1. 如果有13個人其中必然有兩個人出生在同一個月.例2. 如果鞋架上放10雙鞋, 從中任意取11只, 其中至少有兩只恰好是配對的.例

5、3. 從整數(shù)1,2,…,100中人選51個數(shù), 證明在所選的數(shù)中間必然存在兩個整數(shù), 其中之一可以被另一個整除.證明 對于任何一個整數(shù)x, 總可以把x寫成x=2n?a形式, 其中a是奇數(shù), n?0.,,,8,1到100之間一共有50個奇數(shù), 由所選的51個數(shù)利用上述方式可以得到51個奇數(shù), 其中必然有兩個相同, 設這兩個數(shù)為: x=2ra, y=2sa, 如果r?s, 那么x|y; 如果r>s, 那么y|x. 本例中: 鴿子=

6、去掉2因子得到的奇數(shù); 鴿巢=1到100之間奇數(shù).這個例子可以推廣到從1,2,…,2n中任意取n+1個數(shù), 其中必然存在兩個數(shù), 其中一個整除另外一個, 證法類似.,,,9,例4. 在一個邊長為1的正三角形中任意取5個點, 必然有兩個點之間距離不超過1/2. 在邊長為1的正六邊形中, 任意選取7個點, 必然有兩個點之間的距離不超過1.只要通過畫圖, 找出相應的鴿子和鴿巢 就可以解決問題

7、.利用鴿巢原理解決問題的關鍵在于: 辨認問題, 建立鴿巢, 尋找鴿子.,,,10,III.一般形式鴿巢原理,定理2 設m1,m2,?,mn均為正整數(shù),如果有m1+m2+?+mn-n+1只鴿子飛回n個鴿巢,則或者第1個鴿巢至少有m1只鴿子,或者第2個鴿巢至少有m2只鴿子,?,或者第n個鴿巢至少有mn只鴿子.證明 用反證法. 假若第1鴿巢少于m1只鴿子, 第2鴿巢少于m2個鴿子, …, 第n鴿巢少于mn只鴿子, 則鴿子

8、總數(shù)至多為: (m1-1)+(m2-1)+…+(mn-1) =m1+m2+…+mn-n,這比假定的鴿子數(shù)少了一個, 矛盾. ?,11,從定理2可得出以下推論：推論1 如果m1=m2=?=mn=r, 若將n(r-1)+1個球放入n個盒子中, 則至少有一個盒子含有不少于r個球.推論2 如果n個正整數(shù)m1,m2,?,mn的平均數(shù)(m1+m2+?+mn)/n>r-1,則m1,m2, ?,mn中至少有一個正整數(shù)不會小于r.推

9、論3 有m個球放入n個盒子,則至少有一個盒子中有不少于[(m-1)/n]+1個球.,,,,12,例5. 隨意給一個正十邊形的10個頂點標上號碼1,2,…,10, 求證: 必然有一個頂點, 該頂點及與之相鄰的兩個頂點的標號之和不小于17. 證明 設v1,v2,…,v10是正十邊形的10個頂點, ai表示頂點vi及與vi相鄰的兩個頂點標號之和, 則 a1+a2+…+a10=(1+2+…+10)?3

10、 =165>(17-1) ? 10+1 這樣必然有某個ak?17. ?,,,13,定理3 (Erdös)由n2+1個不同實數(shù)構成的序列中, 至少存在由n+1個實數(shù)組成一個單調(diào)遞增子序列或單調(diào)遞減子序列.證 設原序列為:,,令mi表示從ai開始最長遞增子序列的長度. 若有某個mi?n+1,則定理得證. 因為給定的序列有n

11、2+1個實數(shù), 故可產(chǎn)生n2+1個長度:,,,14,如果全部的mi<n+1, 則這些整數(shù)必定在1到n之間, 相當于把n2+1個球放入n個盒子.由定理2的推論1可知, 這是r=n+1的特殊情況, 這n2+1個mi中至少有n+1個數(shù)相等.不妨設,,且1?i1<i2<?<in+1?n2+1, 則可以得到下面的長度為n+1的遞減序列:,,,?,15,IV. Ramsey數(shù),在引出Ramsey數(shù)之前,先給出幾個

12、引理.引理1 若集合S由6個人組成, 那么S中或者存在至少3個人互相認識,或者存在至少3個人互不認識.證明 在6個人中, 任意固定一個人A, 則其余的5人可以分成兩部分, 一部分是由與A認識的人組成的F, 另外一部分是由與A不認識的人組成的T, 由鴿巢原理, 這兩部分至少有一部分含有3個人.,,,16,|F|=3. 這時候, 如果F中3個人都互相不認識, 自然命題得證; 如果其中至少有2個人互相認識, 則這兩個人與A一起組成

13、互相認識的3個人.|T|=3. 如果T中3個人互相認識, 命題得證; 如果其中至少有2個人互相不認識, 再添加上A即可得三個互相不認識的人.,,,引理可以敘述為: 如果對一個6個頂點的完全圖的邊用紅、藍兩種顏色去染色, 則一定存在一個單色的三角行.,17,引理2 若集合S由10人組成, 那么S中存在至少4個人互相認識, 或存在至少3個人互不認識.證明 在這10個人當中任意固定一個人A, 則其余人可以分成兩類：,圖1,1

14、8,,F：與A相互認識的人的集合 T: 與A相互不認識的人的集合 由鴿巢原理, 至少有一類含有不少于5個的人. 證明可以分情況得到.若|T| ? 3, 則|F| ? 6, 由引理2, F中有3個互相認識的或者互相不認識的. 如果有3個互相不認識的, 引理得證; 如果有3個互相認識的, 再加上A就是4個互相認識的, 引理成立.,19,,(2) 若|T| ? 4, 如果T中所有人都是互相認識的, 引理得證; 如

15、果T中至少有兩個人互相不認識, 再加上A就是3個互相不認識的, 引理也成立. ?類似方法可以證明: 引理3 由10人組成的集合中或者有4人互不認識, 或者至少有3人互相認識.引理4 由20人組成集合中或者有4人互相認識, 或者有4人互不認識.,20,,定義1 設p, q是任意給定的正整數(shù),而且p ?2, q?2. 如果存在一個最小的正整數(shù)R, 使得任意R個人組成的集

16、合S, 下面兩件事中有一件必然成立：(1) S中至少有p個人互相認識；(2) S中至少有q個人互相不認識; 則稱R是具有參數(shù)p, q; 2的Ramsey數(shù),并記作R(p,q; 2), 可省略2, 而簡記作R(p,q).這里我們采用了一個通俗的定義.,21,由引理1, R(3,3)=6. 關于Ramsey數(shù)的幾點注釋：(1) Ramsey數(shù)可以用完全圖邊的2-染色來解釋. 用Kn來表示n階完全圖, 顯然Kn共有

17、 n(n-1)/2條邊.如果用r (r ? 2) 種顏色去染Kn的邊, 每 條邊染一種顏色, 所得到的每條邊都染 了色的Kn稱為r-染色Kn. 可以用頂點表示人, 邊色表示關系.,22,R(p,q)=n?Kn的任意紅、藍染色必然出現(xiàn)紅色Kp, 或者藍色的Kq, 但是Kn-1不具備這樣的性質(zhì). (2) Ramsey數(shù)也可以用圖中的獨立集和團來解釋. R(p,q)=n?任意n個頂點的圖包含Kp 或者有一個q個點

18、的獨立集, 但是存在不具備這樣的性質(zhì)的n-1階圖. 這時候可以理解為互相認識的人連邊, 互相不認識的不連邊.,23,Ramsey數(shù)的決定非常非常困難. 要得到R(p,q)=n, 須完成下面兩步: (a) Kn的任意(紅,藍)-染色必然有紅色Kp或藍色Kq;(b) 構造Kn-1的一個(紅,藍)-染色, 使得其中既沒有紅色Kp也沒有藍色Kq.下面的表格給出目前已知的部分結果, 完全的結果可以見: http://mathwo

19、rld.wolfram/RamseyNumber.html,24,25,V. Ramsey數(shù)的性質(zhì),定理4 Ramsey數(shù)具下列簡單性質(zhì):(1) R(p, q)= R(q, p)(2) R(p, 2)= p, R(2,q)=q(3) R(p,q;1)= p+q-1證明 (1), (2)結論明顯. (3) p+q-1=p+q-2+1, 利用鴿巢原理, 元素為p+q-1的集合的任意2-劃分, 要么第1個集合含有不少于p個元

20、素, 要么第2個集合中含有不少于q個元素.,26,定理5 設p, q 都是大于2的正整數(shù), 則 R(p,q)?R(p-1,q)+R(p,q-1).證明 令R(p-1,q)+R(p,q-1)=n. 在n個人中間, 任意固定一個人A, 其余n-1個人可以分成兩類: F: 與A相互認識的人的集合; T: 與A互相不認識的人的集合.由于n-1=R(p-1,q)+R(p,q-1)-1, 由

21、鴿巢原理, |F|? R(p-1,q)或者|T|? R(p,q-1).,27,(1) |F|? R(p-1,q). 此時由R(p-1,q)的定義, F中或者有p-1個人互相認識, 加上A就得到p個互相認識的人; 或者有q個人互相不認識. (2) |T|? R(p,q-1). 此時由R(p,q-1)的定義, T中或者有p個人互相認識; 或者有q-1個互相不認識的, 再加上A就得到q個互相認識的人.因此任意n個人中間一定有p

22、個互相認識, 或者有q個人互相不認識. ?,28,定理6 設p, q都是大于2的正整數(shù), 當R(p-1,q)和R(p,q-1)都是偶數(shù)時, 有 R(p, q)?R(p-1, q)+R(p, q-1)-1. 推論1 R(3,4)=9.證明 因為R(2,4)=4, R(3,3)=6, 所以由定理6, 有R(3,4)?R(2,4)+R(3,3)-1=4+6-1=9.由下圖中構造一個(紅,藍)-著色K8不含有

23、藍色K3也不含有紅色K4. R(3,4)>8, 從而可得R(3,4)=9.,29,30,推論2 R(3,5)=14.證明 因為R(2,5)=5, R(3,4)=9, 由定理5, R(3,5)?R(2,5)+R(3,4)=5+9=14. 然后構造一個紅、藍染色的K13, 其中沒有紅色的K3, 也沒有藍色的K5. (圖略)推論3 設p, q是大于1的正整數(shù), 則,,[證明: 利用定理5對

24、p+q作歸納. ],31,VI*. Ramsey定理,Ramsey定理就是證明Ramsey數(shù)的存在性, 是由英國青年數(shù)學家F. P. Ramsey從鴿巢原理出發(fā), 于1928年給出的一個重要定理, 因此把它稱為Ramsey定理.Ramsey定理 設p1,p2,?,pn,t是正整數(shù),且p1?t, p2?t, ?,pn?t, 那么存在一個最小的正整數(shù)R(p1,p2,?,pn;t), 它僅依賴于p1,p2, ?,pn和t,并具有

25、下面性質(zhì):,,32,如果S是m個元素的集合:當m?R(p1,p2,?,pn;t)時, 把S的t元子集分布在n個盒子中, 那么或者有p1個元素使它們的全部t元子集都分布在第一個盒子中, 或者有p2個元素使它們的全部t元子集分布在第二個盒子中,?, 或者第n個盒子中有pn個元素使它們的全部t元子集分布在第n個盒子中.,,33,上述定理中的R(p1,p2,?,pn; t)稱為推廣的Ramsey數(shù). 當t=1時,定理必定存在一個最

26、小的正整數(shù)R(p1,p2,?,pn;1), 并具有如下性質(zhì)： 如果m? R(p1,p2,?,pn;1), 將一個m元 集合S的元素分布在n個盒子中,那么或者第一個盒子含有p1個元素, 或者第二個盒子含有p2個元素,?,或者第n個盒子含有pn個元素.這正是鴿巢原理的推廣形式: R(p1,p2,?,pn;1)=(p1+p2+?+pn)-n+1,,34,下面這種特殊形式有時候更有用.推論2 對于任意給定的三個正整數(shù)

27、p, q, r(p?r, q?r), 總存在一個僅依賴p,q,r的最小正整數(shù)R(p,q;r). 當有限集合S的元素個數(shù)N? R(p,q;r)時, 對于Tr(S)的任意一個2-劃分: Tr(S)=??? ( ???=? ), 則S有一個p元子集, 其一切r元子集都屬于?, 或者S有一個q元子集其一切r元子集都屬于?.,,35,例6 證明: R(3,3,3;2)=17.證 設完全圖K17的頂點集為{v1,v2, ?,v17},其邊用紅

28、、藍、黃三色任意著色. 任取一點v1, 則與v1相關聯(lián)的邊至少有6條邊是同色的,不妨記為(v1,v2), (v1,v3), (v1,v4), (v1,v5), (v1,v6), (v1,v7)這6條邊是紅色的. 考慮v2,v3,v4, v5, v6,v7這六個點組成的完全子圖K6, 它共有C(6,2)=15條邊, 其中只要有一條紅色邊,這條紅色邊的兩端點加上v1就成了紅邊的K3子圖, 結論成立.,,36,若這15條邊中無紅

29、色, 則6點完全子圖的 邊用藍、黃兩色任意著色, 由R(3,3)=6可 知, 或者有藍色的K3,或者有黃色的K3,故 結論成立. 因此, R(3,3,3;2)?17. 當有16個頂點的完全圖K16用紅、藍、 黃三色著色時, 存在一種著色方法,可使 K16中不出現(xiàn)同色K3子圖, 可以自己試一 試. 這說明R(3,3,3;2)>16, 故有R(3,3,3;2)=17.,,37,VII*. Ra

30、msey定理的應用,Schur定理: 設t(t?2)是任意給定的自然數(shù), 則必存在自然數(shù)N, 當n?N時, 對集合S={1,2,?,n}的任一個t-分劃 S=?1??2????t, 必存在某個自然數(shù)i(1?i?t), 使得?i含有 兩個自然數(shù)x和y滿足x+y??i.[證明: N=R(3,3,…,3;2), 其中有t個3.],38,Erdös和Sjekeres定理: 設m

31、(m?3)為任一個正整數(shù), 則必存在正整數(shù)N, 當n?N時, 平面上無3點共線的任意n個點中, 必有m個點可以成為一個凸m邊形的頂點. 這個定理主要應用如下兩個引理來證 明. 我們不給出證明, 但介紹一下引理.引理A 平面上無3點共線的任意5個點中, 必有4個點可以構成凸四邊形.,,39,引理B 設平面上有m(m?4)個點, 這m個點中無3點共線且每4個點都可構成凸四邊形, 則這m個點可構成凸m邊形. 可以利用