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

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

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

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

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

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

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

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

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

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