畢業(yè)論文鴿巢原理在數(shù)學(xué)領(lǐng)域的應(yīng)用

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

2、出相關(guān)的計(jì)算公式.最后，我們進(jìn)一步認(rèn)識(shí)了鴿巢原理并得出其在諸多數(shù)學(xué)領(lǐng)域中都有重要的應(yīng)用.</p><p>　　【關(guān) 鍵 詞】 組合數(shù)學(xué) 鴿巢原理 </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 鴿巢公式及其性質(zhì)2</p&

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

8、;p>　　2.4 鴿巢原理在“人的相識(shí)”問(wèn)題上的應(yīng)用10</p><p>　　2.5 鴿巢原理在“染色問(wèn)題”上的應(yīng)用11</p><p>　　2.6數(shù)學(xué)競(jìng)賽中幾種常見(jiàn)的鴿巢類(lèi)型12</p><p><b>　　3 結(jié)束語(yǔ)14</b></p><p>　　參 考 文 獻(xiàn)15</p><p

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

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

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

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

13、含的元素個(gè)數(shù)，則至少存在某個(gè)集合，其包含的元素個(gè)數(shù).</p><p>　　證（用反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)都有，則因?yàn)槭钦麛?shù)，應(yīng)有，于是，這與題設(shè)矛盾.所以，至少有一個(gè)，即必有一個(gè)集合中含有兩個(gè)或兩個(gè)以上的元素.</p><p>　　形式二 把個(gè)元素劃分到個(gè)集合中，用表示這個(gè)集合對(duì)應(yīng)包含的元素個(gè)數(shù)，則至少存在某個(gè)集合，其包含的元素個(gè)數(shù).</p><p>　

14、　證（用反證法）假設(shè)結(jié)論不成立，即對(duì)每一個(gè)都有，則因?yàn)槭钦麛?shù)，應(yīng)有，于是，這與題設(shè)矛盾.所以，至少存在一個(gè).</p><p>　　形式三 設(shè)把個(gè)元素分為個(gè)集合，用表示這個(gè)集合里相應(yīng)的元素個(gè)數(shù)，則：至少存在某個(gè)都有.</p><p>　　證（用反證法）設(shè)結(jié)論不成立，即對(duì)每一個(gè)都有，于是，這與題設(shè)相矛產(chǎn)生矛盾.所以，必有一個(gè)集合中元素.</p><p>　　形式四 設(shè)把

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

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

17、智能中，很多原理和問(wèn)題可以用命題公式表示.這些公式在適當(dāng)變形其結(jié)構(gòu)后，就會(huì)出現(xiàn)很多有趣的性質(zhì)，比如極小不可滿(mǎn)足性、對(duì)稱(chēng)性、子結(jié)構(gòu)同構(gòu)性、消解難例等等.著名的鴿巢公式就來(lái)自于組合學(xué)中的鴿巢原理.鴿巢原理是指：只鴿子進(jìn)入個(gè)巢穴，必有一個(gè)巢穴至少有2只鴿子.我們引入變?cè)钢圾澴舆M(jìn)入號(hào)巢穴，那么鴿巢原理就能表示為 .</p><p>　　改寫(xiě)鴿巢原理的表示公式得到鴿巢公式：.</p><p>　　

18、在本公式中，符號(hào)是指任意一只鴿子，而是指全部所有的巢穴，是指否定，也就是不允許的意思.于是表示的是所有的只鴿子都要飛進(jìn)這個(gè)巢穴，中間的表示同時(shí)滿(mǎn)足，右邊則表示不允許兩只鴿子進(jìn)同一個(gè)巢穴.</p><p>　　性質(zhì) 是一個(gè)極小不可滿(mǎn)足公式.</p><p>　　證 （1）證明不可滿(mǎn)足.假設(shè)公式.</p><p>　　可滿(mǎn)足，則存在變?cè)仙系囊粋€(gè)真值指派，使得<

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

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

21、定.從中刪去子句后，得到公式： .</p><p>　　取一個(gè)真值指派如下：</p><p><b>　　.</b></p><p>　　我們有.直觀(guān)上，刪去子句后，允許號(hào)鴿子同時(shí)進(jìn)入號(hào)巢.于是，可以讓號(hào)鴿子進(jìn)號(hào)巢，.</p><p>　　綜上所述，是極小不可滿(mǎn)足公式.</p><p>

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

23、lt;/p><p>　?。?）;(為非空結(jié)點(diǎn)集合)</p><p>　　（2）對(duì)于邊集合中的任意一條邊，結(jié)點(diǎn)一個(gè)在中，另一個(gè)在中.</p><p>　　定義2 一個(gè)二分圖稱(chēng)為一個(gè)完全二分圖.如果對(duì)于中的每一個(gè)結(jié)點(diǎn)，中每一個(gè)結(jié)點(diǎn)，含有邊.如果，我們記完全二分圖為.</p><p>　　定義3 （1）命題變?cè)捌浞穸ńy(tǒng)稱(chēng)文字.</p>

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

25、果作為文字出現(xiàn)在子句中，稱(chēng)在中正出現(xiàn)；如果文字出現(xiàn)在子句中，稱(chēng)在中負(fù)出現(xiàn).我們可以用一個(gè)邊上帶正號(hào)或負(fù)號(hào)的二分圖表示一個(gè)公式如下：</p><p>　　設(shè)為一個(gè)含有個(gè)子句的公式，出現(xiàn)在公式中的變?cè)?</p><p>　　視的變?cè)蠟橐粋€(gè)結(jié)點(diǎn)集合(稱(chēng)為變?cè)Y(jié)點(diǎn)集).</p><p>　　引入一個(gè)結(jié)點(diǎn)集合對(duì)應(yīng)于的所有子句（稱(chēng)為子句結(jié)點(diǎn)集）.</p>

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

27、p>　　在圖1中，實(shí)線(xiàn)邊表示邊帶：號(hào)，虛線(xiàn)邊表示邊帶：號(hào).</p><p>　　然后介紹一般鴿巢公式——帶中介的鴿巢公式.現(xiàn)考慮在完全二分圖 （其中，）. 中的兩行結(jié)點(diǎn)之間插入一行新的中介結(jié)點(diǎn).</p><p>　　在的基礎(chǔ)上構(gòu)造一個(gè)完全三分圖，其中， .</p><p>　　直觀(guān)上，鴿子進(jìn)入巢穴要經(jīng)過(guò)一個(gè)“中間站”，

28、這就是“中介”的由來(lái).引入變?cè)獙?duì)應(yīng)于第號(hào)鴿子經(jīng)過(guò)號(hào)“中間站”進(jìn)入號(hào)巢.再引入帶中介的鴿巢原理：只鴿子飛進(jìn)個(gè)巢，其間有個(gè)中間站，鴿子必須經(jīng)過(guò)某一中間站才能進(jìn)巢，那么至少有兩只鴿子在巢中.上述原理可用用如下命題公式表示： .</p><p>　　對(duì)于我們認(rèn)為“號(hào)鴿子經(jīng)過(guò)號(hào)中間站進(jìn)號(hào)巢，而且號(hào)鴿子經(jīng)過(guò)號(hào)中間站進(jìn)號(hào)巢”與“號(hào)鴿子經(jīng)過(guò)號(hào)中間站進(jìn)號(hào)巢，而且號(hào)鴿子經(jīng)過(guò)號(hào)中間站進(jìn)號(hào)巢”的方式是相同的.于是，上述公式可以改寫(xiě)

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

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

31、.</p><p><b>　?。?lt;/b></p><p>　　，所以在同一個(gè)鴿巢里任意兩點(diǎn)間的距離均小于2.由鴿巢原理把10個(gè)點(diǎn)放入9個(gè)鴿巢，則必有兩點(diǎn)在同一鴿巢內(nèi)，這兩點(diǎn)的距離就小于2.</p><p>　　在幾何圖形上鴿巢原理的應(yīng)用相當(dāng)廣泛，以上只是列舉了一個(gè)較為常見(jiàn)的例子，在日常生活中還有很多可以用鴿巢原理來(lái)解決的問(wèn)題.在對(duì)一道題構(gòu)造鴿

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

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

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

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

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

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

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

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

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

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

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

43、識(shí)2個(gè)人，第3個(gè)人認(rèn)識(shí)4個(gè)人，以此類(lèi)推，第50個(gè)人認(rèn)識(shí)98個(gè)人.那么，在剩下的50個(gè)人中，如果已知有兩個(gè)人有相同的熟人，那么可以得到3個(gè)人認(rèn)識(shí)相同個(gè)數(shù)的人，問(wèn)題得證；如果不知道是否還有兩個(gè)人有相同個(gè)數(shù)的熟人，我們來(lái)做下面的假設(shè)：剩下的50個(gè)人也是依次認(rèn)識(shí)個(gè)人，那么結(jié)論無(wú)法證得.</p><p>　　根據(jù)上述的推導(dǎo)和假設(shè)，可以得出有兩個(gè)人認(rèn)識(shí)0個(gè)人，有兩個(gè)人認(rèn)識(shí)98個(gè)人.對(duì)于這兩個(gè)認(rèn)識(shí)0個(gè)人的人來(lái)說(shuō)，而對(duì)于那兩個(gè)認(rèn)

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

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

46、gt;　　例10 設(shè)在一個(gè)平面上有任意的六個(gè)點(diǎn)，并且三點(diǎn)不共線(xiàn)，每?jī)牲c(diǎn)用藍(lán)色或紅色的線(xiàn)段連起來(lái)，都連起來(lái)后．問(wèn)能否找到一個(gè)由這些線(xiàn)構(gòu)成的三角形，使三角形的三邊同色？</p><p><b>　　解</b></p><p>　　首先從這六個(gè)點(diǎn)中任意選中一點(diǎn)，接著連接這一點(diǎn)到其他五個(gè)點(diǎn)．如圖4，在五條線(xiàn)段中，至少有三條線(xiàn)段是同一種顏色，假定是紅色，這三條線(xiàn)段的另一端或許是

47、不同顏色，假設(shè)這三條線(xiàn)段（虛線(xiàn)）中其中一條是紅色的，那么這條紅色的線(xiàn)段和其他兩條紅色的線(xiàn)段便構(gòu)成了所需要的同色三角形．若這三條線(xiàn)段都是藍(lán)色的，那么這三條線(xiàn)段也組成我們所需要的同色三角形.因此無(wú)論怎樣著色，在這六點(diǎn)之間的所有線(xiàn)段中必能找到一個(gè)同色三角形.</p><p>　　2.6數(shù)學(xué)競(jìng)賽中幾種常見(jiàn)的鴿巢類(lèi)型</p><p>　　第一類(lèi) 有“鴿子”也有“巢”</p><p

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

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

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

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

52、原理，必須先要設(shè)計(jì)制造出鴿子和巢.</p><p>　　由題意作序列.因?yàn)椋?lt;/p><p>　　所以　　　　　　　　　　　　　　　　　　　　　　　①　　　　　　　　　　　　　　　　　　　　　</p><p><b>　?、?lt;/b></p><p><b>　?、?lt;/b></p>&l

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

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

55、可以去設(shè)計(jì)不同性質(zhì)的巢和鴿子，另一方面也可以利用有關(guān)知識(shí)對(duì)這些已有的鴿子和巢實(shí)行修改，使其能為解題服務(wù). </p><p><b>　　3 結(jié)束語(yǔ)</b></p><p>　　至此，我們知道，原來(lái)鴿巢原理不僅在我們所學(xué)習(xí)的組合數(shù)學(xué)中是重要的知識(shí)點(diǎn)，在其他的許多方面都是以它為基礎(chǔ)的．特別是在幾何圖形問(wèn)題的處理上，有著非常廣泛的應(yīng)用．</p><p&

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

57、原理解決問(wèn)題的關(guān)鍵是構(gòu)造“鴿巢”，因?yàn)橹挥邪选傍澇病贝_定了，才能明確“鴿子”的放置情況，所以在解題時(shí)，重點(diǎn)更是難點(diǎn)就是如何構(gòu)造“鴿巢”.</p><p>　　其實(shí)，鴿巢原理還不止以上的這些應(yīng)用，在解決一些非一一對(duì)應(yīng)的離散關(guān)系的充分性判別問(wèn)題上還有更為寬廣的應(yīng)用．</p><p>　　甚至可以毫不夸張的說(shuō)：無(wú)論哪一門(mén)基礎(chǔ)科學(xué)的近現(xiàn)代分支學(xué)科中，幾乎每一學(xué)科都離不開(kāi)鴿巢原理的相關(guān)基礎(chǔ)及應(yīng)用，由

58、此可見(jiàn)，鴿巢原理在未來(lái)更多的、即將產(chǎn)生的新的學(xué)科領(lǐng)域必然會(huì)有必不可少的應(yīng)用．</p><p><b>　　參 考 文 獻(xiàn)</b></p><p>　　[1](美)布魯?shù)?組合數(shù)學(xué)（原書(shū)第5版）.北京：機(jī)械工業(yè)出版社,2012.5,75-90</p><p>　　[2]（美）羅伯茨.應(yīng)用組合數(shù)學(xué)（原書(shū)第二版）.北京：機(jī)械工業(yè)出版社，2007.5,

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

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

61、合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，1999,83-97</p><p>　　[10]匡正.組合數(shù)學(xué)習(xí)題精解[M].哈爾濱：哈爾濱工業(yè)大學(xué)出版社，2005.9,40-61</p><p>　　[11]陳景林.抽屜原理及其應(yīng)用[J].天津：唐山師專(zhuān)學(xué)報(bào)，1999.9,69-84</p><p>　　[12]王元元，王慶瑞.組合數(shù)學(xué)理論與解題[M].上海：上?？茖W(xué)技術(shù)文獻(xiàn)出版