1、 鴿籠原理的一般形式鴿籠原理的一般形式 在定理在定理2.12.1中，如果將中，如果將n+1n+1改寫成改寫成 于是定理于是定理2.12.1就可以敘述為：如果把就可以敘述為：如果把2+2+2-n+12+2+2-n+1個(gè)物體放入個(gè)物體放入n n個(gè)盒子中去，個(gè)盒子中去，則至少存在一個(gè)則至少存在一個(gè) ( =1,2,n)( =1,2,n)，使得第，使得第 個(gè)盒子中至少放有兩個(gè)物體。個(gè)盒子中至少放有兩個(gè)物體。i12221 nnni i我們?cè)O(shè)想，如果在我們?cè)O(shè)想，如果在2+2+2+ +2-n+12+2+2+ +2-n+1中中的第的第 個(gè)個(gè)2 2改為正整數(shù)改為正整數(shù) ( =1,2,( =1,2,，n)n)就得到

2、鴿籠原理的一般形式：就得到鴿籠原理的一般形式：定理定理2.22.2設(shè)設(shè) 是正整數(shù)是正整數(shù)( =1,2,( =1,2,，n),q -n+1,n),q -n+1,如果把如果把q q個(gè)個(gè)物體放入物體放入n n個(gè)盒子中去，則存在一個(gè)個(gè)盒子中去，則存在一個(gè) ，使得第使得第 個(gè)盒子中至少有個(gè)盒子中至少有個(gè)物體。個(gè)物體。 iqiiqinqqq 21iiiqi 用反證法。假設(shè)結(jié)論不成立，即用反證法。假設(shè)結(jié)論不成立，即對(duì)每一個(gè)對(duì)每一個(gè) , ,第第 個(gè)盒子至多放有個(gè)盒子至多放有 個(gè)物個(gè)物體體( )( )，從而這，從而這n n個(gè)盒子放入的個(gè)盒子放入的物體的總數(shù)為物體的總數(shù)為這與這與 矛盾，從矛盾，從而定理得證。而定

3、理得證。這樣一來(lái)，這樣一來(lái)，定理定理2.12.1是是定理定理2.22.2的特殊的特殊形式。形式。in1iiqn1) 1(21111 nqqqnqqnqnniiininii121 nqqqqn證明：證明：ii推論推論2 2 對(duì)于正整數(shù)對(duì)于正整數(shù) ，如果，如果 , ,至少存在一個(gè)至少存在一個(gè)i,i,使得使得m mi irr。),2 , 1(nimi1/1rnmnii 推論推論1 1 如果把如果把n(r-1)+1n(r-1)+1個(gè)物體放入個(gè)物體放入n n個(gè)盒個(gè)盒子中，則至少存在一個(gè)盒子放有不少于子中，則至少存在一個(gè)盒子放有不少于r r個(gè)個(gè)物體。物體。 設(shè)第設(shè)第 個(gè)盒子放有個(gè)盒子放有 個(gè)物體，由推個(gè)物

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

5、 是一個(gè)實(shí)數(shù)序列，并假設(shè)在這個(gè)序列中沒有長(zhǎng)度為n+1的遞增子序列，則要證明一定有一個(gè)長(zhǎng)度為n+1的遞減子序列。12n2121,na aa例例1 1證明：證明：令令 表示以表示以 為首項(xiàng)的最長(zhǎng)遞增子序列為首項(xiàng)的最長(zhǎng)遞增子序列的長(zhǎng)度，的長(zhǎng)度， ，則對(duì)于每，則對(duì)于每個(gè)個(gè) ，由假設(shè)知，由假設(shè)知1 n1 n。即是說(shuō)有即是說(shuō)有 個(gè)數(shù)個(gè)數(shù) 都在都在1 1到到n n之間。由推論之間。由推論1 1知，在知，在 個(gè)數(shù)中必有個(gè)數(shù)中必有r=n+1r=n+1個(gè)數(shù)是個(gè)數(shù)是相同的相同的( ) )。kmka1,2 , 12nk112nkkkm12n1, 212, nmmm1, 212,nmmm1) 1(12rnn 不妨設(shè)不妨

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

7、1iikkaa1ikaikaika1ikikmm1ikikmm121nkkkaaa 將兩個(gè)大小不一的圓盤分別分成將兩個(gè)大小不一的圓盤分別分成200200個(gè)相等的扇形。在大圓盤上任選取個(gè)相等的扇形。在大圓盤上任選取100100個(gè)扇形個(gè)扇形染成紅色，另外的染成紅色，另外的100100個(gè)扇形染成藍(lán)色，并將個(gè)扇形染成藍(lán)色，并將小圓盤上的扇形任意染成紅色或藍(lán)色，然后小圓盤上的扇形任意染成紅色或藍(lán)色，然后將小圓盤放大圓盤上且中心重合時(shí)，轉(zhuǎn)動(dòng)小將小圓盤放大圓盤上且中心重合時(shí)，轉(zhuǎn)動(dòng)小圓盤可使其每一扇形都迭放于大圓盤的某一圓盤可使其每一扇形都迭放于大圓盤的某一扇形內(nèi)證明：當(dāng)適當(dāng)轉(zhuǎn)動(dòng)小圓盤可使迭放的扇形內(nèi)證明：當(dāng)

8、適當(dāng)轉(zhuǎn)動(dòng)小圓盤可使迭放的扇形對(duì)中，同色者至少為扇形對(duì)中，同色者至少為100100對(duì)。對(duì)。 例例2 2故由故由推論推論1 1知，至少有一種小圓盤與大圓盤的知，至少有一種小圓盤與大圓盤的迭放可使迭放的扇形對(duì)中迭放可使迭放的扇形對(duì)中至少至少有有100100個(gè)同色的個(gè)同色的扇形對(duì)。扇形對(duì)。證明： 1. 1.首先將大圓盤固定不動(dòng)，則使小圓盤的首先將大圓盤固定不動(dòng)，則使小圓盤的每一扇形都迭放于大圓盤的一個(gè)扇形中有每一扇形都迭放于大圓盤的一個(gè)扇形中有200200種可種可能的位置能的位置( (將這將這200200種可能位置看作種可能位置看作200200個(gè)不同的盒個(gè)不同的盒子子) )。2.2.由于在這由于在這2

9、00200種可能位置中，小圓盤上的每一種可能位置中，小圓盤上的每一扇形都有扇形都有100100次配成同色的扇形對(duì)次配成同色的扇形對(duì)( (將同色的扇形將同色的扇形對(duì)看作放入盒子中的物體對(duì)看作放入盒子中的物體) )。因此這樣的扇形對(duì)一。因此這樣的扇形對(duì)一共有共有200200100100個(gè)。而個(gè)。而200200100200100200(100-1)+1(100-1)+1 解：解：設(shè)設(shè) 表示該圈上相鄰三數(shù)之和，這表示該圈上相鄰三數(shù)之和，這樣的和共有十個(gè)。而樣的和共有十個(gè)。而1,2,101,2,10中的每一個(gè)都出現(xiàn)中的每一個(gè)都出現(xiàn)在在 這十個(gè)和的三個(gè)之中。而這十個(gè)和的三個(gè)之中。而故由推論故由推論2 2知

10、，存在一個(gè)知，存在一個(gè) 使使 。(1,2,10)im i 1210,m mm1013(1210)/1016.517 110iim(1,2,10)i i 17im 如果將如果將1 1，2 2，1010隨機(jī)地?cái)[成一隨機(jī)地?cái)[成一圈，則必有某相鄰三數(shù)之和至少是圈，則必有某相鄰三數(shù)之和至少是1717例例3 3 解：解： 設(shè)設(shè) 為第一天該棋手下棋的盤數(shù)，為第一天該棋手下棋的盤數(shù)， 是是第一、二天該棋手下棋盤數(shù)的和，第一、二天該棋手下棋盤數(shù)的和， 是第一是第一、二、二、j j天該棋手下棋盤數(shù)的和，天該棋手下棋盤數(shù)的和，j=1,2,j=1,2,77,77，于是序列于是序列是嚴(yán)格遞增序列，且是嚴(yán)格遞增序列，且1a2aja7712,a aa1771,132aa 一棋手為參加一次錦標(biāo)賽要進(jìn)行一棋手為參加一次錦標(biāo)賽要進(jìn)行7777天的天的訓(xùn)練，如果他每天至少下一盤棋，且每周至多下訓(xùn)練，如果他每天至少下一盤棋，且每周至多下1212盤棋，試證明不管他怎樣安排，必存在相繼的盤棋，試證明不管他怎樣安排，必存在相繼的若干天，在這段時(shí)間中他恰好下棋若干天，在這段時(shí)間中他恰好下棋2121盤。盤。例例4 4 于是序列于是序列 也是也是嚴(yán)格遞增序列。而嚴(yán)格遞增序列。而 ，故，故154154個(gè)數(shù)個(gè)數(shù)都在都在1 1和和153153兩個(gè)整數(shù)之間，由鴿籠原理兩個(gè)整數(shù)之間，由鴿籠原理知，這知，這154154個(gè)數(shù)中必有兩個(gè)是相等的。