組合數(shù)學(xué)第三章2學(xué)習(xí)資料

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

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

矛盾。從而定理得證。§3.2鴿籠原理的推論1§3.2鴿籠原理的一般形式三個(gè)推論推論3.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§3.2鴿籠原理的一般形式三個(gè)推論推論3.2.1：若把m個(gè)物體放到n個(gè)盒子中去，則至少有一個(gè)盒子放有不少于

(m-1)/n

+1個(gè)物體。

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

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

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

(m-1)/n

+1個(gè)物體。

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

證明：用反證法證明。假設(shè)結(jié)論不成立，即對(duì)每個(gè)i，mi≤r-1，則這與假設(shè)矛盾?！?.2鴿籠原理推廣例1-1例題§3.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…1920

12…

19201…1920...............§3.2鴿籠原理推廣例1-2例題§3.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…1920

12…

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

200=20000次。而20000＞200(100-1)+1，由推論2.2.2知，存在著某個(gè)位置，使同色的小扇形數(shù)大于等于100個(gè)。§3.2鴿籠原理推廣例3例題§3.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è)，與已知矛盾。§3.2鴿籠原理推廣例4例題§3.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é)論成立。§3.2鴿籠原理推廣例5例題§3.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

，使?！?.3Ramsey定理3§2.3Ramsey定理定理3.36個(gè)人中一定有3個(gè)人相互認(rèn)識(shí)或相互不認(rèn)識(shí)。證明：先考慮6個(gè)人中的任意一個(gè)人，不妨把這個(gè)人稱(chēng)作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é)論成立。類(lèi)似的，如果S包含3個(gè)人，則這3個(gè)人或者彼此相識(shí)，或者有兩個(gè)人彼此不相識(shí)。如果這3個(gè)人彼此相識(shí)，則結(jié)論成立。如果有兩個(gè)人彼此不相識(shí)，則由于這兩個(gè)人都與p也不相識(shí)，因此有3個(gè)人彼此不相識(shí)，故定理結(jié)論成立?！?.3Ramsey定理4§3.3Ramsey定理定理3.410人中一定有4人相互認(rèn)識(shí)或有3人相互不認(rèn)識(shí)。

證明：在這10個(gè)人中任意挑選一個(gè)人，不妨把這個(gè)人稱(chēng)作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í)的人，故定理得證?！?.3Ramsey定理5§3.3Ramsey定理定理3.410人中一定有4人相互認(rèn)識(shí)或有3人相互不認(rèn)識(shí)。定理3.510人中一定有3人相互認(rèn)識(shí)或有4人相互不認(rèn)識(shí)。證明：在定理3.4中，如果把“不認(rèn)識(shí)”換成“認(rèn)識(shí)”，“認(rèn)識(shí)”換成“不認(rèn)識(shí)”，則有定理3.5，該定理的證明類(lèi)似于定理3.4。§3.3Ramsey定理6§3.3Ramsey定理定理3.620個(gè)人中一定有4個(gè)人相互認(rèn)識(shí)或相互不認(rèn)識(shí)。證明：在這20個(gè)人中任意挑選一個(gè)人，不妨把這個(gè)人稱(chēng)作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í)