1、你有一桶果凍，其中有黃色、綠色、紅色三種，閉上眼睛抓取同種顏色的兩個。抓取多少個就可以確定你肯定有兩個同一顏色的果凍? 第3章 鴿籠原理 本章重點介紹鴿籠原理及其在排列組合中的（存在性）應(yīng)用： 例子、意義 鴿籠原理及其推廣 Ramsey定理 Ramsey數(shù)3.1 鴿籠原理定理3.1 鴿籠原理定理 3.1鴿籠原理（抽屜原理）若把n+1個物體放到n （n1）個盒子中去，則至少有一個盒子放有至少2個物體。證明：用反證法證明。如果n個盒子中每個盒子至多放入一個物體，則放入n個盒子中的物體總數(shù)至多為n個。這與假設(shè)有n+1個物體矛盾。從而定理得證。注：鴿籠原理只指出了至少存在這樣的盒子，并沒有給出“確定哪

2、一個盒子有此性質(zhì)的方法”，因此，它只能用來解決存在性問題。4 = 4+0+0 = 3+1+0 = 2+2+0 = 2+1+13.1 鴿籠原理例1、2、33.1 鴿籠原理例 題例1、一年有365天，今有366個人，則其中至少有兩個人生日相同。 證明：此例中把“天”當(dāng)作盒子，相當(dāng)于365個盒子放入366個物體。得證。例2、抽屜里有10雙相同的手套，從中取11只出來，其中至少有兩只是完整配對的。 證明：此例中把“每雙手套”當(dāng)作盒子，相當(dāng)于10個盒子放11個物體。得證。例3、一個教師每周上6次課，則這教師至少有一天要上至少2次課（星期六和星期天不上課除外）。 證明：此例中把“天”當(dāng)作盒子，相當(dāng)于5個盒

3、子放6個物體，從而得證。例 題例4、某次會議由n位代表參加，每一位代表至少認(rèn)識其余n-1位中的一位，則n位代表中，至少有兩位認(rèn)識的人數(shù)相等（n2） 。 證明：n個代表認(rèn)識的人數(shù)有1,2,n-1，相當(dāng)于n-1盒子，根據(jù)鴿籠原理可知至少有兩人認(rèn)識的人數(shù)相等。例5、某次會議由n位代表參加，每一位代表至少認(rèn)識其余n-1位中的一位，則n位代表中，至少有兩位認(rèn)識的人數(shù)相等（n2） 。成立嗎？ 證明：n個代表認(rèn)識的人數(shù)只能取0,1,2,n-1。（1）若每一位代表至少認(rèn)識其余n-1位中的一位，則這種情況例4中已經(jīng)討論。（2）但若有一位代表認(rèn)識的人數(shù)為0，即此代表和其他人都不認(rèn)識，則其他n-1人認(rèn)識的人數(shù)只有0

4、,1,2,n-2共n-1種可能，所以根據(jù)鴿籠原理，這種情況下也至少有兩人認(rèn)識的人數(shù)相等。 3.1 鴿籠原理例4、53.1 鴿籠原理3.1 鴿籠原理例6證明：設(shè)所取n+1個數(shù)是a1,a2,an,an+1，對該序列中的每一個數(shù)去掉一切2的因子，直至剩下一個奇數(shù)為止，即 ri = ai / 2x ，x = 0,1,2,。結(jié)果得由奇數(shù)組成的序列R：r1,r2,rn,rn+1。1到2n中只有n個奇數(shù)，故序列R中至少有兩個數(shù)是相同的。設(shè)為 ，對應(yīng)的有 ，則ai是aj的倍數(shù)。3.1 鴿籠原理例 題例6、從1到2n的正整數(shù)中任取n+1個，則這n+1個數(shù)中至少有一對數(shù)，其中一個數(shù)是另一個數(shù)的倍數(shù)（n1） 。 3

5、.1 鴿籠原理例7證明：構(gòu)造一個序列則此時有兩種可能：（1）若這m個和中有一個sh(1hm)是m 的倍數(shù)，則結(jié)論成立。（2）若這m個和中沒有一個 是m 的倍數(shù)，則這些和被m除時必有1,2,m-1這樣的余數(shù)。由于有m個和，且只有m-1個余數(shù)，于是我們可以構(gòu)造m-1個盒子，第i個“盒子”是被m除余數(shù)為i的數(shù)，(i=1,2,m-1)。由鴿籠原理知，用m除各和時，至少有兩個和的余數(shù)是相同的。則存在整數(shù)k和l (kl) ，使得sk和sl 被m除有相同的余數(shù)，即 sksl mod m 。故3.1 鴿籠原理例 題例7、設(shè)a1a2am是正整數(shù)的序列，則至少存在整數(shù)k和l，1klm，使得和ak+1+ak+2+a

6、l是m的倍數(shù)。 （m2） 3.1 鴿籠原理例83.1 鴿籠原理例 題例8、設(shè)a1a2a100是由1和2組成的序列，已知從其中任意一個數(shù)開始的順序10個數(shù)的和不超過16，即對于1i91恒有ai+ai+1+ai+916。則至少存在h和k，kh1，使得ah+ah+1+ak=39 。證明：作序列由于每個ai都是正的整數(shù)，故而且故根據(jù)假設(shè)有做序列最后的項但序列（S）共200項，為從1到199的整數(shù)。根據(jù)鴿籠原理，其中必有兩項相等。但序列（S）中前100項為單調(diào)增，后100項也為單調(diào)增，故存在h和k，使則即或3.1 鴿籠原理例93.1 鴿籠原理例 題例9、證明：把5個頂點放到邊長為2的正方形中，至少存在兩

7、個頂點，它們之間的距離小于或等于 。證明：把邊長為2的正方形分成四個全等的邊長為1的小正方形，則每個小正方形的對角線長為 。如果把每個小正方形當(dāng)作一個盒子，由鴿籠原理知，把5個頂點放到4個盒子中，必有一個盒子中放入了兩個頂點。即必有一個小正方形中有2個頂點；而小正方形的對角線長為 ，也就是說小正方形中任意兩點的最大距離為 。這就證明了本題。鴿籠原理的一般形式設(shè)qi為正整數(shù)(i=1,2,n)， ，如把q個物體放入n個盒子中，則至少存在一個i，使得第i個盒子中至少有qi個物體。 3.2 鴿籠原理一般形式3.2 鴿籠原理的一般形式定理 3.2證明：用反證法證明。假設(shè)結(jié)論不成立，即對每一個i，第i個盒

8、子至多放有ni個物體， ，從而這n個盒子放入物體的總數(shù)為這與矛盾。從而定理得證。3.2 鴿籠原理的推論13.2 鴿籠原理的一般形式三個推論推論3.2.1：若把m個物體放到n個盒子中去，則至少有一個盒子放有不少于(m-1)/n+1個物體。 證明：用反證法證明。假設(shè)結(jié)論不成立，即對每個盒子中至多放有(m-1)/n個物體， 從而這n個盒子放入物體的總數(shù)最多為n(m-1)/nm-1這與假設(shè)矛盾。3.2 鴿籠原理的推論23.2 鴿籠原理的一般形式三個推論推論3.2.1：若把m個物體放到n個盒子中去，則至少有一個盒子放有不少于(m-1)/n+1個物體。 推論3.2.2：若把n(r-1)+1個物體放到n個盒

9、子中去，則至少有一個盒子放有不少于r個物體。 證明：這是定理2.2當(dāng)q1=q2=qn=r時的特殊情況。3.2 鴿籠原理的推論33.2 鴿籠原理的一般形式三個推論推論3.2.3：若mi為正整數(shù)(i=1,2,n), ，則至少存在一個i，使得mir 。推論3.2.1：若把m個物體放到n個盒子中去，則至少有一個盒子放有不少于(m-1)/n+1個物體。 推論3.2.2：若把n(r-1)+1個物體放到n個盒子中去，則至少有一個盒子放有不少于r個物體。 證明：用反證法證明。假設(shè)結(jié)論不成立，即對每個i ，mir-1，則這與假設(shè)矛盾。3.2 鴿籠原理推廣例1-1例 題3.2 鴿籠原理的一般形式例1、設(shè)A=a1a

10、2a20時有10個0和10個1組成的某一20位2進(jìn)制數(shù)，B=b1b2b20是任意的20位2進(jìn)制數(shù)，先把A、B分別計入圖（A）、（B）兩個20個格子，分別得（A）、（B）兩種圖像，并把兩個B聯(lián)接的40位的2進(jìn)制數(shù)C=b1b2b20 b1b2b20，它的圖像為（C）。則存在某個i，1i20，使得cici+1ci+19與a1a2a20至少有10位對應(yīng)相等。.ABC第 i 格第 i +19格1 2 19 20 1 2 19 20 1 2 19 20 1 19 20.3.2 鴿籠原理推廣例1-2例 題3.2 鴿籠原理的一般形式證明：在C = c1c2c40中，當(dāng) i 遍歷1,2,20時，每一個bj, j

11、=1, 2,20，歷遍 a1,a2,a20。因A中有10個0和10個1，每一個bj都有10位次對應(yīng)相等，從而當(dāng) i歷遍1,2,20時，共有1020=200位次對應(yīng)相等。故對每個 i平均有200/20=10位相等，因而對某個 i 至少有10位對應(yīng)相等。.ABC第 i 格第 i +19格1 2 19 20 1 2 19 20 1 2 19 20 1 19 20.3.2 鴿籠原理推廣例2例 題3.2 鴿籠原理的一般形式例2、將兩個大小不一的圓盤分別分成200個相等的扇形。在大圓盤上任取100個扇形染成紅色，另外的100個扇形染成藍(lán)色，并將小圓盤上的扇形任意染成紅色或藍(lán)色，然后將小圓盤放在大圓盤上且中

12、心重合時，轉(zhuǎn)動小圓盤可使其每一扇形都疊放于大圓盤的某一扇形內(nèi)。證明：當(dāng)適當(dāng)轉(zhuǎn)動小圓盤可使疊放的扇形對中，同色者至少100對。 證明：設(shè)使大小兩盤中心重合，固定大盤，轉(zhuǎn)動小盤，則有200個不同的位置使小盤上的每個小扇形含在大盤上的小扇形中， （將這200種可能的位置看作200個不同的盒子）。由于大盤上的200個小扇形中有100個染成紅色，100個染成藍(lán)色，所以小盤上的每個小扇形在轉(zhuǎn)動過程中，無論染成紅色或藍(lán)色，在200個可能的重合位置上恰好有100次與大盤上的小扇形同色（將同色的扇形看作放入盒子的物體）。因而小盤上的200個小扇形在200個重合位置上共同色100200=20000次。而20000

13、200(100-1)+1，由推論2.2.2知，存在著某個位置，使同色的小扇形數(shù)大于等于100個。3.2 鴿籠原理推廣例3例 題3.2 鴿籠原理的一般形式例3、將1, 67劃分為個子集，必有一個子集中有一數(shù)是同子集中的兩數(shù)之差（或和）。證明：設(shè)從1到67的整數(shù)任意分成4部分p1,p2,p3,p4，作如下分析：由鴿籠原理知， 1到67的整數(shù)中必有一部分，不妨設(shè)為p1, 至少有(67-1)/4+1=17個元素。并設(shè)這17個元素為a1a2a17，若ai中存在一個元素是某兩個元素之差，則命題得證。否則，令b1=a2-a1,b2=a3-a1,b16=a17-a1，顯然1bi67，故bi不屬于p1，屬于p2

14、,p3或p4。 同理，bi中至少有(17-1)/3+1=6個元素屬于p2，設(shè)這6個元素為c1c2c6，若ci中存在一個元素是某兩個元素之差，則命題得證。否則，令d1=c2-c1,d2=c3-c1,d5=c6-c1，顯然1di67，且存在1l,m17,di=ci-c1=al-am, i=1,2,5，故di不屬于p1,p2，屬于p3,p4。di中至少有(6-1)/2+1=3個元素屬于p3，設(shè)這3個元素為f1f2f3，若fi中存在一個元素是某兩個元素之差，則命題得證。否則，令g1=f2-f1, g2=f3-f1，顯然1gi67，且存在1l,m17, gi=fi-f1=al-am, i=1,2 ，故f

15、i不屬于p1,p2,p3，屬于p4。若g1=g2-g1，則命題得證。否則，令h=g2-g1，顯然1h67，且同上可以證明h不屬于p1,p2,p3, p4中任一個，與已知矛盾。3.2 鴿籠原理推廣例4例 題3.2 鴿籠原理的一般形式例4、證明：在每個包含n2+1個不同的實數(shù)的序列中，存在一個長度為n+1的遞增子序列，或者存在一個長度為n+1的遞減子序列。（一個序列的長度是指該序列的元素個數(shù)）。 證明：設(shè) 是一個實數(shù)序列，并假設(shè)在這個序列中沒有長度為n+1的遞增子序列，則要證明一定有一個長度為n+1的遞減子序列。令 表示以 為首項的最長遞增子序列的長度則對每個k，由假設(shè)知道這相當(dāng)于把 個物品放入 個盒子中，由推論2.2.2知，必有一個盒子里面至少有 個物品，即存在及，使得對應(yīng)于這些下標(biāo)的實數(shù)序列必滿足它們構(gòu)成一長為