組合數(shù)學(xué)幻燈片22

鴿籠原理的一般形式在定理2.1中，如果將n+1改寫成

于是定理2.1就可以敘述為：如果把2+2+…+2-n+1個(gè)物體放入n個(gè)盒子中去，則至少存在一個(gè)(=1,2,…,n)，使得第個(gè)盒子中至少放有兩個(gè)物體。§2.2我們?cè)O(shè)想，如果在2+2+2++2-n+1中的第個(gè)2改為正整數(shù)(=1,2,…，n)就得到鴿籠原理的一般形式：定理2.2設(shè)是正整數(shù)(=1,2,…，n),q≥-n+1,如果把q個(gè)物體放入n個(gè)盒子中去，則存在一個(gè)，使得第個(gè)盒子中至少有個(gè)物體。用反證法。假設(shè)結(jié)論不成立，即對(duì)每一個(gè),第個(gè)盒子至多放有個(gè)物體()，從而這n個(gè)盒子放入的物體的總數(shù)為這與矛盾，從而定理得證。這樣一來(lái)，定理2.1是定理2.2的特殊形式。證明：推論2對(duì)于正整數(shù)，如果

,至少存在一個(gè)i,使得mi≥r。

推論1

如果把n(r-1)+1個(gè)物體放入n個(gè)盒子中，則至少存在一個(gè)盒子放有不少于r個(gè)物體。設(shè)第個(gè)盒子放有個(gè)物體，由推論1知，把不少于n(r-1)+1的個(gè)物體放入n個(gè)盒子里，至少存在一個(gè)i使得。推論2證明：有或≥n(r-1)+1證明：在由每個(gè)包含個(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的遞減子序列。［例1］證明：令表示以為首項(xiàng)的最長(zhǎng)遞增子序列的長(zhǎng)度，，則對(duì)于每個(gè)，由假設(shè)知1≤≤n。即是說(shuō)有個(gè)數(shù)都在1到n之間。由推論1知，在個(gè)數(shù)中必有r=n+1個(gè)數(shù)是相同的(∵)。

不妨設(shè)其中。下面指出，當(dāng)時(shí)，必有，若對(duì)某個(gè)i(i=1,2,…,n),有，則可把放在以為首項(xiàng)的最長(zhǎng)遞增子序列的前面，就得到以為首項(xiàng)的一個(gè)遞增子序列，這樣一來(lái)，就有，這與相矛盾，因此對(duì)每個(gè)i=1,2,…,n都有這樣一個(gè)長(zhǎng)度為n+1的遞減子序列。故本例結(jié)論成立。

將兩個(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ì)。

［例2］故由推論1知，至少有一種小圓盤與大圓盤的迭放可使迭放的扇形對(duì)中至少有100個(gè)同色的扇形對(duì)。證明：1.首先將大圓盤固定不動(dòng)，則使小圓盤的每一扇形都迭放于大圓盤的一個(gè)扇形中有200種可能的位置(將這200種可能位置看作200個(gè)不同的盒子)。2.由于在這200種可能位置中，小圓盤上的每一扇形都有100次配成同色的扇形對(duì)(將同色的扇形對(duì)看作放入盒子中的物體)。因此這樣的扇形對(duì)一共有200×100個(gè)。而200×100>200×(100-1)+1解：設(shè)表示該圈上相鄰三數(shù)之和，這樣的和共有十個(gè)。而1,2,…10中的每一個(gè)都出現(xiàn)在這十個(gè)和的三個(gè)之中。而故由推論2知，存在一個(gè)使。

如果將1，2，…，10隨機(jī)地?cái)[成一圈，則必有某相鄰三數(shù)之和至少是17［例3］

解：設(shè)為第一天該棋手下棋的盤數(shù)，是第一、二天該棋手下棋盤數(shù)的和，是第一、二、…、j天該棋手下棋盤數(shù)的和，j=1,2,…,77，于是序列是嚴(yán)格遞增序列，且

一棋手為參加一次錦標(biāo)賽要進(jìn)行77天的訓(xùn)練，如果他每天至少下一盤棋，且每周至多下12盤棋，試證明不管他怎樣安排，必存在相繼的若干天，在這段時(shí)間中他恰好下棋21盤。［例4］

于是序列也是嚴(yán)格遞增序列。而，故154個(gè)數(shù)

都在1和153兩