組合數(shù)學(xué)（第二版）抽屜原理和瑞姆賽(Ramsey)理論

抽屜原理和瑞姆賽(Ramsey)理論5.1抽屜原理5.2應(yīng)用5.3Ramsey問題5.4Ramsey數(shù)

抽屜原理又稱鴿巢原理或重疊原理,是組合數(shù)學(xué)中兩大基本原理之一,是一個極其初等而又應(yīng)用較廣的數(shù)學(xué)原理.其道理并無深奧之處,且正確性也很明顯.但若能靈活運用,便可能得到一些意料不到的結(jié)果.

5.1抽屜原理

定理5.1.1(基本形式)將n+1個物品放入n個抽屜,則至少有一個抽屜中的物品數(shù)不少于兩個.

證反證之.將抽屜編號為:1,2,…,n,設(shè)第i個抽屜放有qi個物品,則

【例5.1.1】一年365天,今有366人,那么,其中至少有兩人在同一天過生日.

【例5.1.2】箱子中放有10雙手套,從中隨意取出11只,則至少有兩只是完整配對的.

定理5.1.2(推廣形式)將q1+q2+…+qn-n+1個物品放入n個抽屜,則下列事件至少有一個成立:即第i個抽屜的物品數(shù)不少于qi個,i=1,2,…,n.

證反證.不然,設(shè)第i個抽屜的物品數(shù)小于qi(i=1,2,…,n)(即該抽屜最多有qi-1個物品),則有

與假設(shè)矛盾.

推論5.1.1將n(r-1)+1個物品放入n個抽屜,則至少有一個抽屜中的物品個數(shù)不少于r個.

推論5.1.2將m個物品放入n個抽屜,則至少有一個抽屜中的物品個數(shù)不少于其中[x]表示取正數(shù)x的整數(shù)部分,[x]表示不小于x的最小整數(shù).

推論5.1.3若n個正整數(shù)qi(i=1,2,…,n)滿足

則至少存在一個qi,滿足qi≥r.

【例5.1.3】有n位代表參加會議,若每位代表至少認(rèn)識另外一個代表,則會議上至少有兩個人,他們認(rèn)識的人數(shù)相同.

證設(shè)某代表認(rèn)識的人數(shù)為k個,則k∈{1,2,…,n-1}(視為n-1個抽屜).而會議上有n個代表,故每位代表認(rèn)識的人數(shù)共為n個數(shù)(視為n個物品).那么,由基本定理,結(jié)論成立.

【例5.1.4】任意一群人中,必有兩人有相同數(shù)目的朋友.

證設(shè)有n個人(n≥2),分三種情形討論:

(1)每人都有朋友,由例5.1.3即知結(jié)論成立;

(2)只有一人無朋友,余下的n-1人都有朋友,由(1)知此n-1人中必有兩人有相同數(shù)目的朋友;

(3)有兩人或兩人以上的人無朋友,則朋友數(shù)為零的人已經(jīng)有兩個了,同樣滿足條件.

圖5.1.1抽屜的選擇

5.2應(yīng)用

【例5.2.1】任意三個整數(shù),必有兩個之和為偶數(shù)(其差也為偶數(shù)).

證制造兩個抽屜:“奇數(shù)”和“偶數(shù)”,3個數(shù)放入兩個抽屜,必有一個抽屜中至少有兩個數(shù),由整數(shù)求和的奇、偶性質(zhì)即知此二數(shù)之和必為偶數(shù).同理可知,二者之差也為偶數(shù).

問題一任給3個整數(shù),其中必存在兩個整數(shù),其和能被2整除.

證明此問題是上例的另一種提法,目的是為了便于問題的推廣.記這3個數(shù)為a1,a2,a3,令ri≡aimod2,則ri=0,1(i=1,2,3),其中,符號“≡”表示模運算.將可能出現(xiàn)的余數(shù)值0,1視為兩個抽屜,3個數(shù)ai

看作物品,以ri的值決定將ai

放入哪個抽屜.那么,由抽屜原理,某個抽屜中至少有兩個ai

,其除以2的余數(shù)相同,從而此2數(shù)即滿足要求.

問題二任給n個整數(shù),其中必存在3個整數(shù),其和能被3整除.問n最小應(yīng)為多少.

證明此問題是問題一的擴(kuò)展.按照常規(guī)思路,當(dāng)n=7時結(jié)論成立.即記這7個數(shù)為a1,a2,…,a7(7個物品),并令ri

=aimod3,則ri

=0,1,2(3個抽屜)(i=1,2,…,7).同樣,由抽屜原理知,至少有3個ai,其對應(yīng)的余數(shù)ri

相同,而這3個數(shù)ai即滿足要求.但實際上7并不是最少數(shù)字,而是有n=5個整數(shù)就夠了.

記這5個數(shù)為a1,a2,…,a5,令ri=aimod3,則ri

=0,1,2(i=1,2,…,5)(構(gòu)造抽屜和物品的方法同上).那么,可分兩種情況討論問題:

(1)若有某3個ri

相同,則對應(yīng)的3個ai滿足條件;

(2)否則,5個ri

中最多有2個ri

相同(即每個抽屜中最多放2個物品),此時,每個抽屜必不空.那么,從每個抽屜中選一個整數(shù),該3個數(shù)也滿足條件.

若n=4,則結(jié)論不一定成立.例如,選

就找不到3個數(shù)滿足要求.所以必有n=5.

問題三任給n個整數(shù),其中必存在k個整數(shù),其和能被k整除.問n最小應(yīng)為多少.

這是問題的一般提法.例如:k=2時,n=3;k=3時,n=5(而非7);k=4時,n=7(請讀者自己證明).

從幾何角度,可以將問題一、二重新描述如下:

設(shè)一維數(shù)軸上有3個整點(指坐標(biāo)為整數(shù)的點),則其中必存在兩個點xi和xj,其幾何中心(xi+xj)/2也是一個整點.當(dāng)點數(shù)增到5個時,必存在3個點xi、xj

和xk,其幾何中心(xi+xj+xk)/3也是一個整點,而且整點的個數(shù)最少為5.

上述這些例子,都相當(dāng)于在一維空間上討論問題.這些例子也可以推廣到更一般的情形,即多維空間.

而當(dāng)n=9時,可分為兩種情形討論:

(1)若某個抽屜中至少含有3個點,則選此種類型的3個點即可.

(2)否則,每個抽屜中最多有兩個點.但此時至少存在某一行,或某一列,或不同行不同列的3個抽屜,其中不空.那么,按照前述推理,從此3個抽屜中各選一點,即達(dá)目的.由本例可以看出,在證明存在性問題的過程中,即使是完全一樣的一個問題,只要問題的規(guī)模發(fā)生變化,哪怕是增加1,證明問題的思路都可能與前不同.也就是說,小規(guī)模時的方法解決不了問題,還需要人們重新考慮解決問題的新辦法.對這樣的一類問題,也只能在規(guī)模上做到有限解決.這也從一個方面反映了本章在學(xué)習(xí)、理解過程中的難度.尤其是下面的兩節(jié),問題將暴露得更為突出.

【例5.2.5】將65個正整數(shù)1,2,…,65隨意分為4組,那么,至少有一組,該組中最少存在一個數(shù),是同組中某兩數(shù)之和或另一數(shù)的兩倍.

證用反證法.設(shè)任何一組數(shù)中的每一個數(shù),它既不等于同組中另外兩數(shù)之和,也不等于同組中另一數(shù)的兩倍.即任何一組數(shù)中任意兩個數(shù)之差總不在這個組中.

【例5.2.6】由mn+1個不同實數(shù)構(gòu)成的序列{ai|i=1,2,…,mn+1}中必存在一個(m+1)項的遞增子序列或(n+1)項的遞減子序列.

證某個序列{bn|n=1,2,…,n}是遞增的,是指該序列滿足:b1<b2<…<bn;反之,若b1>b2>…>bn,則稱其是遞減的.

【例5.2.7】證明:對任意正整數(shù)n,必存在僅由數(shù)字0、3和7組成的正整數(shù),該正整數(shù)能被n整除.

【例5.2.8】已知402個集合,每個集合都恰有20個元素,其中每兩個集合都恰有一個公共元素.求這402個集合的并集所含元素的個數(shù).

【例5.2.9】將上下兩個同心而且同樣大小的圓盤A、B各自劃分成200個全等的扇形,在A盤上任取100個扇形涂上紅色,其余100個扇形涂上藍(lán)色,而B盤上的200個扇形任意地涂上紅色或藍(lán)色.證明,總可適當(dāng)?shù)剞D(zhuǎn)動兩圓盤到某個位置,當(dāng)上下的扇形互相重合時,兩圓盤上至少有100對具有相同顏色的扇形重疊在一起.

證定義兩圓盤的扇形對齊時為一種重疊格局,由于每個圓盤都分為200個扇形,故當(dāng)其中一個圓盤轉(zhuǎn)動時,可能出現(xiàn)的重疊格局有200個.對這200個格局計算同色扇形重疊的對數(shù).由于A盤上紅、藍(lán)扇形各100個,因此,B盤上每個扇形(或紅色或藍(lán)色)在這200個格局里與A盤上的同色扇形各重疊100次.對B盤的每個扇形統(tǒng)計,在這200個格局中B盤的200個扇形與A盤同色扇形重疊在一起共100×200=20000對.因此可計算出每一格局中同色扇形重疊的平均對數(shù)為20000÷200=100.因此至少有一格局中同色扇形重疊的至少有100對.

【例5.2.10】某俱樂部有3n+1名成員.對每一個人,其余的人中恰好有n個愿與他打網(wǎng)球,n個愿與他下象棋,n個愿與他打乒乓球.證明該俱樂部至少有3個人,他們之間玩的游戲三種俱全.

證將每個人作為平面上的一個點,且任何3點不共線.由每一點引出n條紅邊、n條藍(lán)邊、n條黑邊,分別代表打網(wǎng)球、下象棋及打乒乓球.問題等價于要證明圖中至少有一個三邊顏色全不相同的三角形.

定理5.2.1(極端原理):

最小數(shù)原理1在有限個實數(shù)組成的集合中,必存在最小的數(shù).

最小數(shù)原理2設(shè)N是自然數(shù)全體組成的集合,若M是N的非空子集,則M中必有最小的數(shù).

最大數(shù)原理1在有限個實數(shù)組成的集合中,必存在最大的數(shù).

最大數(shù)原理2在由負(fù)整數(shù)組成的集合(有限或無限)中必存在最大的負(fù)整數(shù).

最短長度原理1任意給定相異兩點,所有連接這兩點的線中,以直線段的長度為最短.

最短長度原理2在連接一個已知點與某個已知直線或已知平面上的點的所有線段中,以垂線段的長度為最短.

【例5.2.11】某次體育比賽,每兩名選手賽一場,每場比賽一定決出勝負(fù).通過比賽確定優(yōu)秀選手.選手A為優(yōu)秀選手的條件是:對任何選手B,或者A勝B,或者A間接勝B.所謂間接勝B,是指存在選手C,使得A勝C而C勝B.假定按上述規(guī)則確定的優(yōu)秀選手只有一名,求證這名選手全勝所有其他選手.

【例5.2.13】求證:在四面體ABCD中,必有某個頂點,把從它引出的三條棱當(dāng)作邊,這三條邊可以構(gòu)成一個三角形.

證首先,已知三條線段能構(gòu)成一個三角形的充分必要條件是任何兩線段長度之和大于第三條邊的長度.其次,由最大數(shù)原理1知,在四面體ABCD的4條棱中必存在最長的棱.設(shè)AB為最長棱之一,則A、B兩點中至少有一點,以此點為端點的3條棱的長度滿足構(gòu)成三角形的條件.若不然,由于AB是最長棱,故以A為端點的3條棱AB、AC、AD和以B為端點的3條棱BA、BC、BD分別滿足

是顯然的,除非有

但上式一旦成立,就必有

矛盾,故命題得證.

上邊用到AC+BC>AB,AD+BD>AB,也是顯然的,因為A、B、C這3個點組成四面體的一個側(cè)面,并形成△ABC.同理,A、B、D也在一個側(cè)面上形成△ABD(見圖5.2.1).圖5.2.1四面體

【例5.2.14】平面上放了有限多個圓,它們蓋住的面積為1.試證:一定可以從這組圓中去掉若干個圓,使得余下的圓互不相交,而且它們可蓋住的面積不小于1/9.

5.3Ramsey問題

Ramsey理論起始于20世紀(jì)20年代末30年代初,最初由英國數(shù)學(xué)家F.P.Ramsey提出.其思想已日益被人們理解、接受并得到了一定的發(fā)展.Ramsey定理是抽屜原理的推廣,也叫廣義抽屜原理.

5.3.1完全圖的染色問題

設(shè)平面上有n個點,任何三點都不共線,將這些點兩兩之間連一線段,構(gòu)成的圖形稱為完全圖,記為Kn.

問題一證明任意6個人的集會上,總有3人互相認(rèn)識或互相不認(rèn)識(1947年匈牙利數(shù)學(xué)競賽試題,后被收入1958年的《美國數(shù)學(xué)月刊》第5、6期中).

問題二1959年,《美國數(shù)學(xué)月刊》又進(jìn)一步提出:“任意18個人的集會上,一定有4人或互相認(rèn)識,或互不認(rèn)識”.

5.3.2Ramsey問題

提法一經(jīng)觀察,在6個或6個以上的人群中,必有3人互相認(rèn)識,或有3人,彼此根本不認(rèn)識.而將人數(shù)降到5個或更少時,此有趣現(xiàn)象就可能消失.于是6成為具有這一特性的最少人數(shù).

提法二當(dāng)n≥6時,若對Kn的每一條邊隨意涂以紅、藍(lán)兩色之一,那么,Kn上至少可以找出一個同色K3.而當(dāng)n≤5時,至少可以給出一種涂法,使得Kn上不存在同色K3.如圖5.3.1所示,當(dāng)n=5時,按照圖中的涂法,是不存在同色K3的(其中用實線表示紅線,虛線表示藍(lán)線,下同).圖5.3.1無同色K3的五邊形染色方案

5.3.3問題的一般化

引理5.3.1若將K9涂以紅藍(lán)兩色,則必存在一個頂點,從此點引出的8條線段中,同色的線段或多于3條,或少于3條.

證明用反證法.假如不存在這樣的頂點,即從每一頂點發(fā)出的線段中,紅色(藍(lán)色)線段都是3條,現(xiàn)在對9個頂點逐點統(tǒng)計由它們發(fā)出的紅色(藍(lán)色)線段的條數(shù),應(yīng)為27.另一方面,設(shè)K9中實有紅色(藍(lán)色)線段共m條,現(xiàn)在對這m條邊的每個端點逐點統(tǒng)計由它們發(fā)出的紅色(藍(lán)色)線段的條數(shù),由于每條線段有兩個端點,故應(yīng)為2m.于是得出2m=27,這是不可能的.引理得證.

定理5.3.1對K9涂以紅藍(lán)兩色,必定會出現(xiàn)一個同色的K3或同色K4.

圖5.3.2既無紅色K3又無藍(lán)色K4的八邊形染色方案

5.4Ramsey數(shù)

定義5.4.1滿足上述條件的數(shù)r稱為Ramsey數(shù),記為r(p,q;2),簡記為r(p,q)

【例5.4.1】證明r(4,4)=18.

證設(shè)v0,v1,v2,…,v17是完全圖K18的頂點,現(xiàn)考察K18中從v0出發(fā)的17條線段.它們分成了紅、藍(lán)兩類,由抽屜原理可知:至少有9條是同色的,不妨設(shè)它們?yōu)榧t色(藍(lán)色).進(jìn)一步再來考察這9條紅色(藍(lán)色)線段里,異于v0的9個端點所構(gòu)成的K9,其中一定會出現(xiàn)一個紅色(藍(lán)色)K3,或一個藍(lán)色(紅色)K4.若是前者,則這個紅色(藍(lán)色)K3的三個頂點和v0一起便構(gòu)成一個紅色(藍(lán)色)K4,若是后者,則本身已存在藍(lán)色(紅色)K4.

由此可知,r(4,4)≤18,下面證r(4,4)>17,從而有r(4,4)=18

5.4.1Ramsey數(shù)的性質(zhì)

定理5.4.1Ramsey數(shù)r(p,q;2)具有以下性質(zhì):

(1)r(p,q)=r(q,p);

(2)r(1,q)=r(p,1)=1;

(3)r(2,q)=q,r(p,2)=p;

(4)當(dāng)p、q≥2時,有r(p,q)≤r(p,q-1)+r(p-1,q);若r(p,q-1)和r(p-1,q)都為偶數(shù),不等式嚴(yán)格成立.

例5.4.2證明r(3,5)=14.

5.4.2Ramsey數(shù)的推廣

將染色問題可以推廣到一般情形.

(1)增加顏色數(shù):設(shè)有n個頂點的平面完全圖Kn,用m種顏色c1,c2,…,cm隨意給Kn的邊著色.那么,對于給定的正整數(shù)p1,p2,…,pm(pi≥2,i=1,2,…,m),是否存在最小的正整數(shù)r(p1,p2,…,pm;2),當(dāng)n≥r(p1,p2,…,pm;2)時,在Kn中一定含有某個Kpi,它的所有邊都為顏色ci.

(2)擴(kuò)大空間的維數(shù):設(shè)Kn為k維空間上的具有n個頂點的完全圖,對同樣的問題,是否也存在r(p1,p2,…,pm;2)?

定理5.4.3廣義Ramsey數(shù)r(p1,p2,…,pm;k)是存在的.

【例5.4.3】有17位學(xué)者,每人給其他人各寫一封信,討論三個問題中的某一個問題,且兩人之間互相通信討論的是同一個問題.證明至少有三位學(xué)者,他們之間通信討論的是同一問題(1964年第六屆國際奧林匹克數(shù)學(xué)比賽題目).此問題等價于對K17的每條邊涂以紅、藍(lán)、黃三色之一(即邊3著色),其中必存在同色K3.由此可知,r(3,3,3;2)≤17.

【例5.4.4】證明r(3,3,3;2)>16,即對于K16,存在一種邊3著色方案,使得其中不存在同色K3.

推論5.4.1下式成立:

5.4.3Ramsey數(shù)的應(yīng)用

【例5.4.5】(凸多邊形問題)設(shè)m是大于或等于3的整數(shù),則存在正整數(shù)N,使得當(dāng)n≥N時,在平面上任何3點都不共線的n個點中,必有m個點是凸m邊形的頂點.為證明這個命題,需要兩條引理.

引理5.4.1若平面上有任何3點都不共線的5個點,則其中必有4點是凸四邊形的頂點.

證把這5個點之間都連上線可得10條直線段