組合競(jìng)賽問(wèn)題等多個(gè)文件第二章

第2章鴿籠原理

回顧前一章——計(jì)數(shù)：本章重點(diǎn)介紹鴿籠原理及其在排列組合中的（存在性）應(yīng)用：例子、意義鴿籠原理及其推廣

Ramsey定理

Ramsey數(shù)排列組合組合恒等式§2.1鴿籠原理定理§2.1鴿籠原理定理2.1鴿籠原理（抽屜原理）若把n+1個(gè)物體放到n

（n≥1）個(gè)盒子中去，則至少有一個(gè)盒子放有至少2個(gè)物體。證明：用反證法證明。如果n個(gè)盒子中每個(gè)盒子至多放入一個(gè)物體，則放入n個(gè)盒子中的物體總數(shù)至多為n個(gè)。這與假設(shè)有n+1個(gè)物體矛盾。從而定理得證。注：鴿籠原理只指出了至少存在這樣的盒子，并沒(méi)有給出“確定哪一個(gè)盒子有此性質(zhì)的方法”，因此，它只能用來(lái)解決存在性問(wèn)題。4=4+0+0=3+1+0=2+2+0=2+1+1§2.1鴿籠原理例1、2、3§2.1鴿籠原理例題例1、一年有365天，今有366個(gè)人，則其中至少有兩個(gè)人生日相同。證明：此例中把“天”當(dāng)作盒子，相當(dāng)于365個(gè)盒子放入366個(gè)物體。得證。例2、抽屜里有10雙相同的手套，從中取11只出來(lái)，其中至少有兩只是完整配對(duì)的。證明：此例中把“每雙手套”當(dāng)作盒子，相當(dāng)于10個(gè)盒子放11個(gè)物體。得證。例3、一個(gè)教師每周上7次課，則這教師至少有一天要上至少2次課（星期天不上課除外）。證明：此例中把“天”當(dāng)作盒子，相當(dāng)于6個(gè)盒子放7個(gè)物體，從而得證?！?.1鴿籠原理解釋§2.1鴿籠原理例題依據(jù)？方法？目的？例題例4、某次會(huì)議由n位代表參加，每一位代表至少認(rèn)識(shí)其余n-1位中的一位，則n位代表中，至少有兩位認(rèn)識(shí)的人數(shù)相等（n≥2）。證明：n個(gè)代表認(rèn)識(shí)的人數(shù)有1,2,…,n-1，相當(dāng)于n-1盒子，根據(jù)鴿籠原理可知至少有兩人認(rèn)識(shí)的人數(shù)相等。例5、某次會(huì)議由n位代表參加，每一位代表至少認(rèn)識(shí)其余n-1位中的一位，則n位代表中，至少有兩位認(rèn)識(shí)的人數(shù)相等（n≥2）。成立嗎？

證明：n個(gè)代表認(rèn)識(shí)的人數(shù)只能取0,1,2,…,n-1。（1）若每一位代表至少認(rèn)識(shí)其余n-1位中的一位，則這種情況例4中已經(jīng)討論。（2）但若有一位代表認(rèn)識(shí)的人數(shù)為0，即此代表和其他人都不認(rèn)識(shí)，則其他n-1人認(rèn)識(shí)的人數(shù)只有0,1,2,…,n-2共n-1種可能，所以根據(jù)鴿籠原理，這種情況下也至少有兩人認(rèn)識(shí)的人數(shù)相等?！?.1鴿籠原理例4、5§2.1鴿籠原理§2.1鴿籠原理例6證明：設(shè)所取n+1個(gè)數(shù)是a1,a2,…,an,an+1，對(duì)該序列中的每一個(gè)數(shù)去掉一切2的因子，直至剩下一個(gè)奇數(shù)為止，即ri=ai/2x

，x=0,1,2,…。結(jié)果得由奇數(shù)組成的序列R：r1,r2,…,rn,rn+1。1到2n中只有n個(gè)奇數(shù)，故序列R中至少有兩個(gè)數(shù)是相同的。設(shè)為 ，對(duì)應(yīng)的有，則ai是aj的倍數(shù)?！?.1鴿籠原理例題例6、從1到2n的正整數(shù)中任取n+1個(gè)，則這n+1個(gè)數(shù)中至少有一對(duì)數(shù)，其中一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù)（n≥1）?！?.1鴿籠原理例7證明：構(gòu)造一個(gè)序列則此時(shí)有兩種可能：（1）若這m個(gè)和中有一個(gè)sh(1≤h≤m)是m的倍數(shù)，則結(jié)論成立。（2）若這m個(gè)和中沒(méi)有一個(gè)

是m的倍數(shù)，則這些和被m除時(shí)必有1,2,…,m-1這樣的余數(shù)。由于有m個(gè)和，且只有m-1個(gè)余數(shù)，于是我們可以構(gòu)造m-1個(gè)盒子，第i個(gè)“盒子”是被m除余數(shù)為i的數(shù)，(i=1,2,…,m-1)。由鴿籠原理知，用m除各和時(shí)，至少有兩個(gè)和的余數(shù)是相同的。則存在整數(shù)k和l(k＜l)，使得sk和sl被m除有相同的余數(shù)，即sk≡slmodm。故§2.1鴿籠原理例題例7、設(shè)a1a2…am是正整數(shù)的序列，則至少存在整數(shù)k和l，1≤k＜l≤m，使得和ak+1+ak+2+…+al是m的倍數(shù)。（m≥2）

§2.1鴿籠原理例8§2.1鴿籠原理例題例8、設(shè)a1a2…a100是由1和2組成的序列，已知從其中任意一個(gè)數(shù)開始的順序10個(gè)數(shù)的和不超過(guò)16，即對(duì)于1≤i≤91恒有ai+ai+1+…+ai+9≤16。則至少存在h和k，k＞h≥1，使得ah+ah+1+…+ak=39。證明：作序列由于每個(gè)ai都是正的整數(shù)，故而且故根據(jù)假設(shè)有做序列最后的項(xiàng)但序列（S）共200項(xiàng)，為從1到199的整數(shù)。根據(jù)鴿籠原理，其中必有兩項(xiàng)相等。但序列（S）中前100項(xiàng)為單調(diào)增，后100項(xiàng)也為單調(diào)增，故存在h和k，使則即或§2.1鴿籠原理例9§2.1鴿籠原理例題例9、證明：把5個(gè)頂點(diǎn)放到邊長(zhǎng)為2的正方形中，至少存在兩個(gè)頂點(diǎn)，它們之間的距離小于或等于。證明：把邊長(zhǎng)為2的正方形分成四個(gè)全等的邊長(zhǎng)為1的小正方形，則每個(gè)小正方形的對(duì)角線長(zhǎng)為。如果把每個(gè)小正方形當(dāng)作一個(gè)盒子，由鴿籠原理知，把5個(gè)頂點(diǎn)放到4個(gè)盒子中，必有一個(gè)盒子中放入了兩個(gè)頂點(diǎn)。即必有一個(gè)小正方形中有2個(gè)頂點(diǎn)；而小正方形的對(duì)角線長(zhǎng)為，也就是說(shuō)小正方形中任意兩點(diǎn)的最大距離為。這就證明了本題。鴿籠原理的一般形式設(shè)qi為正整數(shù)(i=1,2,…,n)，

，如把q個(gè)物體放入n個(gè)盒子中，則至少存在一個(gè)i，使得第i個(gè)盒子中至少有qi個(gè)物體。§2.2鴿籠原理一般形式§2.2鴿籠原理的一般形式定理2.2證明：用反證法證明。假設(shè)結(jié)論不成立，即對(duì)每一個(gè)i，第i個(gè)盒子至多放有ni個(gè)物體，，從而這n個(gè)盒子放入物體的總數(shù)為這與

矛盾。從而定理得證?！?.2鴿籠原理的推論1§2.2鴿籠原理的一般形式三個(gè)推論推論2.2.1：若把m個(gè)物體放到n個(gè)盒子中去，則至少有一個(gè)盒子放有不少于(m-1)/n+1個(gè)物體。

證明：用反證法證明。假設(shè)結(jié)論不成立，即對(duì)每個(gè)盒子中至多放有(m-1)/n個(gè)物體，從而這n個(gè)盒子放入物體的總數(shù)最多為n×(m-1)/n≤m-1這與假設(shè)矛盾。§2.2鴿籠原理的推論2§2.2鴿籠原理的一般形式三個(gè)推論推論2.2.1：若把m個(gè)物體放到n個(gè)盒子中去，則至少有一個(gè)盒子放有不少于(m-1)/n+1個(gè)物體。

推論2.2.2：若把n(r-1)+1個(gè)物體放到n個(gè)盒子中去，則至少有一個(gè)盒子放有不少于r個(gè)物體。

證明：這是定理2.2當(dāng)q1=q2=…=qn=r時(shí)的特殊情況。 §2.2鴿籠原理的推論3§2.2鴿籠原理的一般形式三個(gè)推論推論2.2.3：若mi為正整數(shù)(i=1,2,…,n),

，則至少存在一個(gè)i，使得mi≥r。推論2.2.1：若把m個(gè)物體放到n個(gè)盒子中去，則至少有一個(gè)盒子放有不少于(m-1)/n+1個(gè)物體。

推論2.2.2：若把n(r-1)+1個(gè)物體放到n個(gè)盒子中去，則至少有一個(gè)盒子放有不少于r個(gè)物體。

證明：用反證法證明。假設(shè)結(jié)論不成立，即對(duì)每個(gè)i，mi≤r-1，則這與假設(shè)矛盾?！?.2鴿籠原理推廣例1-1例題§2.2鴿籠原理的一般形式例1、設(shè)A=a1a2…a20時(shí)有10個(gè)0和10個(gè)1組成的某一20位2進(jìn)制數(shù)，B=b1b2…b20是任意的20位2進(jìn)制數(shù)，先把A、B分別計(jì)入圖（A）、（B）兩個(gè)20個(gè)格子，分別得（A）、（B）兩種圖像，并把兩個(gè)B聯(lián)接的40位的2進(jìn)制數(shù)C=b1b2…b20

b1b2…b20，它的圖像為（C）。則存在某個(gè)i，1≤i≤20，使得cici+1…ci+19與a1a2…a20至少有10位對(duì)應(yīng)相等。...ABC第i

格第i+19格12…192012…192012…

19201…1920...............§2.2鴿籠原理推廣例1-2例題§2.2鴿籠原理的一般形式證明：在C=c1c2…c40中，當(dāng)i遍歷1,2,…,20時(shí)，每一個(gè)bj,j=1,2,…,20，歷遍

a1,a2,…,a20。因A中有10個(gè)0和10個(gè)1，每一個(gè)bj都有10位次對(duì)應(yīng)相等，從而當(dāng)

i歷遍1,2,…,20時(shí)，共有10×20=200位次對(duì)應(yīng)相等。故對(duì)每個(gè)

i平均有200/20=10位相等，因而對(duì)某個(gè)i至少有10位對(duì)應(yīng)相等。...ABC第i

格第i+19格12…192012…192012…

19201…1920...............§2.2鴿籠原理推廣例2例題§2.2鴿籠原理的一般形式例2、將兩個(gè)大小不一的圓盤分別分成200個(gè)相等的扇形。在大圓盤上任取100個(gè)扇形染成紅色，另外的100個(gè)扇形染成藍(lán)色，并將小圓盤上的扇形任意染成紅色或藍(lán)色，然后將小圓盤放在大圓盤上且中心重合時(shí)，轉(zhuǎn)動(dòng)小圓盤可使其每一扇形都疊放于大圓盤的某一扇形內(nèi)。證明：當(dāng)適當(dāng)轉(zhuǎn)動(dòng)小圓盤可使疊放的扇形對(duì)中，同色者至少100對(duì)。證明：設(shè)使大小兩盤中心重合，固定大盤，轉(zhuǎn)動(dòng)小盤，則有200個(gè)不同的位置使小盤上的每個(gè)小扇形含在大盤上的小扇形中，（將這200種可能的位置看作200個(gè)不同的盒子）。由于大盤上的200個(gè)小扇形中有100個(gè)染成紅色，100個(gè)染成藍(lán)色，所以小盤上的每個(gè)小扇形在轉(zhuǎn)動(dòng)過(guò)程中，無(wú)論染成紅色或藍(lán)色，在200個(gè)可能的重合位置上恰好有100次與大盤上的小扇形同色（將同色的扇形看作放入盒子的物體）。因而小盤上的200個(gè)小扇形在200個(gè)重合位置上共同色100200=20000次。而20000＞200(100-1)+1，由推論2.2.2知，存在著某個(gè)位置，使同色的小扇形數(shù)大于等于100個(gè)?！?.2鴿籠原理推廣例3例題§2.2鴿籠原理的一般形式例3、將[1,67]劃分為４個(gè)子集，必有一個(gè)子集中有一數(shù)是同子集中的兩數(shù)之差（或和）。證明：設(shè)從1到67的整數(shù)任意分成4部分p1,p2,p3,p4，作如下分析：①由鴿籠原理知，1到67的整數(shù)中必有一部分，不妨設(shè)為p1,至少有(67-1)/4+1=17個(gè)元素。并設(shè)這17個(gè)元素為a1＜a2＜…＜a17，若ai中存在一個(gè)元素是某兩個(gè)元素之差，則命題得證。否則，令b1=a2-a1,b2=a3-a1,…,b16=a17-a1，顯然1≤bi＜67，故bi不屬于p1，屬于p2,p3或p4。②同理，bi中至少有(17-1)/3+1=6個(gè)元素屬于p2，設(shè)這6個(gè)元素為c1＜c2＜…＜c6，若ci中存在一個(gè)元素是某兩個(gè)元素之差，則命題得證。否則，令d1=c2-c1,d2=c3-c1,…,d5=c6-c1，顯然1≤di＜67，且存在1≤l,m≤17,di=ci-c1=al-am,i=1,2,…,5，故di不屬于p1,p2，屬于p3,p4。③di中至少有(6-1)/2+1=3個(gè)元素屬于p3，設(shè)這3個(gè)元素為f1＜f2＜f3，若fi中存在一個(gè)元素是某兩個(gè)元素之差，則命題得證。否則，令g1=f2-f1,g2=f3-f1，顯然1≤gi＜67，且存在1≤l,m≤17,gi=fi-f1=al-am,i=1,2

，故fi不屬于p1,p2,p3，屬于p4。④若g1=g2-g1，則命題得證。否則，令h=g2-g1，顯然1≤h＜67，且同上可以證明h不屬于p1,p2,p3,p4中任一個(gè)，與已知矛盾?！?.2鴿籠原理推廣例4例題§2.2鴿籠原理的一般形式例4、證明：在每個(gè)包含n2+1個(gè)不同的實(shí)數(shù)的序列中，存在一個(gè)長(zhǎng)度為n+1的遞增子序列，或者存在一個(gè)長(zhǎng)度為n+1的遞減子序列。（一個(gè)序列的長(zhǎng)度是指該序列的元素個(gè)數(shù)）。證明：設(shè) 是一個(gè)實(shí)數(shù)序列，并假設(shè)在這個(gè)序列中沒(méi)有長(zhǎng)度為n+1的遞增子序列，則要證明一定有一個(gè)長(zhǎng)度為n+1的遞減子序列。令表示以為首項(xiàng)的最長(zhǎng)遞增子序列的長(zhǎng)度 則對(duì)每個(gè)k

，由假設(shè)知道這相當(dāng)于把個(gè)物品放入個(gè)盒子中，由推論2.2.2知，必有一個(gè)盒子里面至少有個(gè)物品，即存在及 ，使得對(duì)應(yīng)于這些下標(biāo)的實(shí)數(shù)序列必滿足它們構(gòu)成一長(zhǎng)為的遞減子序列。否則，若有某個(gè)使得 ，那么以 為首項(xiàng)的最長(zhǎng)遞增子序列加上 ，就得到一個(gè)以為首項(xiàng)的遞增子序列，由定義知，這與 矛盾。因此， 成立。 這是一個(gè)長(zhǎng)度為n+1的遞減子序列，故結(jié)論成立?！?.2鴿籠原理推廣例5例題§2.2鴿籠原理的一般形式例5、將1,2,…,10隨機(jī)地?cái)[成一圓，則必有某相鄰三數(shù)之和至少是17。證明：設(shè) 表示該圓上相鄰三個(gè)數(shù)之和（i居中）。這樣的和共有10個(gè)。而1,2,…,10中的每一個(gè)都出現(xiàn)在這十個(gè)和的三個(gè)之中，故由推論2.2.3知，存在一個(gè)i

，使。§2.3Ramsey定理3§2.3Ramsey定理定理2.36個(gè)人中一定有3個(gè)人相互認(rèn)識(shí)或相互不認(rèn)識(shí)。證明：先考慮6個(gè)人中的任意一個(gè)人，不妨把這個(gè)人稱作p。則其他的5個(gè)人可以分為下面的兩個(gè)集合F和S。其中F=與p相識(shí)的人的集合，S=與p不相識(shí)的人的集合由鴿籠原理知，這兩個(gè)集合中至少有一個(gè)集合包含有3個(gè)人。若F包含有3個(gè)人，則這3個(gè)人或者彼此不相識(shí)，或者有兩個(gè)人彼此相識(shí)。如果F中有3個(gè)人彼此不相識(shí)，則結(jié)論成立。如果F中有2人相識(shí)，則由于這兩個(gè)人都與p相識(shí)，因此有3人彼此相識(shí)，故定理結(jié)論成立。類似的，如果S包含3個(gè)人，則這3個(gè)人或者彼此相識(shí)，或者有兩個(gè)人彼此不相識(shí)。如果這3個(gè)人彼此相識(shí)，則結(jié)論成立。如果有兩個(gè)人彼此不相識(shí)，則由于這兩個(gè)人都與p也不相識(shí)，因此有3個(gè)人彼此不相識(shí)，故定理結(jié)論成立?！?.3Ramsey定理4§2.3Ramsey定理定理2.410人中一定有4人相互認(rèn)識(shí)或有3人相互不認(rèn)識(shí)。

證明：在這10個(gè)人中任意挑選一個(gè)人，不妨把這個(gè)人稱作p。則其他的9個(gè)人可以分為下面的兩個(gè)集合F和S。其中F=與p相識(shí)的人的集合，S=與p不相識(shí)的人的集合如果S中有4個(gè)（或4個(gè)以上）人，則或者這4個(gè)人（或4個(gè)人以上）或者彼此認(rèn)識(shí)，或者有兩個(gè)人彼此不認(rèn)識(shí)。如果有4個(gè)人彼此認(rèn)識(shí)，則結(jié)論成立。如果在S中有2人彼此不認(rèn)識(shí)，則由于這兩個(gè)人都與p不認(rèn)識(shí)，因此有3人彼此不認(rèn)識(shí)，故定理結(jié)論成立。如果S中最多有3個(gè)人，則由鴿籠原理知，F(xiàn)中至少有6個(gè)人。由定理2.3知，F(xiàn)中一定有3人相互認(rèn)識(shí)或有3人相互不認(rèn)識(shí)。如果有3個(gè)人彼此不認(rèn)識(shí)，則定理成立。如果有3個(gè)人彼此認(rèn)識(shí)，則把p加入，就有4個(gè)彼此認(rèn)識(shí)的人，故定理得證。§2.3Ramsey定理5§2.3Ramsey定理定理2.410人中一定有4人相互認(rèn)識(shí)或有3人相互不認(rèn)識(shí)。定理2.510人中一定有3人相互認(rèn)識(shí)或有4人相互不認(rèn)識(shí)。證明：在定理2.4中，如果把“不認(rèn)識(shí)”換成“認(rèn)識(shí)”，“認(rèn)識(shí)”換成“不認(rèn)識(shí)”，則有定理2.5，該定理的證明類似于定理2.4。§2.3Ramsey定理6§2.3Ramsey定理定理2.620個(gè)人中一定有4個(gè)人相互認(rèn)識(shí)或相互不認(rèn)識(shí)。證明：在這20個(gè)人中任意挑選一個(gè)人，不妨把這個(gè)人稱作p。則其他的19個(gè)人可以分為下面的兩個(gè)集合F和S。其中F=與p相識(shí)的人的集合，S=與p不相識(shí)的人的集合由鴿籠原理知，這兩個(gè)集合中至少有一個(gè)包含（至少）10個(gè)人。如果F中有10個(gè)（或10個(gè)以上）人，則或者這10個(gè)人（或10個(gè)人以上）有3個(gè)人相互認(rèn)識(shí)，或者有4個(gè)人彼此不認(rèn)識(shí)。如果有4個(gè)人彼此不認(rèn)識(shí)，則結(jié)論成立。如果有3人彼此認(rèn)識(shí)，則由于這3個(gè)人都與p認(rèn)識(shí)，因此有4人彼此認(rèn)識(shí)，故定理結(jié)論成立。如果S中有10個(gè)（或10個(gè)以上）人，則或者這10個(gè)人（或10個(gè)人以上）有3個(gè)人相互不認(rèn)識(shí)，或者有4個(gè)人彼此認(rèn)識(shí)。如果有4個(gè)人彼此認(rèn)識(shí)，則結(jié)論成立。如果有3人彼此不認(rèn)識(shí)，則由于這3個(gè)人都與p不認(rèn)識(shí)，因此有4人彼此不認(rèn)識(shí)，故定理結(jié)論成立?！?.3Ramsey推論1-1§2.3Ramsey定理推論推論2.3.1：用圖形表示這個(gè)定理，上述定理可描述為：