畢業(yè)論文鴿巢原理在數學領域的應用

1、<p>　　鴿巢原理在數學領域的應用</p><p><b>　　摘 要</b></p><p>　　組合數學是現(xiàn)代數學的重要分支，而鴿巢原理是組合數學中最基本最重要的概念之一，具有廣泛的應用價值. 本文首先介紹了鴿巢原理的定義及其相關的公式和性質.接著重點討論了鴿巢原理的應用，包括其在幾何圖形、數的整除、連續(xù)時間、人的相識和染色問題等領域的應用，并給

2、出相關的計算公式.最后，我們進一步認識了鴿巢原理并得出其在諸多數學領域中都有重要的應用.</p><p>　　【關 鍵 詞】 組合數學 鴿巢原理 </p><p>　　Application of the Pigeonhole Principle in the field of mathematics</p><p><b>　　Abstract</

3、b></p><p>　　Combinatorial mathematics is one of the important branches of modern mathematics, and the Pigeonhole Principle is a basic and most important theorem in combinatorial mathematics. In this paper

4、, we first introduce the definition and some properties of the Pigeonhole Principle, together with the relative functions. Then we mainly focus on the applications of the Pigeonhole Principle, such as its applications on

5、 geometric figures, divisible problems of numbers, continuous time, human knowledge, col</p><p>　　[Key words] combinatorial mathematics Pigeonhole Principle </p><p><b>　　目 錄</b&

6、gt;</p><p><b>　　引 言1</b></p><p>　　1 鴿巢原理的概念1</p><p><b>　　1.1定義1</b></p><p>　　1.2 鴿巢原理的一般表現(xiàn)形式1</p><p>　　1.3 鴿巢公式及其性質2</p&

7、gt;<p>　　1.4 帶中介的鴿巢公式及其性質4</p><p>　　2 鴿巢原理在多領域的應用7</p><p>　　2.1 鴿巢原理在幾何圖形方面的應用7</p><p>　　2.2 鴿巢原理在數的整除關系中的應用8</p><p>　　2.3 鴿巢原理在“連續(xù)時間”問題上的應用9</p><

8、;p>　　2.4 鴿巢原理在“人的相識”問題上的應用10</p><p>　　2.5 鴿巢原理在“染色問題”上的應用11</p><p>　　2.6數學競賽中幾種常見的鴿巢類型12</p><p><b>　　3 結束語14</b></p><p>　　參 考 文 獻15</p><p

9、><b>　　引 言</b></p><p>　　課桌上有八個蘋果，要把這八個蘋果放進七個抽屜中，無論怎樣放，我們會發(fā)現(xiàn)有一個抽屜里面至少有個蘋果，這一現(xiàn)象就是 “抽屜原理”. 抽屜原理的一般含義為：“如果每個抽屜代表一個集合，每一個蘋果就可以代表一個元素，假如有或多于個元素放到個集合中去，其中必定至少有一個集合里有兩個元素”.抽屜原理也被稱為“鴿巢原理”（如果有七個鴿籠，養(yǎng)鴿人

10、養(yǎng)了八只鴿子，那么當鴿子飛回籠中后，至少有一個籠子中裝有兩只鴿子”），它在組合數學中占據著非常重要的地位，常被用來證明一些關于存在性的數學問題.鴿巢原理不僅在組合數學的研究中起著關鍵作用，而且在求解幾何圖形、數的整除、連續(xù)時間、人的相識和染色問題等數學領域中都有著重要作用.</p><p><b>　　1 鴿巢原理的概念</b></p><p><b>　　

11、1.1定義</b></p><p>　　一般的鴿巢原理：個鴿巢，若有只鴿子在里面，則至少有一個鴿巢里至少有兩只鴿子.</p><p>　　推論1 只鴿子，個鴿巢，則至少有一個鴿巢里有不少于只鴿子.</p><p>　　推論 2 若有只鴿子飛進個鴿巢，則至少有一個鴿巢里有只鴿子.</p><p>　　推論3 如果有個整數的平均數大于

12、，</p><p>　　即，則中至少有一個整數不小于.</p><p>　　1.2 鴿巢原理的一般表現(xiàn)形式</p><p>　　抽屜原理是由數學家狄利克雷首先提出，并用于證明一些數論中的問題，因此，也被稱為狄利克雷原則.把鴿巢原理推廣到一般情形有以下幾種表現(xiàn)形式：</p><p>　　形式一 把個元素劃分到個集合中，用分別表示這個集合對應包

13、含的元素個數，則至少存在某個集合，其包含的元素個數.</p><p>　　證（用反證法）假設結論不成立，即對每一個都有，則因為是整數，應有，于是，這與題設矛盾.所以，至少有一個，即必有一個集合中含有兩個或兩個以上的元素.</p><p>　　形式二 把個元素劃分到個集合中，用表示這個集合對應包含的元素個數，則至少存在某個集合，其包含的元素個數.</p><p>　

14、　證（用反證法）假設結論不成立，即對每一個都有，則因為是整數，應有，于是，這與題設矛盾.所以，至少存在一個.</p><p>　　形式三 設把個元素分為個集合，用表示這個集合里相應的元素個數，則：至少存在某個都有.</p><p>　　證（用反證法）設結論不成立，即對每一個都有，于是，這與題設相矛產生矛盾.所以，必有一個集合中元素.</p><p>　　形式四 設把

15、個元素分為個集合，用表示這個集合里相應的元素個數，則：至少存在某個，使得.</p><p>　　證（用反證法） 設結論不成立，即對任意的都有，因為為整數，應有</p><p><b>　　，，</b></p><p>　　這與題設發(fā)生矛盾.所以，假設不成立，故必有一個，在第個集合中元素.</p><p>　　形式五 令

16、無窮多個元素分成有窮多個集合，則至少存在一個集合，它含有無窮多個元素.</p><p>　　證 （用反證法）將無限多個元素劃分至有限個集合，先假設這有限個集合中元素的個數全是有限個，那么有限個有限數相加之和必是有限數，這就與題設發(fā)生矛盾，因此假設不成立，故必有一個集合含有無窮多個元素.</p><p>　　1.3 鴿巢公式及其性質</p><p>　　在組合學和人工

17、智能中，很多原理和問題可以用命題公式表示.這些公式在適當變形其結構后，就會出現(xiàn)很多有趣的性質，比如極小不可滿足性、對稱性、子結構同構性、消解難例等等.著名的鴿巢公式就來自于組合學中的鴿巢原理.鴿巢原理是指：只鴿子進入個巢穴，必有一個巢穴至少有2只鴿子.我們引入變元指只鴿子進入號巢穴，那么鴿巢原理就能表示為 .</p><p>　　改寫鴿巢原理的表示公式得到鴿巢公式：.</p><p>　　

18、在本公式中，符號是指任意一只鴿子，而是指全部所有的巢穴，是指否定，也就是不允許的意思.于是表示的是所有的只鴿子都要飛進這個巢穴，中間的表示同時滿足，右邊則表示不允許兩只鴿子進同一個巢穴.</p><p>　　性質 是一個極小不可滿足公式.</p><p>　　證 （1）證明不可滿足.假設公式.</p><p>　　可滿足，則存在變元集合上的一個真值指派，使得<

19、/p><p><b>　?。?.1）對每個.</b></p><p>　　（1.2）對每對以及每個</p><p>　　由（1.1），對每個，存在某個，使得.由鴿巢原理：存在某對以及某個，使得.這與情形（1.2）矛盾.</p><p>　?。?）證明極小不可滿足.即證明：從中刪去一個子句后，得到的公式可滿足.分兩種情形討論：

20、</p><p>　　情形1 對某個.從中刪去子句后，得到公式：取一個真值指派如下：</p><p><b>　　.</b></p><p>　　我們有.直觀上，刪子句后，號鴿子可以不進巢，于是，可以讓號鴿子進號巢，.</p><p>　　情形2 對某對及某個.</p><p>　　不失一般性，假

21、定.從中刪去子句后，得到公式： .</p><p>　　取一個真值指派如下：</p><p><b>　　.</b></p><p>　　我們有.直觀上，刪去子句后，允許號鴿子同時進入號巢.于是，可以讓號鴿子進號巢，.</p><p>　　綜上所述，是極小不可滿足公式.</p><p>

22、;　　1.4 帶中介的鴿巢公式及其性質</p><p>　　鴿巢公式的一個真值指派可以用一個邊帶標記的完全二分圖表示. 現(xiàn)插入一中介結點集合于完全二分圖中，即可將鴿巢公式推廣到帶中介的情形, 繼而形成了一種新的消解難例公式，也就是帶中介的鴿巢公式.</p><p>　　首先引入二分圖的概念：</p><p>　　定義1 一個無向圖稱為一個二分圖.如果下列條件成立：&

23、lt;/p><p>　?。?）;(為非空結點集合)</p><p>　?。?）對于邊集合中的任意一條邊，結點一個在中，另一個在中.</p><p>　　定義2 一個二分圖稱為一個完全二分圖.如果對于中的每一個結點，中每一個結點，含有邊.如果，我們記完全二分圖為.</p><p>　　定義3 （1）命題變元及其否定統(tǒng)稱文字.</p>

24、<p>　?。?）一個子句是若干個文字的析取.子句可以視為一個文字的集合.</p><p>　?。?）是若干個子句的合取.公式可看作是一個子句的集合，或者是一個子句表.</p><p>　　定義4 設是一個公式.稱是極小不可滿足公式（簡稱為公式），如果不可滿足，并且從中刪去任意一個子句后得到的公式可滿足.</p><p>　　假定是一個變元，是一個子句.如

25、果作為文字出現(xiàn)在子句中，稱在中正出現(xiàn)；如果文字出現(xiàn)在子句中，稱在中負出現(xiàn).我們可以用一個邊上帶正號或負號的二分圖表示一個公式如下：</p><p>　　設為一個含有個子句的公式，出現(xiàn)在公式中的變元集合.</p><p>　　視的變元集合為一個結點集合(稱為變元結點集).</p><p>　　引入一個結點集合對應于的所有子句（稱為子句結點集）.</p>

26、<p><b>　　定義邊集合.</b></p><p>　　定義邊集合上的標記函數</p><p><b>　　.</b></p><p>　　于是，我們可以用一個邊帶標記的二分圖表示一個公式.</p><p>　　例如：公式可以用如下帶標記的二分圖表示.</p><

27、p>　　在圖1中，實線邊表示邊帶：號，虛線邊表示邊帶：號.</p><p>　　然后介紹一般鴿巢公式——帶中介的鴿巢公式.現(xiàn)考慮在完全二分圖 （其中，）. 中的兩行結點之間插入一行新的中介結點.</p><p>　　在的基礎上構造一個完全三分圖，其中， .</p><p>　　直觀上，鴿子進入巢穴要經過一個“中間站”，

28、這就是“中介”的由來.引入變元對應于第號鴿子經過號“中間站”進入號巢.再引入帶中介的鴿巢原理：只鴿子飛進個巢，其間有個中間站，鴿子必須經過某一中間站才能進巢，那么至少有兩只鴿子在巢中.上述原理可用用如下命題公式表示： .</p><p>　　對于我們認為“號鴿子經過號中間站進號巢，而且號鴿子經過號中間站進號巢”與“號鴿子經過號中間站進號巢，而且號鴿子經過號中間站進號巢”的方式是相同的.于是，上述公式可以改寫

29、成： .</p><p>　　由此，我們引入帶中介的鴿巢公式如下：.</p><p>　　類似于鴿巢公式，其中，，與前面一節(jié)里的意義相同，而且我們也有如下性質 對于，公式是極小不可滿足公式，證明過程與上節(jié)類似.</p><p>　　2 鴿巢原理在多領域的應用</p><p>　　2.1 鴿巢原理在幾何圖形方面的應用</p>

30、;<p>　　例1 在直徑為5的圓內任意給定10個點.證明：存在兩個點，它們之間的距離小于2.</p><p><b>　　證</b></p><p>　　我們先把圓平均劃分成8個相等的扇形，接著以圓的中心作為一個圓心，以0.9為半徑畫一個小圓，讓該小圓作為一個鴿巢，余下的部分均勻分成8等份，作為8個鴿巢，如圖2表示，總共有9個鴿巢.弧長，從而弧長小于2

31、.</p><p><b>　?。?lt;/b></p><p>　　，所以在同一個鴿巢里任意兩點間的距離均小于2.由鴿巢原理把10個點放入9個鴿巢，則必有兩點在同一鴿巢內，這兩點的距離就小于2.</p><p>　　在幾何圖形上鴿巢原理的應用相當廣泛，以上只是列舉了一個較為常見的例子，在日常生活中還有很多可以用鴿巢原理來解決的問題.在對一道題構造鴿

32、巢時，也不僅僅只有一種構造方法．只有更多地接觸不同形式的問題和應用，不斷的去構造和探索，才能靈活使用鴿巢原理.</p><p>　　2.2 鴿巢原理在數的整除關系中的應用</p><p>　　例3 證明：任意5個整數中，必有3個整數的和是3的倍數.</p><p>　　證 任意的整數除以3的余數只能是0,1,2.若所給出的5個整數除以3所得的余數中0,1,2都出現(xiàn)，

33、則那些余數分別是0,1,2的三個數的和就必定能被3整除．如果余數中至多出現(xiàn)0,1,2中的任意兩個，那可由鴿巢原理，其中必有一個余數至少出現(xiàn)三次，于是這余數相同的三個數的和一定可以被3整除. </p><p>　　例4 證明：對任意給定的52個整數，存在其中的兩個整數，要么兩者的差能被100整除，要么兩者的和能被100整除.</p><p>　　證 任意一個整數a被100整除產生的余數無非是

34、.題目中的52個整數除以100則產生52個余數.</p><p>　　若這52個余數中有兩個余數相等，即，那么一定有能被100整除，即存在兩個數，它們的差能被100整除.</p><p>　　若這52個余數均不相等，我們現(xiàn)在對這100個數來構造鴿巢，將相加之和為100的兩個數放在同一個鴿巢里.構造出來的51個鴿巢如下：</p><p>　　因為有52個不同的余數，根

35、據鴿巢原理，必有兩個余數來自于同一鴿巢，這只能從前49個鴿巢中取出.然而不論從哪個鴿巢里取，同一個鴿巢里的兩個余數之和一定是100，那么必有產生這兩個余數的兩個整數之和能被100整除.</p><p>　　例5 在前12個自然數中任取7個數，一定存在兩個數，其中的一個數是另一個數的整數倍.</p><p>　　分析 如果把前12個自然數劃分成6個集合，即構建6個鴿巢，并且使每個鴿巢內只有一

36、個數；或有任意的兩個數，其中的一個是另一個的整數倍.那么如何對這12個自然數進行分組？我們知道，一個自然數，它要么是奇數，要么是偶數.若是偶數，我們只能把它表達為奇數與的乘積的形式.這樣，如果上述表達式中的因子的指數允許等于0，那么每個自然數都可以表達成“奇數”的形式，于是這12個自然數就能用上述表達式表達出來，同時把式中“奇數”部分相同的自然數作為一組，構成一個鴿巢.</p><p>　　證 把前12個自然數

37、劃分為如下六個鴿巢：</p><p>　　顯然，上述六個鴿巢內的任意兩個鴿巢無公共元素，且.由鴿巢原理，從前12個自然數中任意中取出7個數，則必定存在兩個數同在或或鴿巢里，那么這兩個數之間存在倍數關系，即一個數是另一個數的整數倍.</p><p>　　2.3 鴿巢原理在“連續(xù)時間”問題上的應用</p><p>　　例5 某廠在五年期間的每一個月里至少試制一種新產品，

38、每年最多試制19種新產品.試證明：一定存在連續(xù)的幾個月，恰好試制24種新產品.</p><p>　　證　設該廠在這五年期間各個月試制的新產品的個數分別為，由題意，構造出數列的前n項和的數列,</p><p><b>　?。?lt;/b></p><p>　　而序列也是一個嚴格遞增序列：．</p><p>　　于是，這120個自

39、然數和都在區(qū)間內.在內，只有119個自然數，根據鴿巢原理，必定存在兩個數相等.上述兩個數列又分別是嚴格單調的，因此必然存在一個和j，使得.從而，該廠在從第個月起到第個月的這幾個月時間里，恰好試制了24種新產品.</p><p>　　例6 一個孩子每天至少看一個小時電視，總共看7周，但是每周看電視從不超過11小時.證明存在連續(xù)若干天在此期間這個孩子恰好看電視20個小時.（假設這個孩子每天看電視時間為整數個小時）&l

40、t;/p><p>　　證　設這個孩子7周內每天看電視的時間分別為，現(xiàn)在構造出數列的前n項和的數列，則有：，而序列也是一個嚴格遞增序列： 于是，這98個自然數和都在區(qū)間內.而在內，只有97個自然數，根據鴿巢原理，必定存在兩個數相等.而上述兩個數列又分別是嚴格單調的，因此必然存在一個和，使得.從而，這個孩子在第天起到第天的時間里，恰好看電視20個小時.</p><p>　　2.4 鴿巢原理在“人的

41、相識”問題上的應用</p><p>　　例7 證明在一群個人中，存在兩個人，他們在這群人中有相同個數的熟人. </p><p>　　證　在個人中，每個人所認識的人數只能是.若有兩個人認識的人數相等，那么問題已經得證.</p><p>　　由于某人認識個人的情況與另一個人認識0個人的情況不可能同時發(fā)生，那么這個人所能認識的人數也不可能同時存在，即最多只能存在種情況，我

42、們把它看成個鴿巢，根據鴿巢原理，個元素放進個鴿巢，則一定有兩個元素在同一鴿巢內，即有兩個人所認識的人數相等.</p><p>　　例8 在某次100人的聚會中，每個人都有偶數個（有可能是0個）熟人，證明：在這次聚會上存在3個人有相同的熟人.</p><p>　　證　由題意可知，每個人所能認識的人數可能為：.在這個100人的聚會中，如果50種情況都出現(xiàn)，我們假設第1個人認識0個人，第2個人認

43、識2個人，第3個人認識4個人，以此類推，第50個人認識98個人.那么，在剩下的50個人中，如果已知有兩個人有相同的熟人，那么可以得到3個人認識相同個數的人，問題得證；如果不知道是否還有兩個人有相同個數的熟人，我們來做下面的假設：剩下的50個人也是依次認識個人，那么結論無法證得.</p><p>　　根據上述的推導和假設，可以得出有兩個人認識0個人，有兩個人認識98個人.對于這兩個認識0個人的人來說，而對于那兩個認

44、識98個人的人來說，只能有一個人他們不認識，這就與有兩個人都不認識他們產生矛盾，所以不可能出現(xiàn)兩個認識0個人的人和兩個認識98個人的人同時存在的情況，故假設不成立. 因此剩下的50個人中，最多只能出現(xiàn)認識個人這50種情況的49種.最后再由鴿巢原理，必然有一種情況要重復.故一共存在3個人有相同個數的熟人.</p><p>　　2.5 鴿巢原理在“染色問題”上的應用</p><p&g

45、t;　　例9 有5個小孩，每人都從裝有若干黑白小球的不透明袋中任意摸出3個小球.證明：這5個人中至少有兩個小孩摸出的小球的顏色的配組是一樣的.</p><p>　　證　首先要確定3個小球的顏色有多少種不同的情況，可以有：3白，1黑2白，2黑1白，3黑共四種配組情況，不妨看作4只鴿巢.根據鴿巢原理，至少有兩個小孩摸出的小球的顏色在同一鴿巢里，也就是他們所拿小球的顏色配組是一樣的.</p><p&

46、gt;　　例10 設在一個平面上有任意的六個點，并且三點不共線，每兩點用藍色或紅色的線段連起來，都連起來后．問能否找到一個由這些線構成的三角形，使三角形的三邊同色？</p><p><b>　　解</b></p><p>　　首先從這六個點中任意選中一點，接著連接這一點到其他五個點．如圖4，在五條線段中，至少有三條線段是同一種顏色，假定是紅色，這三條線段的另一端或許是

47、不同顏色，假設這三條線段（虛線）中其中一條是紅色的，那么這條紅色的線段和其他兩條紅色的線段便構成了所需要的同色三角形．若這三條線段都是藍色的，那么這三條線段也組成我們所需要的同色三角形.因此無論怎樣著色，在這六點之間的所有線段中必能找到一個同色三角形.</p><p>　　2.6數學競賽中幾種常見的鴿巢類型</p><p>　　第一類 有“鴿子”也有“巢”</p><p

48、>　　例11 柜子里有5雙不同的鞋子，從中取出6只，則其中必有2只是完全配對的.</p><p>　　從例11中可以看出，每取出一只鞋，就是一只“鴿子”，一雙鞋就是一個“巢”.這是一個簡單的鴿巢原理.</p><p>　　第二類 只見“鴿子”不見“巢”</p><p>　　例12 任取11個整數，求證其中至少有兩個數它們的差是10的倍數.</p>

49、;<p>　　這個問題中，任取的11個整數就是11只鴿子，但是這些鴿子朝什么巢飛呢？題中沒有直接的答案.因此，設計建造巢是解答這類問題的當務之急.我們可以從結論出發(fā)，找出怎樣的“兩數差”是10的倍數和已有的鴿子來設計巢，只要這兩個數的個位數字相同，則它們的差就是10的倍數.而一個整數的個位數字只可能是0,1，…，9中的任意一個.因此我們可以設計這樣10個巢——個位數字是0為一個巢，……，個位數字是9的為一個巢.這樣就形成了

50、10個巢，11只鴿子的局面.問題就基本解決了.</p><p>　　第三類 不見“鴿子”只見“巢”</p><p>　　例13 15個奇數和15個偶數組成一個數列，從這個數列中任取16個數，則這16個數中至少有一對數，其中一個數是另一個數的倍數.</p><p>　　解　由結論，使我們想到任意一個正整數都可以寫成形式，其中，P是奇數.對于兩個數和只要，那么其中一個

51、一定是另一個的倍數.因此給出的15個奇數可以看成是15個巢.另外把任意取出的16個數都表示成的形式，設這16個數為，從而得到了由奇數組成的16只鴿子：.由鴿巢原理中至少有兩個是相同的.不妨設則有，若，那么是的倍數，否則是的倍數.</p><p>　　第四類 不見“鴿子”不見“巢”</p><p>　　例14 設是一個正整數列，滿足.則至少存在一對整數和 ，使得．這個鴿巢問題無法直接利用鴿巢

52、原理，必須先要設計制造出鴿子和巢.</p><p>　　由題意作序列.因為，</p><p>　　所以　　　　　　　　　　　　　　　　　　　　　　?、佟　　　　　　　　　　　　　　　　　　　　?lt;/p><p><b>　?、?lt;/b></p><p><b>　?、?lt;/b></p>&l

53、t;p>　?、凼怯?4項組成的序列，我們可以把每一項看作一只鴿子，共有24只鴿子，再考慮條件，由已知可得所以③中最大的項，因此，③是由1到23之間的整數組成的共有24項的一個序列.而1到23 這二十三個數可以看作23個巢.由鴿巢原理，其中至少有兩項相等（由同一個整數組成）.但因①和②至少存在一對整數n和k，滿足關系，即，所以.</p><p>　　由此，我們可以歸納出鴿巢解題策略：從解題方法和解題過程看，解

54、答第一類問題的關鍵是能否在問題中正確地找出鴿子和巢.一般先找到巢，再找鴿子；解答第二類問題的關鍵是能否根據鴿子的去向，即問題的結論，正確地設計建造巢；解答第三類問題的關鍵是根據巢的特點和問題的性質正確設計鴿子，使鴿子能飛入巢并發(fā)揮作用；解答第四類問題的關鍵是根據問題的特性，先制造出巢，把問題轉化為第三類問題，或先設計粗鴿子，把問題轉化為第二類問題.另外，在解答鴿巢問題時解題技巧也是相當重要的.在你開始設計鴿子，巢不能為解題服務時，一方面

55、可以去設計不同性質的巢和鴿子，另一方面也可以利用有關知識對這些已有的鴿子和巢實行修改，使其能為解題服務. </p><p><b>　　3 結束語</b></p><p>　　至此，我們知道，原來鴿巢原理不僅在我們所學習的組合數學中是重要的知識點，在其他的許多方面都是以它為基礎的．特別是在幾何圖形問題的處理上，有著非常廣泛的應用．</p><p&

56、gt;　　由上面應用可以看出，鴿巢原理雖然不是非常復雜，但應用鴿巢原理解題技巧卻很多.我們解題時要注意以下問題：</p><p>　?。?）題目中給出的“鴿子”具有任意性，分類也是任意的，所以不能用“鴿子”的一種特殊布局來代替元素的任意放置.</p><p>　?。?）用鴿巢原理解決的僅僅是存在性問題，無需考慮存在地點、存在多少.</p><p>　　（3）運用鴿巢

57、原理解決問題的關鍵是構造“鴿巢”，因為只有把“鴿巢”確定了，才能明確“鴿子”的放置情況，所以在解題時，重點更是難點就是如何構造“鴿巢”.</p><p>　　其實，鴿巢原理還不止以上的這些應用，在解決一些非一一對應的離散關系的充分性判別問題上還有更為寬廣的應用．</p><p>　　甚至可以毫不夸張的說：無論哪一門基礎科學的近現(xiàn)代分支學科中，幾乎每一學科都離不開鴿巢原理的相關基礎及應用，由

58、此可見，鴿巢原理在未來更多的、即將產生的新的學科領域必然會有必不可少的應用．</p><p><b>　　參 考 文 獻</b></p><p>　　[1](美)布魯迪.組合數學（原書第5版）.北京：機械工業(yè)出版社,2012.5,75-90</p><p>　　[2]（美）羅伯茨.應用組合數學（原書第二版）.北京：機械工業(yè)出版社，2007.5,

59、67-81</p><p>　　[3]（美）Ralph.離散與組合數學.北京：科學出版社,2012,7,100-132</p><p>　　[4]單墫.組合幾何.合肥：中國科學技術大學出版社，2011,12,55-70</p><p>　　[5]何春，萬琳等.鴿巢原理及其應用[J].計算機與數字工程，2007.8,95-103</p><p>

60、;　　[6]肖美英.抽屜原理及其應用[J].晉中師專學報，1999.21（5）</p><p>　　[7]盧開澄，盧華明燈.組合數學（第三版）[M].北京：清華大學出版社，2002,120-145</p><p>　　[8]蘭社云，高喜梅.淺談抽屜原理及抽屜構造[J].河南：河南教育學院學報，2003.6</p><p>　　[9]孫淑玲，許胤龍.組合數學論[M].

61、合肥：中國科學技術大學出版社，1999,83-97</p><p>　　[10]匡正.組合數學習題精解[M].哈爾濱：哈爾濱工業(yè)大學出版社，2005.9,40-61</p><p>　　[11]陳景林.抽屜原理及其應用[J].天津：唐山師專學報，1999.9,69-84</p><p>　　[12]王元元，王慶瑞.組合數學理論與解題[M].上海：上海科學技術文獻出版