鴿籠原理的一般形式設qi為正整數(i=1,2,…,n)，

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

矛盾。從而定理得證。§3.2鴿籠原理的推論1§3.2鴿籠原理的一般形式三個推論推論3.2.1：若把m個物體放到n個盒子中去，則至少有一個盒子放有不少于

(m-1)/n

+1個物體。

證明：用反證法證明。假設結論不成立，即對每個盒子中至多放有

(m-1)/n

個物體，從而這n個盒子放入物體的總數最多為n×(m-1)/n

≤m-1這與假設矛盾。§3.2鴿籠原理的推論2§3.2鴿籠原理的一般形式三個推論推論3.2.1：若把m個物體放到n個盒子中去，則至少有一個盒子放有不少于

(m-1)/n

+1個物體。

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

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

，則至少存在一個i，使得mi≥r。推論3.2.1：若把m個物體放到n個盒子中去，則至少有一個盒子放有不少于

(m-1)/n

+1個物體。

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

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

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

格第i+19格12…192012…1920

12…

19201…1920...............§3.2鴿籠原理推廣例1-2例題§3.2鴿籠原理的一般形式證明：在C=c1c2…c40中，當i遍歷1,2,…,20時，每一個bj,j=1,2,…,20，歷遍

a1,a2,…,a20。因A中有10個0和10個1，每一個bj都有10位次對應相等，從而當

i歷遍1,2,…,20時，共有10×20=200位次對應相等。故對每個

i平均有200/20=10位相等，因而對某個i至少有10位對應相等。...ABC第i

格第i+19格12…192012…1920

12…

19201…1920...............§3.2鴿籠原理推廣例2例題§3.2鴿籠原理的一般形式例2、將兩個大小不一的圓盤分別分成200個相等的扇形。在大圓盤上任取100個扇形染成紅色，另外的100個扇形染成藍色，并將小圓盤上的扇形任意染成紅色或藍色，然后將小圓盤放在大圓盤上且中心重合時，轉動小圓盤可使其每一扇形都疊放于大圓盤的某一扇形內。證明：當適當轉動小圓盤可使疊放的扇形對中，同色者至少100對。證明：設使大小兩盤中心重合，固定大盤，轉動小盤，則有200個不同的位置使小盤上的每個小扇形含在大盤上的小扇形中，（將這200種可能的位置看作200個不同的盒子）。由于大盤上的200個小扇形中有100個染成紅色，100個染成藍色，所以小盤上的每個小扇形在轉動過程中，無論染成紅色或藍色，在200個可能的重合位置上恰好有100次與大盤上的小扇形同色（將同色的扇形看作放入盒子的物體）。因而小盤上的200個小扇形在200個重合位置上共同色100

200=20000次。而20000＞200(100-1)+1，由推論2.2.2知，存在著某個位置，使同色的小扇形數大于等于100個。§3.2鴿籠原理推廣例3例題§3.2鴿籠原理的一般形式例3、將[1,67]劃分為４個子集，必有一個子集中有一數是同子集中的兩數之差（或和）。證明：設從1到67的整數任意分成4部分p1,p2,p3,p4，作如下分析：①由鴿籠原理知，1到67的整數中必有一部分，不妨設為p1,至少有

(67-1)/4+1=17個元素。并設這17個元素為a1＜a2＜…＜a17，若ai中存在一個元素是某兩個元素之差，則命題得證。否則，令b1=a2-a1,b2=a3-a1,…,b16=a17-a1，顯然1≤bi＜67，故bi不屬于p1，屬于p2,p3或p4。②同理，bi中至少有

(17-1)/3+1=6個元素屬于p2，設這6個元素為c1＜c2＜…＜c6，若ci中存在一個元素是某兩個元素之差，則命題得證。否則，令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個元素屬于p3，設這3個元素為f1＜f2＜f3，若fi中存在一個元素是某兩個元素之差，則命題得證。否則，令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中任一個，與已知矛盾。§3.2鴿籠原理推廣例4例題§3.2鴿籠原理的一般形式例4、證明：在每個包含n2+1個不同的實數的序列中，存在一個長度為n+1的遞增子序列，或者存在一個長度為n+1的遞減子序列。（一個序列的長度是指該序列的元素個數）。證明：設 是一個實數序列，并假設在這個序列中沒有長度為n+1的遞增子序列，則要證明一定有一個長度為n+1的遞減子序列。令表示以為首項的最長遞增子序列的長度 則對每個k

，由假設知道這相當于把個物品放入個盒子中，由推論2.2.2知，必有一個盒子里面至少有個物品，即存在及 ，使得對應于這些下標的實數序列必滿足它們構成一長為的遞減子序列。否則，若有某個使得 ，那么以 為首項的最長遞增子序列加上 ，就得到一個以為首項的遞增子序列，由定義知，這與 矛盾。因此， 成立。

這是一個長度為n+1的遞減子序列，故結論成立。§3.2鴿籠原理推廣例5例題§3.2鴿籠原理的一般形式例5、將1,2,…,10隨機地擺成一圓，則必有某相鄰三數之和至少是17。證明：設 表示該圓上相鄰三個數之和（i居中）。這樣的和共有10個。而1,2,…,10中的每一個都出現在這十個和的三個之中，故由推論2.2.3知，存在一個i

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

證明：在這10個人中任意挑選一個人，不妨把這個人稱作p。則其他的9個人可以分為下面的兩個集合F和S。其中F=與p相識的人的集合，S=與p不相識的人的集合如果S中有4個（或4個以上）人，則或者這4個人（或4個人以上）或者彼此認識，或者有兩個人彼此不認識。如果有4個人彼此認識，則結論成立。如果在S中有2人彼此不認識，則由于這兩個人都與p不認識，因此有3人彼此不認識，故定理結論成立。如果S中最多有3個人，則由鴿籠原理知，F中至少有6個人。由定理2.3知，F中一定有3人相互認識或有3人相互不認識。如果有3個人彼此不認識，則定理成立。如果有3個人彼此認識，則把p加入，就有4個彼此認識的人，故定理得證。§3.3Ramsey定理5§3.3Ramsey定理定理3.410人中一定有4人相互認識或有3人相互不認識。定理3.510人中一定有3人相互認識或有4人相互不認識。證明：在定理3.4中，如果把“不認識”換成“認識”，“認識”換成“不認識”，則有定理3.5，該定理的證明類似于定理3.4。§3.3Ramsey定理6§3.3Ramsey定理定理3.620個人中一定有4個人相互認識或相互不認識。證明：在這20個人中任意挑選一個人，不妨把這個人稱作p。則其他的19個人可以分為下面的兩個集合F和S。其中F=與p相識的人的集合，S=與p不相識的人的集合由鴿籠原理知，這兩個集合中至少有一個包含（至少）10個人。如果F中有10個（或10個以上）人，則或者這10個人（或10個人以上）有3個人相互認識