組合數(shù)學(xué)鴿巢原理

1、第1章 鴿巢原理鴿巢原理（又叫抽屜原理）指的是一件簡(jiǎn)單明了的事實(shí)：為數(shù)眾多的一群鴿子飛進(jìn)不多的巢穴里，則至少有一個(gè)巢穴飛進(jìn)了兩只或更多的鴿子。這個(gè)原理并無(wú)深?yuàn)W之處，其正確性也是顯而易見的，但利用它可以解決許多有趣的組合問(wèn)題，得到一些很重要的結(jié)論，它在數(shù)學(xué)的歷史上起了很重要的作用。1.1 鴿巢原理的簡(jiǎn)單形式鴿巢原理的簡(jiǎn)單形式可以描述為：定理1.1.1 如果把個(gè)物品放入個(gè)盒子中，那么至少有一個(gè)盒子中有兩個(gè)或更多的物品。證明 如果每個(gè)盒子中至多有一個(gè)物品，那么個(gè)盒子中至多有個(gè)物品，而我們共有個(gè)物品，矛盾。故定理成立。鴿巢原理只斷言存在一個(gè)盒子，該盒中有兩個(gè)或兩個(gè)以上的物品，但它并沒有指出是哪個(gè)盒子，

2、要想知道是哪一個(gè)盒子，則只能逐個(gè)檢查這些盒子。所以，這個(gè)原理只能用來(lái)證明某種安排的存在性，而對(duì)于找出這種安排卻毫無(wú)幫助。例1 共有12個(gè)屬相，今有13個(gè)人，則必有兩人的屬相相同。例2 在邊長(zhǎng)為1的正方形內(nèi)任取5點(diǎn)，則其中至少有兩點(diǎn)，它們之間的距離不超過(guò)。證明 把邊長(zhǎng)為1的正方形分成4個(gè)邊長(zhǎng)為的小正方形，如圖1.1.1所示，在大正方形內(nèi)任取5點(diǎn)，則這5點(diǎn)分別落在4個(gè)小正方形中。由鴿巢原理知，至少有兩點(diǎn)落在某一個(gè)小正方形中，從而這兩點(diǎn)間的距離小于或等于小正方形對(duì)角線的長(zhǎng)度。例3 給出個(gè)整數(shù)，證明：必存在整數(shù)，使得證明 構(gòu)造部分和序列則有如下兩種可能：（i）存在整數(shù)，使得，此時(shí)，取即滿足題意。（ii

3、）對(duì)任一整數(shù)i，均有，令，則有，這樣，個(gè)余數(shù)均在1到m-1之間。由鴿巢原理知，存在整數(shù)，使得。不妨設(shè)，則綜合（i）和（ii），即知題設(shè)結(jié)論成立。例4 一個(gè)棋手有11周時(shí)間準(zhǔn)備錦標(biāo)賽，他決定每天至少下一盤棋，一周中下棋的次數(shù)不能多于12次，證明：在此期間的連續(xù)一些天中他正好下棋21次。證明 令分別為這11周期間他每天下棋的次數(shù)，并作部分和根據(jù)題意，有且所以有（1.1.1）考慮數(shù)列它們都在1與之間，共有154項(xiàng)，由鴿巢原理知，其中必有兩項(xiàng)相等，由（1.1.1）式知這77項(xiàng)互不相等，從而這77項(xiàng)也互不相等，所以一定存在，使得因此這說(shuō)明從第天到第天這連續(xù)天中，他剛好下了21盤棋。例5 從1到200的所

4、有整數(shù)中任取101個(gè)，則這101個(gè)整數(shù)中至少有一對(duì)數(shù)，其中的一個(gè)一定能被另一個(gè)整除。證明 設(shè)是被選出的101個(gè)整數(shù)，對(duì)任一，都可以唯一地寫成如下的形式：，其中，為整數(shù)，為奇數(shù)。例如：由于，所以只能取1，3，5，199這100個(gè)奇數(shù)，而，共有101項(xiàng)，由鴿巢原理知，存在，使得不妨設(shè)，則整數(shù)即能被整除。從上面的幾個(gè)例子可以看出，盡管鴿巢原理很簡(jiǎn)單，但它卻能解決一些看似很復(fù)雜的組合問(wèn)題。在將其應(yīng)用到具體的組合問(wèn)題時(shí)，需要一定的技巧去構(gòu)造具體問(wèn)題中的“鴿子”與“鴿巢”。1.2 鴿巢原理的強(qiáng)形式定理1.2.1 設(shè)都是正整數(shù)，如果把個(gè)物品放入個(gè)盒子，那么或者第1個(gè)盒子至少包含個(gè)物品，或者第2個(gè)盒子至少包含

5、個(gè)物品，或者第個(gè)盒子至少包含個(gè)物品。證明 若對(duì)所有的，第個(gè)盒子至多只有個(gè)物品，則個(gè)盒子中至多有個(gè)物品，而我們現(xiàn)在有個(gè)物品，矛盾。故定理成立。在定理1.2.1中令，則變成了鴿巢原理的簡(jiǎn)單形式。在定理1.2.1中令，則得到如下的推論：推論1.2.1 若將個(gè)物品放入個(gè)盒子中，則至少有一個(gè)盒子中有個(gè)物品。推論1.2.1也可以敘述如推論1.2.2所描述的另一種形式：推論1.2.2 設(shè)是個(gè)整數(shù)，而且則中至少有一個(gè)數(shù)不小于。推1.2.3 若將個(gè)物品放入n個(gè)盒子中，則至少有一個(gè)盒子中有不少于個(gè)物品。其中，是不小于的最小整數(shù)。例1 設(shè)有大小兩只圓盤，每個(gè)都劃分成大小相等的200個(gè)小扇形，在大盤上任選100個(gè)小扇

6、形漆成黑色，其余的100個(gè)小扇形漆成白色，而將小盤上的200個(gè)小扇形任意漆成黑色或白色?，F(xiàn)將大小兩只圓盤的中心重合，轉(zhuǎn)動(dòng)小盤使小盤上的每個(gè)小扇形含在大盤上的小扇形之內(nèi)。證明：有一個(gè)位置使小盤上至少有100個(gè)小扇形同大盤上相應(yīng)的小扇形同色。證明 如圖1.2.1所示，使大小兩盤中心重合，固定大盤，轉(zhuǎn)動(dòng)小盤，則有200個(gè)不同的位置使小盤上的每個(gè)小扇形含在大盤上的小扇形中，由于大盤上的200個(gè)小扇形中有100個(gè)漆成黑色，100個(gè)漆成白色，所以小盤上的每個(gè)小扇形無(wú)論漆成黑色或白色，在200個(gè)可能的重合位置上恰好有100次與大盤上的小扇形同色，因而小盤上的200個(gè)小扇形在200個(gè)重合位置上共同色次，平均每

7、個(gè)位置同色次。由鴿巢原理知，存在著某個(gè)位置，使同色的小扇形數(shù)大于等于100個(gè)。例2 任意個(gè)實(shí)數(shù)（1.2.1）組成的序列中，必有一個(gè)長(zhǎng)為的非降子序列，或必有一個(gè)長(zhǎng)為的非升子序列。在證明本例之前先看一個(gè)具體的例子，對(duì)于序列從中可以選出幾個(gè)遞增子序列：也可以選出如下幾個(gè)遞減子序列：證明 方法1 假設(shè)長(zhǎng)為的實(shí)數(shù)序列（1.2.1）中沒有長(zhǎng)度為的非降子序列，下面證明其必有一長(zhǎng)度為的非升子序列。令表示從開始的最長(zhǎng)非降子序列的長(zhǎng)度，因?yàn)閷?shí)數(shù)序列（1.2.1）中沒有長(zhǎng)度為的非降子序列，所以有這相當(dāng)于把個(gè)物品放入個(gè)盒子1，2，n中，由鴿巢原理知，必有一盒子里面至少有個(gè)物品，即存在：及：。使得（1.2.2）對(duì)應(yīng)于這

8、些下標(biāo)的實(shí)數(shù)序列必滿足：（1.2.3）它們構(gòu)成一長(zhǎng)為的非增子序列。否則，若有某個(gè)，使得，那么由從開始的最長(zhǎng)非降子序列加上，就得到一個(gè)從開始的長(zhǎng)度為的非降子序列。由的定義知這與（1.2.2）式矛盾。因此（1.2.3）式成立，從而定理的結(jié)論成立。方法2 對(duì)應(yīng)于實(shí)數(shù)序列（1.2.1）中的每個(gè)，定義一個(gè)有序偶其中，為從開始的最長(zhǎng)非降子序列的長(zhǎng)度，為從開始的最長(zhǎng)非長(zhǎng)子序列的長(zhǎng)度，則對(duì)應(yīng)于序列（1.2.1），有以下的有序偶序列（1.2.4）若實(shí)數(shù)序列（1.2.1）中既沒有長(zhǎng)為的非升子序列，也沒有長(zhǎng)為的非降子序列，則有（1.2.5）滿足條件（1.2.5）的有序偶最多只有個(gè)，由鴿巢原理知，序列（1.2.4）中

9、至少有兩個(gè)有序偶相同。即存在，使得即不妨設(shè)，由方法1的分析知，若，則，與矛盾；若，則，與矛盾。所以，實(shí)數(shù)序列（1.2.1）中必有一長(zhǎng)為的非降子序列，或有一長(zhǎng)為的非升子序列。例3 將1到16的16個(gè)正整數(shù)任意分成三部分，其中必有一部分中的一個(gè)元素是某兩個(gè)元素之差（三個(gè)元素不一定互不相同）。證明 用反證法。設(shè)將1到16的16個(gè)整數(shù)任意分成和三個(gè)部分，若這三部分中無(wú)一具有問(wèn)題所指的性質(zhì)，即其中一個(gè)元素是其中某兩個(gè)元素之差，由此我們來(lái)導(dǎo)出矛盾，從而證明問(wèn)題的結(jié)論是正確的。（1）將1到16的整數(shù)任意分成三部分，由鴿巢原理知，其中必有一部分至少有個(gè)元素，不妨設(shè)中含有6個(gè)元素，為令，若A中存在一個(gè)元素是某兩個(gè)元素之差，則滿足問(wèn)題的要求。否則，令并令。顯然，即B中的元素仍是1到16的整數(shù)。根據(jù)假設(shè)，無(wú)一屬于。否則，與中不存在一元素等于某兩元素之差相矛盾。所以，B中元素屬于或（2）與（1）類似，不妨設(shè)B中至少個(gè)元素屬于，設(shè)為并令。由假設(shè)，C中不存在一元素是某兩個(gè)元素之差。令并令。顯然，D中元素不屬于，否則，與中不存在一元素是