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

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

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

5.1抽屜原理

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

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

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

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

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

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

與假設(shè)矛盾.

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

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

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

則至少存在一個(gè)qi,滿足qi≥r.

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

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

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

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

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

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

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

圖5.1.1抽屜的選擇

5.2應(yīng)用

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

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

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

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

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

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

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

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

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

=aimod3,則ri

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

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

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

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

(1)若有某3個(gè)ri

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

(2)否則,5個(gè)ri

中最多有2個(gè)ri

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定理5.2.1(極端原理):

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

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

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

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

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

最短長(zhǎng)度原理2在連接一個(gè)已知點(diǎn)與某個(gè)已知直線或已知平面上的點(diǎn)的所有線段中,以垂線段的長(zhǎng)度為最短.

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

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

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

是顯然的,除非有

但上式一旦成立,就必有

矛盾,故命題得證.

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

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

5.3Ramsey問(wèn)題

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

5.3.1完全圖的染色問(wèn)題

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

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

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

5.3.2Ramsey問(wèn)題

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

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

5.3.3問(wèn)題的一般化

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

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

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

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

5.4Ramsey數(shù)

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

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

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

將染色問(wèn)題可以推廣到一般情形.

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

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

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

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

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

推論5.4.1下式成立:

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

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

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

證把這5個(gè)點(diǎn)之間都連上線可得10條直線段