鴿巢原理及其應(yīng)用精選文檔

1、1鴿巢原理及其應(yīng)用鴿巢原理及其應(yīng)用 陳陳 淑淑 貞貞 2011.11.222主要內(nèi)容v1. 引言引言v2. 鴿巢原理鴿巢原理v3.鴿巢的構(gòu)造及其應(yīng)用鴿巢的構(gòu)造及其應(yīng)用v4.鴿巢原理在國(guó)內(nèi)外數(shù)學(xué)競(jìng)賽中的應(yīng)用鴿巢原理在國(guó)內(nèi)外數(shù)學(xué)競(jìng)賽中的應(yīng)用v5.鴿巢原理的推廣鴿巢原理的推廣ramsey定理定理(介紹）介紹）31. 引言引言 鴿巢原理為組合學(xué)中的一個(gè)重要原理。鴿巢原理最早是由19世紀(jì)的德國(guó)數(shù)學(xué)家迪里赫萊（dirichlet）運(yùn)用于解決數(shù)學(xué)問(wèn)題而提出來(lái)的，所以又稱為“迪里赫萊原理”，也有稱“抽屜原理”的。應(yīng)用它可以解決許多有趣的問(wèn)題，并且常常得到一些令人驚異的結(jié)果。它常被用來(lái)證明一些存在性的數(shù)學(xué)問(wèn)題，

2、并且在數(shù)論和密碼學(xué)中也有著廣泛的應(yīng)用。對(duì)于一些比較特殊的問(wèn)題，若用一般的數(shù)學(xué)方法去研究，很復(fù)雜或根本解決不了，但用鴿巢原理往往能起到事半功倍的效果，所以鴿巢原理也是國(guó)際國(guó)內(nèi)數(shù)學(xué)競(jìng)賽中的重要內(nèi)容，在數(shù)學(xué)競(jìng)賽中具有很大的應(yīng)用意義。42. 鴿巢原理鴿巢原理2.1 鴿巢原理的簡(jiǎn)單形式鴿巢原理的簡(jiǎn)單形式 若有n+1只鴿子飛到n個(gè)鴿巢里面，則至少有一個(gè)鴿巢里至少有兩只鴿子。2.2 鴿巢原理的加強(qiáng)形式鴿巢原理的加強(qiáng)形式注: n+1為結(jié)論成立的最小數(shù)。 將q1q2qnn1個(gè)物品放入n個(gè)抽屜中，則至少存在某個(gè)抽屜i（1in）,使得這個(gè)抽屜里至少有qi個(gè)物品。注: q1q2qnn1為結(jié)論成立的 最小 數(shù),記為n(

3、q1,q2,qn;1)。顯然,當(dāng)q1=q2=qn=2時(shí),加強(qiáng)形式即為簡(jiǎn)單形式。即即n(q1,q2,qn;1)=q1+q2+qn-n+1.5 推論1 n(r-1)1只鴿子飛入n個(gè)巢里，則至少有一個(gè)鴿巢里至少有r只鴿子。當(dāng)qi=r時(shí)，得： 推論3：設(shè)m1,m2,mn均為正整數(shù),且滿足 ,則m1,m2,mn中至少有一個(gè)數(shù)不小于r。 123.1nmmmmrn 推論2：m只鴿子飛入n個(gè)巢里，則至少有一個(gè)鴿巢里至少有 只鴿子,其中 是不小于 的最小整數(shù)。mnmnmn63 鴿巢的構(gòu)造及其應(yīng)用鴿巢的構(gòu)造及其應(yīng)用 雖然鴿巢原理十分簡(jiǎn)單明了，但不是所有的問(wèn)題都一眼就可以看出什么是鴿子，什么是鴿巢。在應(yīng)用它的時(shí)候卻

4、涉及很多技巧，這是利用鴿巢原理解題的魅力所在。常用的構(gòu)造鴿巢的方法有：利用整數(shù)分組、余數(shù)分類，劃分集合，分割區(qū)間、分割圖形，利用染色等。下面給出幾類常用的構(gòu)造鴿巢的方法。3.1 利用整數(shù)分組構(gòu)造利用整數(shù)分組構(gòu)造“鴿巢鴿巢” 例例1 試證明從試證明從11，2 2，knkn中選中選n+1n+1個(gè)數(shù)，總存在個(gè)數(shù)，總存在2 2個(gè)數(shù)，它們之間最多個(gè)數(shù)，它們之間最多相差相差k-1k-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è)鴿巢，從中任個(gè)鴿巢，從中任選選n+1個(gè)數(shù)，由鴿巢原理，必有個(gè)數(shù)，由鴿巢原理，

5、必有2個(gè)數(shù)選在同一個(gè)鴿巢中，所以它們的個(gè)數(shù)選在同一個(gè)鴿巢中，所以它們的差最大為差最大為k-1。7 路易路易波薩是匈牙利數(shù)學(xué)家波薩是匈牙利數(shù)學(xué)家, 在他在他11歲時(shí)匈牙利大數(shù)學(xué)家厄杜斯給他出歲時(shí)匈牙利大數(shù)學(xué)家厄杜斯給他出了個(gè)問(wèn)題了個(gè)問(wèn)題: “如果你手頭上有如果你手頭上有n+1個(gè)整數(shù)，這些整數(shù)是小于或等于個(gè)整數(shù)，這些整數(shù)是小于或等于2n的，那么你一的，那么你一定會(huì)有一對(duì)數(shù)是互素的。你知道這是什么原因嗎？定會(huì)有一對(duì)數(shù)是互素的。你知道這是什么原因嗎？”波薩僅思考了半分鐘就巧妙地回答了這個(gè)問(wèn)題。波薩僅思考了半分鐘就巧妙地回答了這個(gè)問(wèn)題。 例例2 在一條筆直的馬路上種樹(shù)，從起點(diǎn)起，每隔在一條筆直的馬路上種

6、樹(shù)，從起點(diǎn)起，每隔1米種一棵數(shù)。如果把三塊米種一棵數(shù)。如果把三塊“愛(ài)愛(ài)護(hù)護(hù) 樹(shù)木樹(shù)木”的小牌分別掛在三棵樹(shù)上，那么不管怎么掛，至少有兩棵掛牌的樹(shù)它們之間的小牌分別掛在三棵樹(shù)上，那么不管怎么掛，至少有兩棵掛牌的樹(shù)它們之間的的 距離是偶數(shù)（以米為單位）。距離是偶數(shù)（以米為單位）。 解解 從起點(diǎn)開(kāi)始給每課樹(shù)編號(hào)，樹(shù)上的號(hào)碼依次為從起點(diǎn)開(kāi)始給每課樹(shù)編號(hào)，樹(shù)上的號(hào)碼依次為1,2,3,1,2,3,n, 把這些號(hào)碼把這些號(hào)碼分為奇數(shù)和偶數(shù)兩類，當(dāng)作兩個(gè)鴿巢，分為奇數(shù)和偶數(shù)兩類，當(dāng)作兩個(gè)鴿巢， 把三塊牌分別掛在三棵樹(shù)上，那么不管把三塊牌分別掛在三棵樹(shù)上，那么不管怎么掛，這三棵掛牌的樹(shù)至少有兩棵樹(shù)的號(hào)碼同為奇數(shù)

7、或偶數(shù)，而這兩棵樹(shù)的差怎么掛，這三棵掛牌的樹(shù)至少有兩棵樹(shù)的號(hào)碼同為奇數(shù)或偶數(shù)，而這兩棵樹(shù)的差必為偶數(shù)，必為偶數(shù)， 所以至少有兩棵掛牌的樹(shù)它們之間的距離是偶數(shù)（以米為單位）。所以至少有兩棵掛牌的樹(shù)它們之間的距離是偶數(shù)（以米為單位）。8 3.2 利用劃分圖形構(gòu)造利用劃分圖形構(gòu)造“鴿巢鴿巢” 例例1 1 邊長(zhǎng)為邊長(zhǎng)為1 1的正方形中，任意放入的正方形中，任意放入9 9個(gè)點(diǎn)，求證這個(gè)點(diǎn)，求證這9 9個(gè)點(diǎn)中任個(gè)點(diǎn)中任取取3 3個(gè)點(diǎn)組成的三角形中，至少有一個(gè)的面積不超過(guò)個(gè)點(diǎn)組成的三角形中，至少有一個(gè)的面積不超過(guò) . .18 解：將邊長(zhǎng)為解：將邊長(zhǎng)為1 1的正方形等分成邊長(zhǎng)為的正方形等分成邊長(zhǎng)為1/21/2

8、的四個(gè)小正方形，視這四的四個(gè)小正方形，視這四個(gè)正方形為鴿巢，個(gè)正方形為鴿巢，9 9個(gè)點(diǎn)任意放入這四個(gè)正方形中，由鴿巢原理必有三個(gè)點(diǎn)任意放入這四個(gè)正方形中，由鴿巢原理必有三點(diǎn)落入同一個(gè)正方形內(nèi)點(diǎn)落入同一個(gè)正方形內(nèi). .現(xiàn)特別取出這個(gè)正方形來(lái)加以討論現(xiàn)特別取出這個(gè)正方形來(lái)加以討論. . 圖1 把落在這個(gè)正方形中的三點(diǎn)記為把落在這個(gè)正方形中的三點(diǎn)記為d d、e e、f.f.如圖如圖1 1，通過(guò)這三點(diǎn)中的任意一點(diǎn)（如通過(guò)這三點(diǎn)中的任意一點(diǎn)（如e e）作正方形邊平行線）作正方形邊平行線1111 1()2222 2hh11.4848hhsdefsdegsefg 所以，結(jié)論成立。9如果如果8個(gè)點(diǎn)無(wú)一個(gè)在圓心

9、上，可將圓分成個(gè)點(diǎn)無(wú)一個(gè)在圓心上，可將圓分成7個(gè)相等的扇形，由鴿巢原理，個(gè)相等的扇形，由鴿巢原理， 這這8個(gè)點(diǎn)至少有兩個(gè)在同一個(gè)扇形內(nèi)，則這兩點(diǎn)之間的距離小于半徑。個(gè)點(diǎn)至少有兩個(gè)在同一個(gè)扇形內(nèi)，則這兩點(diǎn)之間的距離小于半徑。 例例2 2 在圓內(nèi)（包刮圓周）有在圓內(nèi)（包刮圓周）有8 8個(gè)點(diǎn)，則其中必有兩個(gè)點(diǎn)，它們之間的距離小個(gè)點(diǎn)，則其中必有兩個(gè)點(diǎn)，它們之間的距離小于圓的半徑。于圓的半徑。證明證明 分兩種情況考慮。分兩種情況考慮。a1a2a3a4a6a5o 2 sin2br（弦長(zhǎng)）2. 2. 如果如果8 8個(gè)點(diǎn)有一個(gè)點(diǎn)在圓心，可將圓個(gè)點(diǎn)有一個(gè)點(diǎn)在圓心，可將圓分成分成6個(gè)相等的扇形，如圖，個(gè)相等的扇形

10、，如圖，取扇形取扇形oa1a2不包含不包含oa2,扇形扇形oa2a3不包含不包含oa3,扇形扇形oa6a1不包含不包含oa1, 由鴿巢原理，余下的由鴿巢原理，余下的7個(gè)點(diǎn)個(gè)點(diǎn)至少有兩個(gè)在在同一個(gè)扇形內(nèi)，則這兩點(diǎn)之間的距至少有兩個(gè)在在同一個(gè)扇形內(nèi)，則這兩點(diǎn)之間的距離小于半徑。離小于半徑。由于圓上相鄰兩點(diǎn)由于圓上相鄰兩點(diǎn)a ai,a,aj間的弦長(zhǎng)恰好為圓的半徑，所以間的弦長(zhǎng)恰好為圓的半徑，所以10在邊長(zhǎng)為1的正方形內(nèi)任取5個(gè)點(diǎn),則其中至少有兩點(diǎn),它們之間的 距離不超過(guò)2.22.證明: (1) 在一邊長(zhǎng)為1的三角形中任取10個(gè)點(diǎn),則其中至少有兩點(diǎn),它們之間 的距離不超過(guò)1/3. (2) 確定mn，使

11、得在一邊長(zhǎng)為1的三角形中任取mn個(gè)點(diǎn),則其中至少有 兩點(diǎn),它們之間的距離不超過(guò)1/n.類似這樣的問(wèn)題還有不少。113.3 3.3 利用余數(shù)分類構(gòu)造利用余數(shù)分類構(gòu)造“鴿巢鴿巢” 例例 試證明任意給定試證明任意給定5252個(gè)整數(shù)，它們之中必有個(gè)整數(shù)，它們之中必有2 2個(gè)數(shù)，其和或差個(gè)數(shù)，其和或差是是100100的倍數(shù)的倍數(shù)( (即被即被100100整除）整除）。 證明：任意一個(gè)整數(shù)證明：任意一個(gè)整數(shù)a除以除以100產(chǎn)生的余數(shù)為產(chǎn)生的余數(shù)為0，1，2，99共共100種。用種。用a1, a2, ,a52表示這表示這52個(gè)整數(shù)，個(gè)整數(shù)，ai除以除以100產(chǎn)生的余數(shù)記為產(chǎn)生的余數(shù)記為ri（ i=1，2，5

12、2）。）。 由鴿巢原理，這由鴿巢原理，這52個(gè)整數(shù)分別除以個(gè)整數(shù)分別除以100產(chǎn)生的產(chǎn)生的52個(gè)余數(shù)個(gè)余數(shù)r1,r2,r52中必中必有兩個(gè)余數(shù)落在同一組中有兩個(gè)余數(shù)落在同一組中， 我們現(xiàn)在用我們現(xiàn)在用0 0，1 1，2 2，,99,99這這100100個(gè)余數(shù)來(lái)構(gòu)造鴿巢，將它們分為個(gè)余數(shù)來(lái)構(gòu)造鴿巢，將它們分為5151組，組，構(gòu)造出構(gòu)造出5151個(gè)鴿巢：個(gè)鴿巢： 00，11，9999，22， 9898，49,51,50,49,51,50,即存在兩個(gè)數(shù)，它們的和或差能被即存在兩個(gè)數(shù)，它們的和或差能被100整除。整除。若這兩個(gè)余數(shù)落在若這兩個(gè)余數(shù)落在0或或50中，則它們的和及中，則它們的和及差都能被差

13、都能被100整除。整除。 若這兩個(gè)余數(shù)落在剩下的若這兩個(gè)余數(shù)落在剩下的49組中的一組，當(dāng)余數(shù)相同組中的一組，當(dāng)余數(shù)相同時(shí)，它們的差時(shí)，它們的差被被100100整除，整除，當(dāng)余數(shù)不同時(shí)，它們的和被當(dāng)余數(shù)不同時(shí)，它們的和被100整除，整除，12類似這樣的例子也有不少。 這個(gè)問(wèn)題的一般提法 任意給定n+2個(gè)整數(shù)，它們之中必有2個(gè)數(shù)，其和或差是2n的倍數(shù)。1.任取n+1個(gè)正整數(shù)，求證在這n+1 個(gè)數(shù)中必有兩個(gè)數(shù)它們之差被n整除.2.任意給出2011個(gè)正整數(shù) 證明必存在正整數(shù)122011,a aa122011/().kklaaa使得,2011),k lkl （0132.任意給出2011個(gè)正整數(shù) 證明必存

14、在正整數(shù)122011,a aa122011/().kklaaa使得,2011),k lkl （0證明證明 構(gòu)造部分和序列構(gòu)造部分和序列112122011122011,sasaasaaa則有如下兩種可能：則有如下兩種可能：（i）存在整數(shù)存在整數(shù)h(1h 2011), 使得使得 . 此時(shí)此時(shí), 取取k=0,l=h即滿足即滿足 題題意意.2011/hs（iiii）對(duì)任一整數(shù)）對(duì)任一整數(shù)i，均有，均有 . .令令 ，2011| (12011)isi (mod2011)iisr12010 (12011),iri 則有則有這樣這樣, 2011個(gè)余數(shù)均在個(gè)余數(shù)均在1到到2010之間之間,由鴿巢原理知由鴿巢原

15、理知, , 存在整數(shù)存在整數(shù) , , 使得使得 . . (1,2011)klk lklrr不妨設(shè)不妨設(shè)l k，則，則12()(mod2011)0(mod2011).kkllklkaaassrr綜合（綜合（i）和（）和（ii），即知題設(shè)結(jié)論成立），即知題設(shè)結(jié)論成立.143.4 利用分割區(qū)間來(lái)構(gòu)造利用分割區(qū)間來(lái)構(gòu)造“鴿巢鴿巢“ 例例 一個(gè)孩子每天至少看一個(gè)小時(shí)電視，共看一個(gè)孩子每天至少看一個(gè)小時(shí)電視，共看7 7周，每周看電視從不周，每周看電視從不超過(guò)超過(guò)1111小時(shí)，證明：在此期間存在連續(xù)若干天這個(gè)孩子恰好看電視小時(shí)，證明：在此期間存在連續(xù)若干天這個(gè)孩子恰好看電視 2020個(gè)個(gè)小時(shí)。（設(shè)這個(gè)孩子每

16、看電視時(shí)間為整數(shù)個(gè)小時(shí)）小時(shí)。（設(shè)這個(gè)孩子每看電視時(shí)間為整數(shù)個(gè)小時(shí)） 證明證明 設(shè)這個(gè)孩子設(shè)這個(gè)孩子7周內(nèi)每天看電視的時(shí)間分別為周內(nèi)每天看電視的時(shí)間分別為a1,a2,a49小時(shí)小時(shí)，現(xiàn)在構(gòu)造出數(shù)列現(xiàn)在構(gòu)造出數(shù)列an的前的前n項(xiàng)和的數(shù)列項(xiàng)和的數(shù)列 s1=a1， s2=a1+a2， s49=a1+a2+a49 ，則有：1 s1s2s3s49117=77,而序列s1+20，s2+20，, s49+20也是一個(gè)嚴(yán)格的遞增序列，且有 21 s1+20 s2+20j)，即，即si-sj= 20，從而這個(gè)孩子從，從而這個(gè)孩子從j+1天起到第天起到第i天的時(shí)間里恰好看電視天的時(shí)間里恰好看電視20個(gè)小時(shí)。個(gè)小時(shí)

17、。類似這樣的例子還有不少。類似這樣的例子還有不少。1.1.一個(gè)乒乓球手有一個(gè)乒乓球手有3737天時(shí)間準(zhǔn)備一場(chǎng)比賽天時(shí)間準(zhǔn)備一場(chǎng)比賽, ,他決定每天至少打他決定每天至少打1 1場(chǎng)球場(chǎng)球,37,37 天至多打天至多打6060場(chǎng)球場(chǎng)球, ,證明證明: :在此期間存在連續(xù)若干天他恰好打了在此期間存在連續(xù)若干天他恰好打了2121場(chǎng)球。場(chǎng)球。2.一一個(gè)學(xué)生解數(shù)學(xué)題個(gè)學(xué)生解數(shù)學(xué)題100天天,每天至少解一道題每天至少解一道題,每每10天至多解天至多解17道道題題,證明證明:在此期間存在連續(xù)若干天他恰好解了在此期間存在連續(xù)若干天他恰好解了29道題道題.那么是否存那么是否存在連續(xù)若干天他恰好解了在連續(xù)若干天他恰好

18、解了30道題。道題。3. 在在(0,1區(qū)間上任取區(qū)間上任取5個(gè)點(diǎn)，則必有兩個(gè)點(diǎn)它們的距離小于個(gè)點(diǎn)，則必有兩個(gè)點(diǎn)它們的距離小于1/4。4. n+1個(gè)實(shí)數(shù)個(gè)實(shí)數(shù)xi滿足滿足0 xi1（i=1,2,n+1），求證這），求證這n+1個(gè)實(shí)數(shù)中必存在個(gè)實(shí)數(shù)中必存在兩個(gè)數(shù)兩個(gè)數(shù)xi,xj，使得，使得 1|.ijxxn16 由于1ai200，所以ri(1i101)只能取1，3，5，199這100個(gè)奇數(shù)，而r1，r2， ，r101共有101項(xiàng)，由鴿巢原理知，存在 1ij101，使得ri=rj ，不妨設(shè)sisj，則222jjiisssjjsiiarar整數(shù)即aj能被ai整除.3.5 利用化分集合來(lái)構(gòu)造利用化分集合

19、來(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ě)成 如下的形式：2 (1,2,101),isiiari其中，si為整數(shù)，ri為奇數(shù).17推論推論3 3的應(yīng)用的應(yīng)用. .例例1 把把1至至10這十?dāng)?shù)字隨機(jī)的排成一個(gè)圓圈，證明這十?dāng)?shù)字隨機(jī)的排成一個(gè)圓圈，證明必有一個(gè)三相鄰數(shù)字之和大于等于必有一個(gè)三相鄰數(shù)字之和大于等于17證明把證明把1至至10這十個(gè)數(shù)字隨機(jī)排成一個(gè)圓圈這十個(gè)數(shù)字隨機(jī)排成一個(gè)圓圈,從中任取從中任取三個(gè)相鄰數(shù)字的方法有三個(gè)相鄰數(shù)字的方法有

20、10種種,設(shè)這設(shè)這10種三個(gè)相鄰數(shù)字之和分種三個(gè)相鄰數(shù)字之和分別為別為m1,m2,m10,則有則有m1+m2+m10=3(1+2+10)=3 (10 11).21210.3 1116.516,102mmm18 例 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è)mi

21、表示在第i個(gè)位 置時(shí)，大、小扇形同色的個(gè)數(shù)（i=1，2，200），只要證明122001()99 200mmm即可. 對(duì)小盤(pán)上的每一個(gè)扇形，由著色的條件，旋轉(zhuǎn)一周（200個(gè)位置），與大扇形同色的個(gè)數(shù)為100個(gè)，所以200個(gè)小扇形在旋轉(zhuǎn)一周同色的個(gè)數(shù)共有 100200=20000個(gè).1220012200 200001 ()99 200mmmmmm 結(jié)論成立194. 4. 鴿巢原理在國(guó)內(nèi)外數(shù)學(xué)競(jìng)賽中的應(yīng)用鴿巢原理在國(guó)內(nèi)外數(shù)學(xué)競(jìng)賽中的應(yīng)用 中學(xué)數(shù)學(xué)競(jìng)賽中，鴿巢原理常常作為一種處理問(wèn)題的工具，中學(xué)數(shù)學(xué)競(jìng)賽中，鴿巢原理常常作為一種處理問(wèn)題的工具，多用于組合問(wèn)題，在一些代數(shù)與幾何問(wèn)題中亦有應(yīng)用。鴿巢原理多用

22、于組合問(wèn)題，在一些代數(shù)與幾何問(wèn)題中亦有應(yīng)用。鴿巢原理及其簡(jiǎn)單形式多用于解答存在性問(wèn)題，應(yīng)用鴿巢原理解題時(shí)，關(guān)及其簡(jiǎn)單形式多用于解答存在性問(wèn)題，應(yīng)用鴿巢原理解題時(shí)，關(guān)鍵是構(gòu)造適合的鴿巢。下面給出一些利用鴿巢原理解決的數(shù)學(xué)鍵是構(gòu)造適合的鴿巢。下面給出一些利用鴿巢原理解決的數(shù)學(xué)競(jìng)競(jìng)賽題。賽題。例1 (北京市數(shù)學(xué)競(jìng)賽復(fù)賽試題北京市數(shù)學(xué)競(jìng)賽復(fù)賽試題) 將將910瓶紅、藍(lán)墨水，排成130行，每行7瓶。證明：不論怎樣排列，紅、藍(lán)墨水瓶的顏色次序必定出現(xiàn)下述兩種情況之一種： 1至少三行完全相同； 2至少有兩組（四行），每組的兩行完全相同。20 證明：910瓶紅、藍(lán)墨水，排成130行，每行7瓶。每行中的7個(gè)位置

23、中的每個(gè)位置都有紅、藍(lán)兩種可能，因而總計(jì)共有27=128種不同的行式（當(dāng)且僅當(dāng)兩行墨水瓶顏色及次序完全相同時(shí)稱為“行式”相同）。依鴿巢原理可知，在130行中必有兩行（記為a，b）“行式”相同。 在除a、b外的其余128行中若有一行p與a（b）“行式”相同，則p，a，b滿足“至少有三行完全相同”，結(jié)論成立；在除a，b外的其余128行中若沒(méi)有與a（b）行式相同者，則128行至多有127種不同的行式，依鴿巢原則，必有兩行（不妨記為c、d）行式相同，這樣便找到了（a，b）、（c，d）兩組（四行），每組兩行完全相同，結(jié)論成立。 例2 (1995年全國(guó)高中數(shù)學(xué)聯(lián)賽試題年全國(guó)高中數(shù)學(xué)聯(lián)賽試題 ) 將平面上每

24、個(gè)點(diǎn)以紅、藍(lán)兩色之一著色，證明：存在這樣的兩個(gè)相似三角形，它們的相似比為1995，并且每一個(gè)三角形的三個(gè)頂點(diǎn)同色。21證明：如圖，作兩個(gè)半徑分別為1和1995的同心圓，在內(nèi)圓上任取9個(gè)點(diǎn)，必有5點(diǎn)同色，記為a1,a2,a3,a4,a5。如圖所示，連半徑0ai交大圓于bi（i=1,2,3,4,5），對(duì)b1，b2，b3，b4，b5，必有3點(diǎn)同色，記為bi,bj,bk，則bibjbk與aiaja k為三頂點(diǎn)同色的相似三角形，相似比等于1995，所以結(jié)論成立.2sin2rb 弦長(zhǎng)22例例3 (美國(guó)普特南數(shù)學(xué)競(jìng)賽題美國(guó)普特南數(shù)學(xué)競(jìng)賽題 ) 在坐標(biāo)平面上任取五個(gè)整點(diǎn)（該點(diǎn)的橫縱坐標(biāo)都取整數(shù)），證明其中一定

25、存在兩個(gè)整點(diǎ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è)“鴿巢”，因此它們連線的中點(diǎn)就必是整點(diǎn)。 我們可以把整點(diǎn)的概念推廣：如果（x1，x2,xn）是n維（元）有序數(shù)組，且x1，x2,xn中的每一個(gè)數(shù)都是整數(shù)，則稱（x1，x2,xn）是一個(gè)n維整點(diǎn)（整點(diǎn)又稱格點(diǎn)）。如果對(duì)所有的n維整點(diǎn)按

26、每一個(gè)xi的奇偶性來(lái)分類，由于每一個(gè)位置上有奇、偶兩種可能性，因此共可分為222=2n個(gè)類(鴿巢)。這是對(duì)n維整點(diǎn)的一種分類方法。 23 當(dāng)n=3時(shí)，23=8，此時(shí)可以構(gòu)造命題：“任意給定空間中九個(gè)整點(diǎn)，求證它們之中必有兩點(diǎn)存在，使連接這兩點(diǎn)的直線段的內(nèi)部含有整點(diǎn)”。這就是1971年的美國(guó)普特南數(shù)學(xué)競(jìng)賽題。 例例4 (美國(guó)普特南數(shù)學(xué)競(jìng)賽題美國(guó)普特南數(shù)學(xué)競(jìng)賽題 ) 任意6個(gè)人中必有3個(gè)人互相認(rèn)識(shí)，或互相不認(rèn)識(shí)。這就是著名的ramsey問(wèn)題。 這個(gè)問(wèn)題可轉(zhuǎn)化為：對(duì)6階完成圖k6的邊任著紅、藍(lán)兩色，必存在同色三角形。 證明 設(shè)a0,a1,a5為 k6的6個(gè)頂點(diǎn)，從a0 引出 的5條邊中，必有3條同色

27、，不妨設(shè)a0a1,a0a2,a0a3為紅色。若a1a2a3有一條紅邊，則這條邊的兩個(gè)端點(diǎn)連同a0構(gòu)成紅色三角形。若a1a2a 3沒(méi)有紅邊，則這個(gè)三角形為藍(lán)紅色三角形。結(jié)論成立。 我們用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)邊,于是注注:6為結(jié)論成立的最小數(shù)為結(jié)論成立的最小數(shù).24例例5 (第第6屆國(guó)際中學(xué)生數(shù)學(xué)奧林匹克試題屆國(guó)際中學(xué)生數(shù)學(xué)奧林匹克試題 ) 17名科學(xué)家中每名科學(xué)家都和其他科學(xué)家通信，在他們通信時(shí)，只討論三個(gè)問(wèn)題，而且任意兩名科學(xué)家通信時(shí)只討論同一個(gè)問(wèn)題，證明：其中至少有三名科學(xué)家，他們相互通信時(shí)討論的是同一個(gè)問(wèn)題。

28、證明：視17個(gè)科學(xué)家為17個(gè)點(diǎn)，每?jī)蓚€(gè)點(diǎn)之間連一條線表示這兩個(gè)科學(xué)家在討論同一個(gè)問(wèn)題，若討論第一個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連紅線，若討論第2個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連條黃線，若討論第3個(gè)問(wèn)題則在相應(yīng)兩點(diǎn)連條藍(lán)線。三名科學(xué)家研究同一個(gè)問(wèn)題就轉(zhuǎn)化為找到一個(gè)三邊同顏色的三角形。即轉(zhuǎn)化為證明:對(duì)17階完成圖k17的邊任著紅、藍(lán)、黃三色，必存在同色三角形。 考慮科學(xué)家a，他要與另外的16位科學(xué)家每人通信討論一個(gè)問(wèn)題，相應(yīng)于從a出發(fā)引出16條線段，將它們?nèi)境?種顏色，由鴿巢原理必有6條同色，不妨記為ab1，ab2，ab3，ab4，ab5，ab6同紅色，若bi（i=1，2，6）之間有紅線，則出現(xiàn)紅色三角線，命題已成立；否

29、則b1，b2，b3，b4，b5，b6之間的連線只染有黃、藍(lán)兩色，由例4存在同色三角形，證必。25 前面數(shù)例我們看到，鴿巢原理的應(yīng)用多么奇妙，其關(guān)鍵在于恰當(dāng)?shù)刂圃禅澇?，就像我們前面所介紹的，利用余數(shù)分類，劃分集合，分割區(qū)間，分割圖形，利用染色等，都是制造“鴿巢”的方法。運(yùn)用鴿巢原理解題往往能起到事半功倍的效果，鴿巢原理的道理極其簡(jiǎn)單，但需要巧妙地精心地應(yīng)用它，不僅可以解決國(guó)內(nèi)數(shù)學(xué)競(jìng)賽中的問(wèn)題，而且可以解決國(guó)際中學(xué)生數(shù)學(xué)競(jìng)賽的問(wèn)題265.鴿巢原理的推廣鴿巢原理的推廣ramsey定理定理(介紹）介紹） 鴿巢原理是組合學(xué)中的一個(gè)最基本的原理，應(yīng)用它可以解決許鴿巢原理是組合學(xué)中的一個(gè)最基本的原理，應(yīng)用它可以解決許多涉及存在性的組合問(wèn)題。但對(duì)于一些更加復(fù)雜的有關(guān)存在性的組多涉及存在性的組合問(wèn)題。但對(duì)于一些更加復(fù)雜的有關(guān)存在性的組合問(wèn)題，鴿巢原理顯得無(wú)能為力。合問(wèn)題，鴿巢原理顯得無(wú)能為力。 19281928年，年，242