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

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

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

,至少存在一個i,使得mi≥r。

推論1

如果把n(r-1)+1個物體放入n個盒子中，則至少存在一個盒子放有不少于r個物體。設(shè)第個盒子放有個物體，由推論1知，把不少于n(r-1)+1的個物體放入n個盒子里，至少存在一個i使得。推論2證明：有或≥n(r-1)+1證明：在由每個包含個不同的實數(shù)的序列中，存在一個長度為n+1的遞增子序列，或者存在一個長度為n+1的遞減子序列。(一個序列的長度是指該序列的元素個數(shù))。

設(shè)是一個實數(shù)序列，并假設(shè)在這個序列中沒有長度為n+1的遞增子序列，則要證明一定有一個長度為n+1的遞減子序列。［例1］證明：令表示以為首項的最長遞增子序列的長度，，則對于每個，由假設(shè)知1≤≤n。即是說有個數(shù)都在1到n之間。由推論1知，在個數(shù)中必有r=n+1個數(shù)是相同的(∵)。

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

將兩個大小不一的圓盤分別分成200個相等的扇形。在大圓盤上任選取100個扇形染成紅色，另外的100個扇形染成藍(lán)色，并將小圓盤上的扇形任意染成紅色或藍(lán)色，然后將小圓盤放大圓盤上且中心重合時，轉(zhuǎn)動小圓盤可使其每一扇形都迭放于大圓盤的某一扇形內(nèi)證明：當(dāng)適當(dāng)轉(zhuǎn)動小圓盤可使迭放的扇形對中，同色者至少為100對。

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

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

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

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

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

都在1和153兩