組合數(shù)學(xué)課件制作授課：王繼順

2013.9.3第2章 小結(jié)（1）本章小結(jié)本章討論了鴿籠原理及其推廣，

Ramsey

數(shù)及其性質(zhì)，

Ramsey

定理以及一些有趣的應(yīng)用。鴿籠原理是重要的組合基本原理之一。重點(diǎn)是：（1）鴿籠原理的正確使用。這是需要一定的技巧的，關(guān)鍵在于認(rèn)清“鴿子”（放進(jìn)盒子的物體）并制造“鴿籠”。而制造“鴿籠”的依據(jù)是：“待證命題成立，蘊(yùn)涵有兩只鴿子在同一鴿（籠2”）。鴿籠原理的加強(qiáng)形式有多種說(shuō)法，其中關(guān)于算術(shù)平均的說(shuō)法應(yīng)用尤廣，它告訴我們，當(dāng)m/n＞r時(shí)，若把m

個(gè)物體放入n個(gè)盒子，那么至少有一個(gè)盒子有r+1

個(gè)物體。運(yùn)用它解題的關(guān)

鍵仍然是正確的設(shè)置“盒子”。第2章 小結(jié)（3）本章小結(jié)（3）

Ramsey

定理，Ramsey

數(shù)Ramsey定理的性質(zhì)可以概述為“任何一個(gè)足夠大的結(jié)構(gòu)中必定包含有一個(gè)給定大小的規(guī)則子結(jié)構(gòu)”。在解有關(guān)Ramsey

定理及其應(yīng)用的問(wèn)題時(shí)，最重要的是正確理解定理意義，特別是r=2時(shí)定理的幾種形象的說(shuō)法。在解題時(shí)，則要正確地設(shè)計(jì)一個(gè)集合，該集合分成哪幾個(gè)部分，正確的確定a1,a2,…,am

以及r分別體現(xiàn)在哪些已知量或已知事實(shí)中。如果從更高的角度看問(wèn)題，有關(guān)鴿籠原理和Ramsey

定理的應(yīng)用問(wèn)題的解法都是模型化歸方法。即把實(shí)際問(wèn)題化歸到

“鴿子，鴿籠”的模式，化歸到“一個(gè)集合的r?子集分類(lèi)”的模式的方法。鴿巢原理鴿巢原理的簡(jiǎn)單形式若有n+1只鴿子飛到n個(gè)鴿巢里面，則至少有一個(gè)鴿巢里至少有兩只鴿子。注:n+1為結(jié)論成立的最小數(shù)。鴿巢原理的加強(qiáng)形式將q1＋q2＋…＋qn－n＋1個(gè)物品放入n個(gè)抽屜中，則至少存在某個(gè)抽屜i（1≤i≤n）,使得這個(gè)抽屜里至少有qi個(gè)物品。注:q1＋q2＋…＋qn－n＋1為結(jié)論成立的最小數(shù),記為

N(q1,q2,…,qn;1)。即N(q1

,q2,…,qn;1)=q1+q2+…+qn-n+1.顯然,當(dāng)q1=q2=…=qn=2時(shí),加強(qiáng)形式即為簡(jiǎn)單形式。鴿巢原理與Ramsey定理習(xí)題課當(dāng)qi=r時(shí)，得：1

2n足m

1

?m

2?m

3?n不小于r。.?,m則nm??r,m1

,…m,中至少有一個(gè)數(shù)推論1n·r-(1)＋1只鴿子飛入n個(gè)巢里，則至少有一個(gè)鴿巢里至少有r只鴿子。推論2：m只鴿子飛入n個(gè)巢里，則至少有一個(gè)數(shù)。推論3：設(shè)m

1

,m

2

,…m

n均為正整數(shù),且滿(mǎn)鴿巢里至少有?m

只?

鴿子,其中?

??

n

??m

??是n

?不小于的最小整?

?mn2鴿巢的構(gòu)造及其應(yīng)用雖然鴿巢原理十分簡(jiǎn)單明了，但不是所有的問(wèn)題都一眼就可以看出什么是鴿子，什么是鴿巢。在應(yīng)用它的時(shí)候卻涉及很多技巧，這是利用鴿巢原理解題的魅力所在。常用的構(gòu)造鴿巢的方法有：利用整數(shù)分組、余數(shù)分類(lèi)，劃分集合，分割區(qū)間、分割圖形，利用染色等。下面給出幾類(lèi)常用的構(gòu)造鴿巢的方法。2.1

利用整數(shù)分組構(gòu)造“鴿巢”例1試證明從{1，2，…，kn}中選n+1個(gè)數(shù)，總存在2個(gè)數(shù)，它們之間最多相差k-1。證明：把{1，2，…，kn}分為n部分{1，2，3，…,k},{k+1,k+2,…,2k},…,{n(-1)k+1,(n-1)k+2,…,kn},即做n個(gè)鴿巢，從中任選n+1個(gè)數(shù)，由鴿巢原理，必有2個(gè)數(shù)選在同一個(gè)鴿巢中，所以它們的差最大為k-1。例2在一條筆直的馬路上種樹(shù)，從起點(diǎn)起，每隔1米種一棵數(shù)。如果把三塊“愛(ài)護(hù)樹(shù)木”的小牌分別掛在三棵樹(shù)上，那么不管怎么掛，至少有兩棵掛牌的樹(shù)它們之間的距離是偶數(shù)（以米為單位）。解

從起點(diǎn)開(kāi)始給每課樹(shù)編號(hào)，樹(shù)上的號(hào)碼依次為1,2,3,…,n,把這些號(hào)碼分為奇數(shù)和偶數(shù)兩類(lèi)，當(dāng)作兩個(gè)鴿巢，把三塊牌分別掛在三棵樹(shù)上，那么不管怎么掛，這三棵掛牌的樹(shù)至少有兩棵樹(shù)的號(hào)碼同為奇數(shù)或偶數(shù)，而這兩棵樹(shù)的差必為偶數(shù)，所以至少有兩棵掛牌的樹(shù)它們之間的距離是偶數(shù)（以米為單位）。路易·波薩是匈牙利數(shù)學(xué)家,在他11歲時(shí)匈牙利大數(shù)學(xué)家厄杜斯給他出了個(gè)問(wèn)題:“如果你手頭上有n+1個(gè)整數(shù)，這些整數(shù)是小于或等于2n的，那么你一定會(huì)有一對(duì)數(shù)是互素的。你知道這是什么原因嗎？”波薩僅思考了半分鐘就巧妙地回答了這個(gè)問(wèn)題。2.2利用劃分圖形構(gòu)造“鴿巢”例1 邊長(zhǎng)為1的正方形中，任意放入9個(gè)點(diǎn)，求證這9個(gè)點(diǎn)中任取3個(gè)點(diǎn)組成的三角形中，至少有一個(gè)的面積不超過(guò).18GEDF圖1解：將邊長(zhǎng)為1的正方形等分成邊長(zhǎng)為1/2的四個(gè)小正方形，視這四個(gè)正方形為鴿巢，9個(gè)點(diǎn)任意放入這四個(gè)正方形中，由鴿巢原理必有三點(diǎn)落入同一個(gè)正方形內(nèi).現(xiàn)特別取出這個(gè)正方形來(lái)加以討論.把落在這個(gè)正方形中的三點(diǎn)記為D、E、F.如圖1，?

1

12

2? ?

h

?

1

?

1

1

?

h)(2 2

2?

h

1

h

14

8

4

8?

?

?

.通過(guò)這三點(diǎn)中的任意一點(diǎn)（如E）作正方形邊平行線(xiàn)S△DEF

＝S△DEG

＋S△EFG所以，結(jié)論成立。例2 在圓內(nèi)（包刮圓周）有8個(gè)點(diǎn)，則其中必有兩個(gè)點(diǎn)，它們之間的距離小于圓的半徑。證明 分兩種情況考慮。如果8個(gè)點(diǎn)無(wú)一個(gè)在圓心上，可將圓分成7個(gè)相等的扇形，由鴿巢原理，這8個(gè)點(diǎn)至少有兩個(gè)在同一個(gè)扇形內(nèi)，則這兩點(diǎn)之間的距離小于半徑。A

1A

2A

3A

4A

6A

5o2?b

?

2R

sin2.如果8個(gè)點(diǎn)有一個(gè)點(diǎn)在圓心，可將圓分成6個(gè)相等的扇形，如圖，扇形OA

6A

1不包含OA1,由鴿巢原理，余下的7個(gè)點(diǎn)至少有兩個(gè)在同一個(gè)扇形內(nèi)，則這兩點(diǎn)之間的距離小于半徑。由于圓上相鄰兩點(diǎn)Ai,Aj間的弦長(zhǎng)恰好為圓的半徑，所以取扇形OA

1A

2不包含OA

2,扇形OA

2A

3不包含OA

3,…,弦長(zhǎng)：在邊長(zhǎng)為1的正方形內(nèi)任取5個(gè)點(diǎn),則其中至少有兩點(diǎn),它們之間的距離不超過(guò)2

.2證明:在一邊長(zhǎng)為1的三角形中任取10個(gè)點(diǎn),則其中至少有兩點(diǎn),它們之間的距離不超過(guò)1/3.

確定m

n，使得在一邊長(zhǎng)為1的三角形中任取m

n個(gè)點(diǎn),則其中至少有兩點(diǎn),它們之間的距離不超過(guò)1/n.類(lèi)似這樣的問(wèn)題還有不少。2.3

利用余數(shù)分類(lèi)構(gòu)造“鴿巢”例試證明任意給定52個(gè)整數(shù)，它們之中必有2個(gè)數(shù)，其和或差是100的倍數(shù)(即被100整除）。證明：任意一個(gè)整數(shù)a除以100產(chǎn)生的余數(shù)為0，1，2，…99共100種。用a1,a2,…,a52表示這52個(gè)整數(shù)，ai除以100產(chǎn)生的余數(shù)記為ri（

i=1，2，…，52

）。我們現(xiàn)在用0，1，2，…,99這100個(gè)余數(shù)來(lái)構(gòu)造鴿巢，將它們分為51組，構(gòu)造出51個(gè)鴿巢：{0}，{1，99}，{2，

98}},由鴿巢原理，這52個(gè)整數(shù)分別除以100產(chǎn)生的52個(gè)余數(shù)r1,r2,…r52

中必有兩個(gè)余數(shù)落在同一組中，若這兩個(gè)余數(shù)落在{0}或{50}中，則它們的和及差都能被100整除。若這兩個(gè)余數(shù)落在剩下的49組中的一組，當(dāng)余數(shù)相同時(shí)，它們的差被100整除，當(dāng)余數(shù)不同時(shí)，它們的和被100整除，即存在兩個(gè)數(shù)，它們的和或差能被100整除。這個(gè)問(wèn)題的一般提法任意給定n+2個(gè)整數(shù)，它們之中必有2個(gè)數(shù)，其和或差是2n的倍數(shù)。類(lèi)似這樣的例子也有不少。1.任取n+1個(gè)正整數(shù)，求證在這n+1個(gè)數(shù)中必有兩個(gè)數(shù)它們之差被n整除.2.任意給出2011個(gè)正整數(shù)a1,a2

,L,a2011,2011

/(ak?1

?

ak?

2

?

L

?

al).證明必存在正整數(shù)k,l(0??kl?

2011),使得l?

2011),a2011

,證明必存在正整數(shù)k,（l

0??k2.任意給出2011個(gè)正整數(shù)a1

,a2

,L使得2011/(ak?1

?ak?2

?L?al).證明 構(gòu)造部分和序列,s20

11?

a2011

,s1

?

a1

,s2

?

a12?

a

,L?

a12?

a

?

L則有如下兩種可能：（i）存在整數(shù)h(1≤h≤2011)使,得意.2011/s.h此時(shí),取k=0,l=h即滿(mǎn)足題（ii）對(duì)任一整數(shù)i，均有20

1?|

si

(1?i?20

1).令si

?ri(m

od

2011)，則有1?ri

?2010(1?i?2011),這樣,2011個(gè)余數(shù)均在1到2010之間,由鴿巢原理知, 存在整數(shù)

k

?

l(1?

k,l?

20

1),

使得

rk

?

rl

.不妨設(shè)l>

k，則ak?1

?

ak?

2

?

L

?

al

?

sl

?

skl?

(r

?

rk

)(m

od

2011)?

0(m

od

2011).綜合（i）和（ii），即知題設(shè)結(jié)論成立.2.4利用分割區(qū)間來(lái)構(gòu)造“鴿巢“例一個(gè)孩子每天至少看一個(gè)小時(shí)電視，共看7周，每周看電視從不超過(guò)11小時(shí)，證明：在此期間存在連續(xù)若干天這個(gè)孩子恰好看電視20個(gè)小時(shí)。（設(shè)這個(gè)孩子每看電視時(shí)間為整數(shù)個(gè)小時(shí)）證明 設(shè)這個(gè)孩子7周內(nèi)每天看電視的時(shí)間分別為a1,a2,…,a49小時(shí)，現(xiàn)在構(gòu)造出數(shù)列{an}的前n項(xiàng)和的數(shù)列s1=a1，

s2=a1+a

2，……，

s49

=a1+a

2+…+a

49

，則有：1≤

s1<s

2<s

3<…<s

49

≤11×7=77,而序列s1+20，s2+20，…,

s49

+20也是一個(gè)嚴(yán)格的遞增序列，且有21≤s1

+20<

s

2+20<…<

s

49

+20

≤77+20=97，考慮數(shù)列S1

,S,2

.,S49

,S1

?

20,S2

?

20,

.,S49

?

20,它共有98項(xiàng)，且都在1至97中取值，根據(jù)鴿巢原理，必定存在兩項(xiàng)相等。由于前49項(xiàng)和后49項(xiàng)又分別是嚴(yán)格遞增的，因此必然存在一個(gè)i和j,使得si=sj

+20(i>j)，即si-sj=20，從而這個(gè)孩子從j+1天起到第i天的時(shí)間里恰好看電視20個(gè)小時(shí)。類(lèi)似這樣的例子還有不少。一個(gè)乒乓球手有37天時(shí)間準(zhǔn)備一場(chǎng)比賽,他決定每天至少打1場(chǎng)球,37天至多打60場(chǎng)球,證明:在此期間存在連續(xù)若干天他恰好打了21場(chǎng)球。一個(gè)學(xué)生解數(shù)學(xué)題100天,每天至少解一道題,每10天至多解17

道題,證明:在此期間存在連續(xù)若干天他恰好解了29道題.那么是否存在連續(xù)若干天他恰好解了30道題。在(0,1]區(qū)間上任取5個(gè)點(diǎn)，則必有兩個(gè)點(diǎn)它們的距離小于1/4。n+1個(gè)實(shí)數(shù)xi滿(mǎn)足0≤xi≤1（i=1,2,……,n+1

），求證這n+1個(gè)實(shí)數(shù)中必存在兩個(gè)數(shù)xi,xj，使得1i

jn|x

?

x

|?

.使得ri=rj

，i

j不妨設(shè)s<s，則即aj能被ai整除.2.5

利用化分集合來(lái)構(gòu)造“鴿巢”例 試證明在1到200

個(gè)自然數(shù)中任取101

個(gè)數(shù)，一定存在兩個(gè)數(shù)，其中的一個(gè)數(shù)是另一個(gè)數(shù)的整數(shù)倍。證明:設(shè)a1，a2，…，a101是被選出的101個(gè)整數(shù),對(duì)任一ai，都可以唯一地寫(xiě)成如下的形式：i

ia

??2si

r(i?

1,2,L

,101),其中，si為整數(shù)，ri為奇數(shù).由于1≤ai≤200，所以ri(1≤i≤101只)

能取1，3，5，…，199這100個(gè)奇數(shù)，而r1，r2，

…，r101共有101項(xiàng)，由鴿巢原理知，存在 1≤i≠≤j

101，ij

j2siia

2sj

?

ra??

2sj?si??

r整數(shù)推論3的應(yīng)用.例1把1至10這十?dāng)?shù)字隨機(jī)的排成一個(gè)圓圈，證明必有一個(gè)三相鄰數(shù)字之和大于等于17．證明

把1至10這十個(gè)數(shù)字隨機(jī)排成一個(gè)圓圈,從中任取三個(gè)相鄰數(shù)字的方法有10種,設(shè)這10種三個(gè)相鄰數(shù)字之和分別為m

1,m

2,…m,

10,則有1

2

10.m

+m+…+m =3×(1+2+…+10)=

3?

(10?

11)2m

1

?

m

2

?

.?

m

10

?

3?

1

?

16.5

?

16,10

2由推論3,必存在m

i(0≤i≤10),使得m

i≥17，即問(wèn)題得證．例2設(shè)有大小兩個(gè)圓盤(pán)，每個(gè)都劃分成大小相等的200個(gè)小扇形，在大盤(pán)上任選100個(gè)小扇形漆成黑色，其余的100個(gè)小扇形漆成白色，而將小盤(pán)上的200個(gè)小扇形任意漆成黑色或白色.現(xiàn)將大小兩只圓盤(pán)的中心重合，轉(zhuǎn)動(dòng)小盤(pán)使小盤(pán)上的每個(gè)扇形含在大盤(pán)上的小扇形之內(nèi).證明：有一個(gè)位置使小盤(pán)上至少有100個(gè)小扇形同大盤(pán)上相應(yīng)的小扇形同色.證明：由條件，固定大盤(pán)轉(zhuǎn)動(dòng)小盤(pán)共有200個(gè)不同的位置，設(shè)m

i表示在第i個(gè)位置時(shí)，大、小扇形同色的個(gè)數(shù)（i=1，2，…，200），只要證明2001200(m

1

?

m

2

?

L

?

m對(duì)小盤(pán)上的每一個(gè)扇形，由著色的條件，旋轉(zhuǎn)一周（200個(gè)位置），與大扇形同色的個(gè)數(shù)為100個(gè)，所以200個(gè)小扇形在旋轉(zhuǎn)一周同色的個(gè)數(shù)共有2001200100×200=20000個(gè).??)?

99?m

1

?

m

2?

L

?

m

200

?

20000(m

1

?

m

2?

L

?

m結(jié)論成立.)?99.即可.3.

鴿巢原理在國(guó)內(nèi)外數(shù)學(xué)競(jìng)賽中的應(yīng)用中學(xué)數(shù)學(xué)競(jìng)賽中，鴿巢原理常常作為一種處理問(wèn)題的工具，多用于組合問(wèn)題，在一些代數(shù)與幾何問(wèn)題中亦有應(yīng)用。鴿巢原理及其簡(jiǎn)單形式多用于解答存在性問(wèn)題，應(yīng)用鴿巢原理解題時(shí)，關(guān)鍵是構(gòu)造適合的鴿巢。下面給出一些利用鴿巢原理解決的數(shù)學(xué)競(jìng)賽題。例1(北京市數(shù)學(xué)競(jìng)賽復(fù)賽試題)將910瓶紅、藍(lán)墨水，排成130行，每行7瓶。證明：不論怎樣排列，紅、藍(lán)墨水瓶的顏色次序必定出現(xiàn)下述兩種情況之一種：至少三行完全相同；至少有兩組（四行），每組的兩行完全相同。證明：910瓶紅、藍(lán)墨水，排成130行，每行7瓶。每行中的7個(gè)位置中的每個(gè)位置都有紅、藍(lán)兩種可能，因而總計(jì)共有27=128種不同的行式（當(dāng)且僅當(dāng)兩行墨水瓶顏色及次序完全相同時(shí)稱(chēng)為“行式”相

同）。依鴿巢原理可知，在130行中必有兩行（記為A

，B

）“行式”相同。在除A、B外的其余128行中若有一行P與A

（B

）“行式”相同，則P，A

，B滿(mǎn)足“至少有三行完全相同”，結(jié)論成立；在除A，B外的其余128行中若沒(méi)有與A

（B

）行式相同者，則128行至多有127種不同的行式，

依鴿巢原則，必有兩行（不妨記為C、D

）行式相同，這樣便找到了（A，

B

）、（C

，D

）兩組（四行），每組兩行完全相同，結(jié)論成立。例2(1995

年全國(guó)高中數(shù)學(xué)聯(lián)賽試題)將平面上每個(gè)點(diǎn)以紅、藍(lán)兩色之一著色，證明：存在這樣的兩個(gè)相似三角形，它們的相似比為1995，并且每一個(gè)三角形的三個(gè)頂點(diǎn)同色。證明：如圖，作兩個(gè)半徑分別為1和1995的同心圓，在內(nèi)圓上任取9個(gè)點(diǎn)，必有5點(diǎn)同色，記為A

1,A

2,A

3,A

4,A5

。如圖所示，連半徑0Ai交大圓于BiB4A5A4B3A3A2（i=1,2,3,4,5），對(duì)B

1

，B

2

，B

3

，B

4

，B5

，必有3點(diǎn)同色，記為B

i,B

j,B

k，則△B

iB

jB

k與△A

iAjA

k為三頂點(diǎn)同色的相似三角形，相似比等于1995，所以結(jié)論成立.B1B2B5A12?弦長(zhǎng)b?2rsin例3(美國(guó)普特南數(shù)學(xué)競(jìng)賽題)在坐標(biāo)平面上任取五個(gè)整點(diǎn)（該點(diǎn)的橫縱坐標(biāo)都取整數(shù)），證明其中一定存在兩個(gè)整點(diǎn)，它們的連線(xiàn)中點(diǎn)仍是整點(diǎn)。證明欲使坐標(biāo)平面兩點(diǎn)（x1,y1）、（x2,y2）的中點(diǎn)坐標(biāo)是整數(shù)，必須而且只須x1

與x2，y1與y2

的奇偶性相同。坐標(biāo)平面上的任意整點(diǎn)按照橫縱兩個(gè)坐標(biāo)的奇偶性考慮有且只有如下四種：（奇數(shù)、奇數(shù)），（偶數(shù)，偶數(shù)），（奇數(shù)，偶數(shù)），（偶數(shù)，奇數(shù)）以此構(gòu)造四個(gè)“鴿巢”，則在坐標(biāo)平面上任取五個(gè)整點(diǎn)，那么至少有兩個(gè)整點(diǎn)，屬于同一個(gè)“鴿巢”，因此它們連線(xiàn)的中點(diǎn)就必是整點(diǎn)。我們可以把整點(diǎn)的概念推廣：如果（x1，x2

,,…xn）是n維（元）有序數(shù)組，且x1，x2,,…xn中的每一個(gè)數(shù)都是整數(shù)，則稱(chēng)（x1，x2,,…xn）是一個(gè)n維整點(diǎn)（整點(diǎn)又稱(chēng)格點(diǎn)）。如果對(duì)所有的n維整點(diǎn)按每一個(gè)xi的奇偶性來(lái)分類(lèi)，由于每一個(gè)位置上有奇、偶兩種可能性，因此共可分為2×2×…×2=2

n個(gè)類(lèi)(鴿巢)。這是對(duì)n維整點(diǎn)的一種分類(lèi)方法。當(dāng)n=3時(shí)，23=8，此時(shí)可以構(gòu)造命題：“任意給定空間中九個(gè)整點(diǎn)，求證它們之中必有兩點(diǎn)存在，使連接這兩點(diǎn)的直線(xiàn)段的內(nèi)部含有整點(diǎn)”。這就是1971年的美國(guó)普特南數(shù)學(xué)競(jìng)賽題。例4(美國(guó)普特南數(shù)學(xué)競(jìng)賽題)任意6個(gè)人中必有3個(gè)人互相認(rèn)識(shí)，或互相不認(rèn)識(shí)。這就是著名的Ramsey問(wèn)題。我們用6個(gè)點(diǎn)表示6個(gè)人,當(dāng)兩個(gè)人互相認(rèn)識(shí)時(shí),兩個(gè)點(diǎn)之間連一條紅邊,當(dāng)兩個(gè)人互相不認(rèn)識(shí)時(shí),兩個(gè)點(diǎn)之間連一條藍(lán)邊,于是這個(gè)問(wèn)題可轉(zhuǎn)化為：對(duì)6階完成圖K

6

的邊任著紅、藍(lán)兩色，必存在同色三角形。證明

設(shè)A

0,A

1,…,A

5為

K

6

的6個(gè)頂點(diǎn)，從A

0

引出

的5條邊中，必有3條同色，不妨設(shè)A

0A

1

,A

0A

2,A

0A

3

為紅色。若△A

1A

2A

3有一條紅邊，則這條邊的兩個(gè)端點(diǎn)連同A

0構(gòu)成紅色三角形。若△A

1A

2A

3沒(méi)有紅邊，則這個(gè)三角形為藍(lán)紅色三角形。結(jié)論成立。注:6為結(jié)論成立的最小數(shù).例5

(第6屆國(guó)際中學(xué)生數(shù)學(xué)奧林匹克試題)17名科學(xué)家中每名科學(xué)家都和其他科學(xué)家通信，在他們通信時(shí)，只討論三個(gè)問(wèn)題，而且任意兩名科學(xué)家通信時(shí)只討論同一個(gè)問(wèn)題，證明：其中至少有三名科學(xué)家，他們相互通信時(shí)討論的是同一個(gè)問(wèn)題。證明：視17個(gè)科學(xué)家為17個(gè)點(diǎn)，每?jī)蓚€(gè)點(diǎn)之間連一條線(xiàn)表示這兩個(gè)科學(xué)家在討論同一個(gè)問(wèn)題，若討論第一個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連紅線(xiàn)，若討論第2個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連條黃線(xiàn)，若討論第3個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連條藍(lán)線(xiàn)。三名科學(xué)家研究同一個(gè)問(wèn)題就轉(zhuǎn)化為找到一個(gè)三邊同顏色的三角形。即轉(zhuǎn)化為證明：對(duì)17階完成圖K

17

的邊任著紅、藍(lán)、黃三色，必存在同色三角形?？紤]科學(xué)家A，他要與另外的16位科學(xué)家每人通信討論一個(gè)問(wèn)題，相應(yīng)于從A出發(fā)引出16條線(xiàn)段，將它們?nèi)境?種顏色，由鴿巢原理必有6條同色，不妨記為AB

1，AB

2，AB

3，AB

4，AB

5，AB

6同紅色，若B

i（i=1，

2，…，6）之間有紅線(xiàn)，則出現(xiàn)紅色三角線(xiàn)，命題已成立；否則B

1，B

2，B

3，B

4，B

5，B

6之間的連線(xiàn)只染有黃、藍(lán)兩色，由例4存在同色三角形，證畢。前面數(shù)例我們看到，鴿巢原理的應(yīng)用多么奇妙，其關(guān)鍵在于恰當(dāng)?shù)刂圃禅澇玻拖裎覀兦懊嫠榻B的，利用余數(shù)分類(lèi)，劃分集合，分割區(qū)間，分割圖形，利用染色等，都是制造“鴿巢”的方法。運(yùn)用鴿巢原理解題往往能起到事半功倍的效果，鴿巢原理的道理極其簡(jiǎn)單，但需要巧妙地精心地應(yīng)用它，不僅可以解決國(guó)內(nèi)數(shù)學(xué)競(jìng)賽中的問(wèn)題，而且可以解決國(guó)際中學(xué)生數(shù)學(xué)競(jìng)賽的問(wèn)題.4.鴿巢原理的推廣——Ramsey

定理(介紹）鴿巢原理是組合學(xué)中的一個(gè)最基本的原理，應(yīng)用它可以解決許多涉及存在性的組合問(wèn)題。但對(duì)于一些更加復(fù)雜的有關(guān)存在性的組合問(wèn)題，鴿巢原理顯得無(wú)能為力。1928年，24歲的英國(guó)數(shù)學(xué)家、哲學(xué)家兼經(jīng)濟(jì)學(xué)家F.P.Ramsey在倫敦的數(shù)學(xué)會(huì)宣讀了一篇題為“論形式邏輯中的一個(gè)問(wèn)題”的論文，文中證明的一個(gè)組合數(shù)學(xué)定理后來(lái)被稱(chēng)為Ramsey定理。Ramsey定理可視為鴿巢原理的推廣，它的簡(jiǎn)單形式就是我們前面提到的著名的