組合數(shù)學(xué)講義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、rld.wolfram/RamseyNumber.html,24,25,V. Ramsey數(shù)的性質(zhì),定理4 Ramsey數(shù)具下列簡(jiǎn)單性質(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)結(jié)論明顯. (3) p+q-1=p+q-2+1, 利用鴿巢原理, 元素為p+q-1的集合的任意2-劃分, 要么第1個(gè)集合含有不少于p個(gè)元

20、素, 要么第2個(gè)集合中含有不少于q個(gè)元素.,26,定理5 設(shè)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個(gè)人中間, 任意固定一個(gè)人A, 其余n-1個(gè)人可以分成兩類: F: 與A相互認(rèn)識(shí)的人的集合; T: 與A互相不認(rèn)識(shí)的人的集合.由于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). 此時(shí)由R(p-1,q)的定義, F中或者有p-1個(gè)人互相認(rèn)識(shí), 加上A就得到p個(gè)互相認(rèn)識(shí)的人; 或者有q個(gè)人互相不認(rèn)識(shí). (2) |T|? R(p,q-1). 此時(shí)由R(p,q-1)的定義, T中或者有p個(gè)人互相認(rèn)識(shí); 或者有q-1個(gè)互相不認(rèn)識(shí)的, 再加上A就得到q個(gè)互相認(rèn)識(shí)的人.因此任意n個(gè)人中間一定有p

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

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

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

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

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

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

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

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

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

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