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

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

5.1抽屜原理

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

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

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

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

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

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

與假設矛盾.

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

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

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

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

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

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

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

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

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

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

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

圖5.1.1抽屜的選擇

5.2應用

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

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

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

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

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

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

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

問題二任給n個整數,其中必存在3個整數,其和能被3整除.問n最小應為多少.

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

=aimod3,則ri

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

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

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

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

(1)若有某3個ri

相同,則對應的3個ai滿足條件;

(2)否則,5個ri

中最多有2個ri

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

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

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

問題三任給n個整數,其中必存在k個整數,其和能被k整除.問n最小應為多少.

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

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

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

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

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

而當n=9時,可分為兩種情形討論:

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

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

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

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

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

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

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

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

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

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

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

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

定理5.2.1(極端原理):

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

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

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

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

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

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

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

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

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

是顯然的,除非有

但上式一旦成立,就必有

矛盾,故命題得證.

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

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

5.3Ramsey問題

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

5.3.1完全圖的染色問題

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

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

問題二1959年,《美國數學月刊》又進一步提出:“任意18個人的集會上,一定有4人或互相認識,或互不認識”.

5.3.2Ramsey問題

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

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

5.3.3問題的一般化

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

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

定理5.3.1對K9涂以紅藍兩色,必定會出現一個同色的K3或同色K4.

圖5.3.2既無紅色K3又無藍色K4的八邊形染色方案

5.4Ramsey數

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

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

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

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

5.4.1Ramsey數的性質

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

(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)當p、q≥2時,有r(p,q)≤r(p,q-1)+r(p-1,q);若r(p,q-1)和r(p-1,q)都為偶數,不等式嚴格成立.

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

5.4.2Ramsey數的推廣

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

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

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

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

【例5.4.3】有17位學者,每人給其他人各寫一封信,討論三個問題中的某一個問題,且兩人之間互相通信討論的是同一個問題.證明至少有三位學者,他們之間通信討論的是同一問題(1964年第六屆國際奧林匹克數學比賽題目).此問題等價于對K17的每條邊涂以紅、藍、黃三色之一(即邊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數的應用

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

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

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