鴿籠原理畢業(yè)論文經(jīng)典

1、材材 料料 清清 單單一、畢業(yè)論文二、畢業(yè)設(shè)計(jì)任務(wù)書三、畢業(yè)設(shè)計(jì)開題申請(qǐng)表四、畢業(yè)設(shè)計(jì)開題報(bào)告正文聲聲 明明本人 豐海娟 ，學(xué)號(hào)10505039，系數(shù)學(xué)與應(yīng)用數(shù)學(xué)學(xué)院數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)1001班學(xué)生。所做論文內(nèi)容主體均為原創(chuàng)，無任何抄襲、剽竊他人勞動(dòng)成果的行為。如有發(fā)現(xiàn)此類行為，本人愿意為此承擔(dān)一切道義及法律責(zé)任，特此聲明。學(xué)生簽名： 年 月 日 抽屜原理及其應(yīng)用抽屜原理及其應(yīng)用姓名： 專業(yè)：數(shù)學(xué)與應(yīng)用數(shù)學(xué) 學(xué)號(hào)：指導(dǎo)老師：摘摘 要：要：抽屜原理是數(shù)學(xué)中的重要原理抽屜原理是數(shù)學(xué)中的重要原理, ,在解決數(shù)學(xué)問題時(shí)有非常重要的作用在解決數(shù)學(xué)問題時(shí)有非常重要的作用. .各種形式的抽屜原理在高等數(shù)學(xué)和

2、初等數(shù)學(xué)中經(jīng)常被采用各種形式的抽屜原理在高等數(shù)學(xué)和初等數(shù)學(xué)中經(jīng)常被采用. .本文著重從抽屜的本文著重從抽屜的1構(gòu)造方法：構(gòu)造方法：等分區(qū)間、分割圖形、利用等分區(qū)間、分割圖形、利用“對(duì)稱性對(duì)稱性” 、 用整數(shù)用整數(shù)性質(zhì)、利用染色和根據(jù)問題的需要性質(zhì)、利用染色和根據(jù)問題的需要闡述抽屜原理在高等數(shù)學(xué)和闡述抽屜原理在高等數(shù)學(xué)和初等數(shù)學(xué)（競(jìng)賽題）中的應(yīng)用初等數(shù)學(xué)（競(jìng)賽題）中的應(yīng)用, ,同時(shí)指出了它在應(yīng)用領(lǐng)域中的不同時(shí)指出了它在應(yīng)用領(lǐng)域中的不足之處足之處: :抽屜的構(gòu)造有一定的難度抽屜的構(gòu)造有一定的難度, ,這就要求我們必須要求有一這就要求我們必須要求有一定的數(shù)學(xué)功底定的數(shù)學(xué)功底, ,甚至復(fù)雜的需要大量的

3、演算甚至復(fù)雜的需要大量的演算, ,因此抽屜原理不能因此抽屜原理不能充分的運(yùn)用到我們?nèi)粘Ｉ钪腥コ浞值倪\(yùn)用到我們?nèi)粘Ｉ钪腥? .關(guān)鍵詞關(guān)鍵詞 ：抽屜原理：抽屜原理; ;高等數(shù)學(xué)高等數(shù)學(xué); ; 初等數(shù)學(xué)初等數(shù)學(xué) The principle of drawer and its applicationAbstract：Drawer principle is the important principle of mathematics in solving mathematical problems, has a very important role. All forms of drawer pri

4、nciple in Higher Mathematics and elementary mathematics is often used. This article emphatically from the drawer construction methods: equal interval, segmentation graph, using the symmetry, with properties of the integers, using staining and according to problems on the drawer principle in Higher M

5、athematics and Elementary Mathematics ( contest ) application, and points out that it is in the field of application of the deficiencies: drawer structure has certain difficulty, this asks we must have some math skills, even complex requires a large amount of calculation, therefore the drawer princi

6、ple can not full use of our daily life. Key Words：the principle of drawer; advanced mathematics; primary mathematics2目目 錄錄1抽屜原理抽屜原理.11.1 抽屜原理的簡(jiǎn)單形式.11.2 抽屜原理的加強(qiáng)形式.22抽屜原理的應(yīng)用抽屜原理的應(yīng)用.42.1 抽屜的構(gòu)造.42.2 抽屜原理在數(shù)學(xué)解題中的應(yīng)用.103.抽屜原理在生活中的應(yīng)用抽屜原理在生活中的應(yīng)用 143.1 月黑穿襪子.143.2 手指紋和頭發(fā).143.3 電腦算命.154總結(jié)總結(jié).15參考文獻(xiàn)參考文獻(xiàn).16致致 謝謝 .

7、17前言前言 抽屜原理又叫做鴿巢原理，指的是一件簡(jiǎn)單明了的事實(shí)：為數(shù)抽屜原理又叫做鴿巢原理，指的是一件簡(jiǎn)單明了的事實(shí)：為數(shù)眾多的鴿子飛進(jìn)為數(shù)不多的巢穴里，則至少有一個(gè)巢穴飛進(jìn)了兩只眾多的鴿子飛進(jìn)為數(shù)不多的巢穴里，則至少有一個(gè)巢穴飛進(jìn)了兩只或者更多的鴿子。其實(shí)有關(guān)于抽屜原理（鴿巢原理）的闡釋，粗略或者更多的鴿子。其實(shí)有關(guān)于抽屜原理（鴿巢原理）的闡釋，粗略3的說就是如果有許多物體放進(jìn)不足夠多的盒子內(nèi)，那么至少有一個(gè)的說就是如果有許多物體放進(jìn)不足夠多的盒子內(nèi)，那么至少有一個(gè)盒子被兩個(gè)或多個(gè)盒子占據(jù)。抽屜原理在我們?nèi)粘Ｉ钪幸呀?jīng)運(yùn)用盒子被兩個(gè)或多個(gè)盒子占據(jù)。抽屜原理在我們?nèi)粘Ｉ钪幸呀?jīng)運(yùn)用的比較廣泛了

8、的比較廣泛了,它往往和我們數(shù)學(xué)結(jié)合在一起為我們?nèi)粘Ｉ顜砹怂臀覀償?shù)學(xué)結(jié)合在一起為我們?nèi)粘Ｉ顜砹瞬恍〉谋憷Ｎ覍⒅饕獢⑹鲆幌鲁閷显淼木唧w的形式、構(gòu)造方法不小的便利。我將主要敘述一下抽屜原理的具體的形式、構(gòu)造方法以及他在我們生活中的一些具體的應(yīng)用。希望大家能對(duì)抽屜原理有以及他在我們生活中的一些具體的應(yīng)用。希望大家能對(duì)抽屜原理有一個(gè)更加清晰的了解并能運(yùn)用到我們的日常生活中去。一個(gè)更加清晰的了解并能運(yùn)用到我們的日常生活中去。1.1.1.1.抽屜原理的簡(jiǎn)單形式抽屜原理的簡(jiǎn)單形式 抽屜原理的最簡(jiǎn)單的形式如下定理定理 1 1鴿巢原理鴿巢原理( (組合數(shù)學(xué)組合數(shù)學(xué),) )如果如果個(gè)物體放進(jìn)個(gè)物體

9、放進(jìn)個(gè)盒子，那么至少有個(gè)盒子，那么至少有1nn一個(gè)盒子包含兩個(gè)或更多的物體一個(gè)盒子包含兩個(gè)或更多的物體證明證明：（用反證法）如果：（用反證法）如果個(gè)盒子中每個(gè)盒子至多放一個(gè)物體，則放入個(gè)盒子中每個(gè)盒子至多放一個(gè)物體，則放入個(gè)個(gè)nn盒子中的物體總數(shù)至多為盒子中的物體總數(shù)至多為個(gè)這與假設(shè)有個(gè)這與假設(shè)有個(gè)物體矛盾從而定理得證個(gè)物體矛盾從而定理得證n1n注意，無論是抽屜原理還是它的證明，對(duì)于找出含有兩個(gè)或更多物體的盒子都沒有任何幫助我們只是簡(jiǎn)單斷言，如果人們檢查每一個(gè)盒子，那么他們會(huì)發(fā)現(xiàn)有的盒子，里面放有多于一個(gè)的物體抽屜原理只是保證這樣的盒子存在因此，無論何時(shí)抽屜原理被用來證明一個(gè)排列或某種現(xiàn)象的存

10、在性，除了考察所有的可能性外，它都不能對(duì)任何構(gòu)造排列或?qū)ふ椰F(xiàn)象的例證給出任何指示還要注意，抽屜原理的結(jié)論不能被推廣到只存在個(gè)（或更少）物體的情n形這是因?yàn)槲覀兛梢园巡煌奈矬w放到個(gè)盒子的每一個(gè)中去當(dāng)然，在這n些盒子中可以這樣分發(fā)物體：一個(gè)盒子放入兩個(gè)物體，但對(duì)任意分發(fā)這是沒有保證的抽屜原理只是斷言，在個(gè)盒子中去論如何分發(fā)個(gè)物體，總不能n1n避免把兩個(gè)物體放進(jìn)同一個(gè)盒子中去還存在一些與抽屜原理相關(guān)的其它原理，有必要正式敘述如下(1) 如果將個(gè)物體放入個(gè)盒子并且沒有一個(gè)盒子是空的，那么每個(gè)盒子nn恰好包含一個(gè)物體(2) 如果將個(gè)物體放入個(gè)盒子并且沒有盒子被放入多于一個(gè)的物體，那nn么每個(gè)盒子里有一

11、個(gè)物體現(xiàn)在把所闡明的這三個(gè)原理更抽象的表述為：4令和是兩個(gè)有限集，并令是一個(gè)從到得函數(shù)XY:fXYXY（1）如果的元素多于的元素，那么就不是一對(duì)一的XYf（2）如果和含有相同個(gè)數(shù)的元素，并且是映上的，那么就是一對(duì)XYff一的（3）如果和含有相同個(gè)數(shù)的元素，并且是一對(duì)一的，那么就是映上XYff的1.2.1.2.抽屜原理的加強(qiáng)形式抽屜原理的加強(qiáng)形式 下列定理包含定理下列定理包含定理 2.2.作為它的特殊情形作為它的特殊情形定理定理 2.2.鴿巢原理鴿巢原理( (組合數(shù)學(xué)組合數(shù)學(xué))設(shè)設(shè)為正整數(shù)如果將為正整數(shù)如果將12,nq qq個(gè)物體放入個(gè)物體放入 個(gè)盒子內(nèi)，那么，或者第一個(gè)盒子個(gè)盒子內(nèi)，那么，或者

12、第一個(gè)盒子121nqqqnn至少含有至少含有個(gè)物體，或者第二個(gè)盒子至少含有個(gè)物體，或者第二個(gè)盒子至少含有個(gè)物體，個(gè)物體，或者，或者1q2q第第 個(gè)盒子至少含有個(gè)盒子至少含有個(gè)物體個(gè)物體nnq證明證明：設(shè)將：設(shè)將個(gè)物體分放到個(gè)物體分放到 個(gè)盒子中如果個(gè)盒子中如果121nqqqnn對(duì)于每個(gè)對(duì)于每個(gè)，第，第 個(gè)盒子含有少于個(gè)盒子含有少于個(gè)物體，那么所有盒子個(gè)物體，那么所有盒子12,in，iiq中的物體總數(shù)不超過中的物體總數(shù)不超過1212111 nnqqqqqqn（）（）（）該數(shù)比所分發(fā)的物體總數(shù)少該數(shù)比所分發(fā)的物體總數(shù)少 1 1，因此我們斷言，對(duì)于某一個(gè)，因此我們斷言，對(duì)于某一個(gè)，第，第 個(gè)盒子至少

13、包含個(gè)盒子至少包含個(gè)物體個(gè)物體12,in，iiq 注意，能夠?qū)⒆⒁猓軌驅(qū)€(gè)物體用下面的方法分到個(gè)物體用下面的方法分到 個(gè)盒個(gè)盒12nqqqnn子中，對(duì)所有的子中，對(duì)所有的第第 個(gè)盒子都不能含有個(gè)盒子都不能含有個(gè)或更多的物體，個(gè)或更多的物體，12,in，iiq我們可以通過將我們可以通過將個(gè)物體放入第一個(gè)盒子，將個(gè)物體放入第一個(gè)盒子，將個(gè)物體放入第個(gè)物體放入第11q 21q 二個(gè)盒子等來實(shí)現(xiàn)，抽屜原理的簡(jiǎn)單形式是由其強(qiáng)化形式的通過使二個(gè)盒子等來實(shí)現(xiàn)，抽屜原理的簡(jiǎn)單形式是由其強(qiáng)化形式的通過使得到的，由此得到的，由此12.2nqqq有有121211nqqqnnnn 在初等數(shù)學(xué)中抽屜原理的加強(qiáng)形式最常

14、用于都等于同一個(gè)整數(shù)12,nq qq的特殊情況在這種情況下，該定理敘述如下：r5推論推論 1 1 如果如果個(gè)物體放入個(gè)物體放入 個(gè)盒子中，那么至少有一個(gè)盒子中，那么至少有一11n r n個(gè)盒子含有個(gè)盒子含有 個(gè)或更多的物體等價(jià)的，個(gè)或更多的物體等價(jià)的，r推論推論 2 2如果如果 個(gè)非負(fù)整數(shù)個(gè)非負(fù)整數(shù)的平均數(shù)大于的平均數(shù)大于：n12,.,nm mm1r 12.1nmmmrn那么至少有一個(gè)整數(shù)大于或等于那么至少有一個(gè)整數(shù)大于或等于 r這兩種表述之間的聯(lián)系可以通過取這兩種表述之間的聯(lián)系可以通過取個(gè)物體并放入個(gè)物體并放入 個(gè)個(gè)11n r n盒子中得到對(duì)于盒子中得到對(duì)于，令，令是第是第 個(gè)盒子中的物體個(gè)

15、數(shù)于個(gè)盒子中的物體個(gè)數(shù)于12,in，imi是這是這個(gè)數(shù)個(gè)數(shù)的平均數(shù)為的平均數(shù)為m12,.,nm mm12.(1) 11(1)nmmmn rrnnn由于這個(gè)平均數(shù)大于由于這個(gè)平均數(shù)大于，故而有一個(gè)整數(shù)，故而有一個(gè)整數(shù)至少是至少是 換句話說，換句話說，1r imr這些盒子中有一個(gè)盒子至少含有這些盒子中有一個(gè)盒子至少含有 個(gè)物體個(gè)物體r 推論推論 3.3. 如果如果 個(gè)非負(fù)整數(shù)個(gè)非負(fù)整數(shù)的平均數(shù)小于的平均數(shù)小于：n12,.,nm mm1r 12.1nmmmrn那么至少有一個(gè)整數(shù)小于那么至少有一個(gè)整數(shù)小于1r 推論推論 4 4 如果如果 個(gè)非負(fù)整數(shù)個(gè)非負(fù)整數(shù)的平均數(shù)至少等于的平均數(shù)至少等于 ，n12,

16、.,nm mmr那么這那么這 個(gè)整數(shù)個(gè)整數(shù)至少有一個(gè)滿足至少有一個(gè)滿足n12,.,nm mmimr推論推論 5 5 個(gè)物體放入個(gè)物體放入 個(gè)盒子中，則至少有一個(gè)盒子中有不個(gè)盒子中，則至少有一個(gè)盒子中有不mn少于少于個(gè)物體個(gè)物體11mn注：符號(hào)注：符號(hào)表示不超過實(shí)數(shù)表示不超過實(shí)數(shù) 的最大整數(shù)的最大整數(shù) xx證明：證明：（反證法）若不然，則每一個(gè)集合中最多有（反證法）若不然，則每一個(gè)集合中最多有個(gè)物個(gè)物1mn6體，這時(shí)，體，這時(shí)， 個(gè)盒子中就最多有個(gè)盒子中就最多有個(gè)物體個(gè)物體n1mnn因?yàn)橐驗(yàn)?，所以，所以，這與，這與11mmnn111mmnnmmnn 已知條件已知條件個(gè)物體放入個(gè)物體放入 個(gè)盒子中

17、矛盾，故上述推論成立個(gè)盒子中矛盾，故上述推論成立mn抽屜原理的形式比較多變，在具體的應(yīng)用中也會(huì)有不同的變化，抽屜原理的形式比較多變，在具體的應(yīng)用中也會(huì)有不同的變化，但本質(zhì)上都是一樣的但本質(zhì)上都是一樣的 上述定理及推論的證明均采用反證法，這種證明方法對(duì)于證明元上述定理及推論的證明均采用反證法，這種證明方法對(duì)于證明元素個(gè)數(shù)多于抽屜個(gè)數(shù)的問題時(shí)有其普遍意義，素個(gè)數(shù)多于抽屜個(gè)數(shù)的問題時(shí)有其普遍意義， 平均重疊原則平均重疊原則：把一個(gè)量：把一個(gè)量任意分成任意分成 份，則其中至少有一份，則其中至少有一Sn份不大于份不大于，也至少有一份不少于，也至少有一份不少于SnSn不等式重疊原則不等式重疊原則：若：若，

18、且，且，則，則，, , ,a b c dRacbdab至少有一個(gè)成立至少有一個(gè)成立cd 面積重疊原則面積重疊原則：在平面上有：在平面上有 個(gè)面積分別是個(gè)面積分別是，的的n1A2AnA圖形，把這圖形，把這 個(gè)圖形按任何方式一一搬到某一個(gè)面積為個(gè)圖形按任何方式一一搬到某一個(gè)面積為的固定圖形的固定圖形nA上去，上去， （1 1）如果）如果，則至少有兩個(gè)有公共點(diǎn)；，則至少有兩個(gè)有公共點(diǎn)；12.nAAAA （2 2）如果）如果，則固定圖形中至少有一個(gè)點(diǎn)未被蓋，則固定圖形中至少有一個(gè)點(diǎn)未被蓋12.nAAAA住住2 2抽屜原理的應(yīng)用抽屜原理的應(yīng)用應(yīng)用抽屜原理的基本思想是根據(jù)不同問題自身特點(diǎn)，洞察問題本質(zhì)，先

19、弄清對(duì)哪些元素進(jìn)行分類，再找出分類的規(guī)律，即所謂的構(gòu)造抽屜，構(gòu)造抽屜是應(yīng)用抽屜原理的關(guān)鍵在介紹抽屜原理的應(yīng)用之前，本文先用幾個(gè)具體的例子來介紹幾種常用的構(gòu)造抽屜的方法2.1 抽屜的構(gòu)造抽屜的構(gòu)造72. .1.1 等分區(qū)間制造抽屜等分區(qū)間制造抽屜當(dāng)問題的結(jié)論與區(qū)間有關(guān)時(shí)，可等分某個(gè)區(qū)間，設(shè)計(jì)出若干個(gè)抽屜例 1 求證：對(duì)于任給的正無理數(shù)及任意大的自然數(shù)，存在一個(gè)有n理數(shù)，使得km1kmmn證明：把區(qū)間（0，1）進(jìn)行等分，得個(gè)小區(qū)間nn11 22 310,.,1nnn nn nn 由抽屜原理知，這些區(qū)間內(nèi)的個(gè)數(shù)中，必有兩個(gè)數(shù)落在某一個(gè)區(qū)間，1n從而這兩個(gè)數(shù)的差的絕對(duì)值小于1n設(shè)，則由是正無理數(shù)得(1

20、,2,.,1)ipN in01iipp所以這個(gè)數(shù)中，必有 2 個(gè)數(shù)，不妨設(shè)為1n(1,2,.,1)iippin和，它們的差的絕對(duì)值小于，即11pp22pp1n 12121()()ppppn設(shè)，則 1212,ppmppk，即1mkn1kmmn上述例子涉及區(qū)間問題，把區(qū)間（0，1）進(jìn)行等分，得個(gè)小區(qū)間，自然nn就得到了個(gè)抽屜，而個(gè)數(shù)可以作為個(gè)物體，此處可以利用抽屜原理n1n1n解決問題2.1.22.1.2 分割圖形構(gòu)造抽屜分割圖形構(gòu)造抽屜在一個(gè)幾何圖形內(nèi)有若干已知點(diǎn)，我們可以根據(jù)問題的要求把圖形進(jìn)行適當(dāng)?shù)姆指?，用這些分割成的圖形作為抽屜，再對(duì)已知點(diǎn)進(jìn)行分類，集中對(duì)某一個(gè)或幾個(gè)抽屜進(jìn)行進(jìn)行討論，使問

21、題得到解決例 2 在邊長為 2 米的正方形內(nèi)，任意放入 13 個(gè)點(diǎn)求證：必有 4 個(gè)點(diǎn)，以它們?yōu)轫旤c(diǎn)的四邊形的面積不超過 1 平方米8 (1) (2)證明：把邊長為 2 米的正方形分割成面積為 1 平方米的 4 個(gè)小正方形，如圖 1因?yàn)?13=34+1，所以由抽屜原理知，至少有 4 個(gè)點(diǎn)落在同一個(gè)面積為 1平方米的小正方形內(nèi)（或邊上），以這 4 個(gè)點(diǎn)為頂點(diǎn)的四邊形的面積總小于或等于小正方形的面積，即以這 4 個(gè)點(diǎn)為頂點(diǎn)的四邊形的面積不超過 1 平方米注：此例是通過分割圖形構(gòu)造抽屜 將正方形等分成 4 個(gè)矩形來制造抽屜也可以解決本題，如圖 22.1.32.1.3 利用利用“對(duì)稱性對(duì)稱性”構(gòu)造抽屜

22、構(gòu)造抽屜“對(duì)稱性”是數(shù)學(xué)中常用的處理問題的一種方法同樣，在構(gòu)造抽屜的過程中也可以利用“對(duì)稱性”來解決問題，這種方法不易觀察，需要不斷的訓(xùn)練例 3 九條直線中的每一條直線都把正方形分成面積比為 2：3 的兩個(gè)四邊形證明:這九條直線中至少有三條經(jīng)過同一點(diǎn) 證明：如圖，設(shè)是一條這樣的這樣的直CD線我們?cè)佼嫵鲞@兩個(gè)梯形的中位線，因這兩AB個(gè)梯形有相等的高，所以他們的面積比應(yīng)等于對(duì)應(yīng)的中位線長的比，即等于(或者)因:AP PB:BP PA為點(diǎn)有確定的位置，它在正方形一對(duì)對(duì)邊中點(diǎn)P的連線上，并且，由幾何上的對(duì)稱性，:2 3AP PB ：這種點(diǎn)共有 4 個(gè)，即圖中的已知的九, ,P Q R S條適合條件的分

23、割直線中的每一條必須過這 4 點(diǎn)中的一點(diǎn)把當(dāng)成 4 個(gè)抽屜，9 條直線當(dāng)成 9 個(gè)物體，, ,P Q R S, ,P Q R S9即可看出必有 3 條分割直線經(jīng)過同一個(gè)點(diǎn)正方形是個(gè)比較規(guī)則的圖形，在正方形中有很多對(duì)稱關(guān)系，對(duì)解題減小了一點(diǎn)難度。2.1.42.1.4 用整數(shù)性質(zhì)制造抽屜用整數(shù)性質(zhì)制造抽屜當(dāng)問題與整數(shù)性質(zhì)有關(guān)時(shí)，我們可以用整數(shù)的性質(zhì)，把題目中的數(shù)設(shè)計(jì)成一些抽屜，然后用抽屜原理去解（1）劃分?jǐn)?shù)組制造抽屜仔細(xì)觀察題目中的數(shù)，如果題中數(shù)據(jù)具有一定的規(guī)律，可以劃分?jǐn)?shù)組構(gòu)造抽屜例 4 從 1,2,3, 98 中任取 50 個(gè)不同的數(shù)，試證：其中必有兩個(gè)數(shù)，它們之差等于 7證明:先把所給的 9

24、8 個(gè)數(shù)設(shè)計(jì)成 49 個(gè)抽屜：（1，8），（2，9）（3，10），（4，11），（21，28），（91，98），可以發(fā)現(xiàn)每個(gè)抽屜里的兩個(gè)數(shù)之差為 7從 1，2，3，98 中任取 50 個(gè)，就是從這 49 個(gè)抽屜中任取 50 個(gè)數(shù)，由抽屜原理知，必有一個(gè)抽屜中要取出兩個(gè)數(shù)，即這 50 個(gè)數(shù)中必有兩個(gè)數(shù)，它們之差為 7本題的關(guān)鍵就是對(duì)這 98 個(gè)數(shù)進(jìn)行合理分類，構(gòu)造抽屜分類的原則是每個(gè)抽屜中的兩個(gè)數(shù)只差是 7，且抽屜的個(gè)數(shù)少于任取的數(shù)的個(gè)數(shù)（2）按同余類制造抽屜把所有整數(shù)按照除以某個(gè)自然數(shù)的余數(shù)分為類，叫做的剩余類或同mmm余類，用0，1，2，m-1表示每一個(gè)類含有無窮多個(gè)數(shù)在研究與整除有關(guān)的問題

25、時(shí)，常按同余類制造抽屜例 5任意 10 個(gè)自然數(shù)中，總有兩個(gè)數(shù)的差是 9 的倍數(shù)證明：要使兩個(gè)自然數(shù)的差被 9 整除，必須使兩個(gè)自然數(shù)被 9 除的余數(shù)相同于是我們考慮把自然數(shù)按除以 9 所得的余數(shù) 0、1、2、3、8 進(jìn)行分類，也就是 9 個(gè)抽屜根據(jù)抽屜原理，任意 10 個(gè)自然數(shù)中，必有兩個(gè)數(shù)除以9 所得的余數(shù)相同因此這兩個(gè)數(shù)的差一定是 9 的倍數(shù)10本題的特點(diǎn)比較明顯，很容易想到利用同余類制造抽屜2.1.52.1.5 利用染色制造抽屜利用染色制造抽屜我們可以把將物體放入盒子改為用中顏色中的每一種顏色對(duì)每一個(gè)物體n染色此時(shí)抽屜原理斷言，如果個(gè)物體用種顏色涂色，那么必然有兩個(gè)1nn物體被染成相同

26、顏色抽屜原理的加強(qiáng)形式用染色的術(shù)語表述就是：如果個(gè)物體中的每一個(gè)物體被指定用種顏色中的一種染色，121nqqqnn那么存在一個(gè)這樣的 ，使得第 種顏色的物體至少有個(gè)iiiq例 6證明：任意 6 個(gè)人中一定有 3 個(gè)人互相認(rèn)識(shí)或互相不認(rèn)識(shí) 證明：我們用點(diǎn)依次表示這 6 個(gè)人兩者互相認(rèn)識(shí)的，123456,A A A A A A他們之間用紅色線段相連；兩者互相不認(rèn)識(shí)的用藍(lán)色線段相連那么把從出1A發(fā)的 5 條線段，放入紅，藍(lán)兩個(gè)抽屜中，根據(jù)抽12A A13A A14A A15A A16A A屜原理知，一定至少有 3 條線段同色不妨設(shè)線段，都為紅12A A13A A14A A色考慮線段，分以下兩種情況：

27、23A A24A A34A A（1）若，都是藍(lán)色，則三角形的三邊同為藍(lán)色，23A A24A A34A A234A A A如圖（3） ，這就是說三者互不認(rèn)識(shí)234,A A A（2）若，中至少有一條為紅色，不妨設(shè)為，如圖23A A24A A34A A23A A（4） ，則三角形的三邊同為紅色，即三者互相不認(rèn)識(shí)123A A A123,A A AA6A5A4A3A2A1 A6A5A4A3A2A1 （3）（4）實(shí)線表示紅色，虛線表示藍(lán)色總之，任意 6 個(gè)人中一定有 3 個(gè)人互相認(rèn)識(shí)或互相不認(rèn)識(shí)11本題屬于利用染色制造抽屜，染色問題的實(shí)質(zhì)是分類，只不過題目以涂色形式出現(xiàn)，顯得直觀而已2.1.62.1.6

28、根據(jù)問題的需要制造抽屜根據(jù)問題的需要制造抽屜 例 7 能否在 44 的方格表的每個(gè)小方格中分別填上 1、2、3 這 3 個(gè)數(shù)之一，而使大正方形方格的每行、每列及對(duì)角線上的 4 個(gè)數(shù)字的和互不相同?請(qǐng)說明理由 證明：若每格都填數(shù)字“1” ，則 4 個(gè)數(shù)字之和最小，其值為 4；若每格都填數(shù)字“3” ，則 4 個(gè)數(shù)字之和最大，其值為 12因?yàn)閺?4 到 12 之間共有個(gè)互不相同的值作為 9 個(gè)抽屜，而 4 行、4 列及 2 條對(duì)角線上的各124 19 個(gè)數(shù)字之和共有個(gè)整數(shù)值，這樣元素的個(gè)數(shù)比抽屜的個(gè)數(shù)多 1，根44210據(jù)抽屜原理知，一定至少有兩個(gè)數(shù)值屬于同一個(gè)抽屜，即不可能使大正方形的每行、每列及

29、對(duì)角線上的各個(gè)數(shù)字之和互不想同 本題中的抽屜不明顯，需要根據(jù)問題來進(jìn)行構(gòu)造，即找出 4 個(gè)數(shù)字之和的最小值和最大值，從而確定抽屜數(shù)本題可推廣為：不可能在的方格表的n n每個(gè)方格中分別填上 1、2、3 這三個(gè)數(shù)之一，而使大正方形方格表的每行、每列及對(duì)角線上的各個(gè)數(shù)字之和互不相同但如果在每個(gè)方格中分別填上1、2、3、4 這 4 個(gè)數(shù)之一，則可以使大正方形方格的每行、每列及對(duì)角線上的各個(gè)數(shù)字之和互不相同抽屜原理敘述的內(nèi)容很簡(jiǎn)單，但應(yīng)用起來卻比較復(fù)雜，主要原因就是必須找到合適的抽屜，抽屜的構(gòu)造方法大致可歸結(jié)為兩大類：一類是用分割圖形構(gòu)造抽屜，一類是用分類的概念構(gòu)造抽屜其實(shí)質(zhì)是對(duì)對(duì)象進(jìn)行恰當(dāng)?shù)姆诸惓閷线x

30、的好，選的巧，可以得出非常漂亮的結(jié)果，抽屜構(gòu)造的方法很多，上述方法旨在通過以上例子做到舉一反三下面本文將結(jié)合上述方法，簡(jiǎn)單談一下抽12屜原理在數(shù)學(xué)解題中以及生活中的應(yīng)用2.22.2 抽屜原理在數(shù)學(xué)解題中的應(yīng)用抽屜原理在數(shù)學(xué)解題中的應(yīng)用一般地說，用抽屜原理來解決的數(shù)學(xué)問題有如下特征：新給的元素具有任意性，如八個(gè)蘋果放入七個(gè)抽屜，可以隨意的一個(gè)抽屜放幾個(gè)，也可以讓抽屜空著，問題的結(jié)論是存在性命題，題中常含有“至少有”，“一定有”，“不少于”，“存在”，“必然有”等詞語，其結(jié)論只要存在，不必確定前面的內(nèi)容已經(jīng)介紹了一些常用的構(gòu)造抽屜的方法，這對(duì)我們的解題有很大的幫助下面將從代數(shù)，數(shù)論，幾何三方面來談

31、抽屜原理在數(shù)學(xué)解題中的應(yīng)用2.2.12.2.1 解決代數(shù)問題解決代數(shù)問題用集合的語言抽屜原理可以敘述如下：（1）設(shè)個(gè)元素按任意確定方式分成有限個(gè)集合，那么至少有一個(gè)集合含n有兩個(gè)元素（2）設(shè)有無窮多個(gè)元素按任意確定方式分成有限個(gè)集合，那么至少有一個(gè)集合含有無窮多個(gè)元素例 8 證明:有限群中的每個(gè)元素的階均有限 證明：設(shè) G 為階有限群，任取 aG，則由抽屜原理可知n中必有相等的不妨設(shè)于是有231,.,nna aaaa,11staatsn ，從而 a 的階有限s tae例 9 設(shè) A 為階方陣，證明：存在n11,AAkkkn使秩（）=秩（）證明：因?yàn)殡A方陣的秩只能是這個(gè)數(shù)之一，而n0,1,2,3

32、n，1n的個(gè)數(shù)大于秩，從而，由抽屜原理知在0121,.,nnAA AAA中，存在滿足0121,.,nnAA AAA, k l使1kln 秩（）=秩（）kAlA但秩（）秩（）秩（）kA1kAlA所以秩（）=秩（） ，得證kA1kA132.2.22.2.2 解決數(shù)論問題解決數(shù)論問題在初等數(shù)論中，很多問題都可以看作存在性問題，所以可以考慮利用抽屜原理進(jìn)行解決利用抽屜原理解決數(shù)論問題時(shí)常利用整數(shù)的性質(zhì)制造抽屜，可參見 214例 10（中國余式定理）令 和 為兩個(gè)互素的正整數(shù)，并令 和 mnab為整數(shù)，且 以及，則存在一個(gè)正整數(shù)，使得 除01am01bnxx以 的余數(shù)是，并且 除以的余數(shù)為 即 可以寫成

33、 maxnbx xpma的同時(shí)又可以寫成的形式，這里 和 是整數(shù) xqnbpq證明：為了證明這個(gè)結(jié)論考慮個(gè)整數(shù)，n,2,.,1amamanma，這些整數(shù)中的每一個(gè)除以都余設(shè)其中的兩個(gè)除以有相同的余數(shù)令這manr兩個(gè)數(shù)為和，其中因此，存在兩整數(shù)和，使imajma01ijn iqjq得及，這兩個(gè)方程相減可得iimaq nrjjmaq nr()()jiji mqq n于是是的一個(gè)因子由于和沒有除 1 之外的公因子，因此n()ji mnm是的因子然而，意味著，也就是說不可nji01ijn 01jin n能是的因子該矛盾產(chǎn)生于我們的假設(shè)：個(gè)整數(shù)jin,2,.,1amamanma，中的兩個(gè)除以有相同的余數(shù)

34、因此這個(gè)數(shù)中的每一個(gè)數(shù)除以 n 都有不同的余nn數(shù)根據(jù)抽屜原理，個(gè)數(shù)中的每一個(gè)作為余數(shù)都要出現(xiàn)，特別地，n01.1n，數(shù)也是如此令為整數(shù)，滿足，且使數(shù)，除以余數(shù)bp01pnxpman為則對(duì)于某個(gè)適當(dāng)?shù)?，有bqxqnb因此且，從而具有所要求的性質(zhì)xpmaxqnbx2.2.32.2.3 解決幾何問題解決幾何問題抽屜原理在幾何問題中可以變形如下：如果長度為的線段上放置若干條a長度大于之和大于的線段，則放置的線段中必有公共點(diǎn)a例 11 在邊長為 1 的正方形內(nèi)部，放置若干個(gè)圓，這些圓的周長之和等于 10證明：可以作出一條直線，至少與其中四個(gè)圓有交點(diǎn)14證明：將所有的已知圓投影到正方形的一條邊 AB 上

35、注意，周長為的圓l周，其投影長為的線段因此所有已知圓的投影長度之和等于，由于l10，所以由抽屜原理知，線段 AB 上必有一點(diǎn) X，至少被四條投影線1033AB段所覆蓋即至少有四條投影線段有公共點(diǎn)因此，過點(diǎn) X 且垂直于 AB 的直線，至少與四個(gè)已知圓有交點(diǎn)2.2.42.2.4 多次順向運(yùn)用抽屜原理多次順向運(yùn)用抽屜原理前面所舉的例子都知運(yùn)用了一次抽屜原理，其實(shí)在有些應(yīng)用中，順向運(yùn)用抽屜原理時(shí)，必須連續(xù)使用多次，才能解決問題，而且每構(gòu)造一次抽屜都把范圍縮小一些例 12 求證：在平面內(nèi)，任意凸五邊形的頂點(diǎn)中，必有三點(diǎn) A、B、C，使5ABC分析：因?yàn)?，是凸五邊形五個(gè)內(nèi)角大小的平均值， (52)155

36、3(52)5又是的三等分值，所以此題要用兩次抽屜原理5(52)5證明：因?yàn)槠矫嫱刮暹呅蔚膬?nèi)角和為，所以由抽屜原理知，至(52)3少有一個(gè)內(nèi)角不小于不妨設(shè)這個(gè)不小于的內(nèi)角的頂點(diǎn)為 B，與它不相3535鄰的兩個(gè)頂點(diǎn)為 A、C，邊 AB、CB 把分成三個(gè)角，則由抽屜原理知，必有一B個(gè)角不小于，設(shè)這個(gè)角為，于是31535ABC5ABC2.2.52.2.5 逆向運(yùn)用抽屜原理逆向運(yùn)用抽屜原理有些應(yīng)用題，運(yùn)用抽屜原則可歸結(jié)為：已知和的值，求的最n11mnm小值，這種問題可逆向用抽屜原理，并用去解 1xxx例 13 在平面直角坐標(biāo)系內(nèi)，求至少在多少個(gè)整點(diǎn)（坐標(biāo)都是整數(shù)的點(diǎn)）中有 4 個(gè)整點(diǎn)，它們兩兩的中點(diǎn)也是

37、整點(diǎn)15解解：由中點(diǎn)坐標(biāo)公式知，中點(diǎn)為整點(diǎn)的條件是兩個(gè)端點(diǎn)的對(duì)應(yīng)坐標(biāo)的奇偶性相同，因此需要把整點(diǎn)的坐標(biāo)按奇偶性分類整點(diǎn)的坐標(biāo)按整數(shù)的奇偶性分成四類：（奇，奇），（奇，偶），（偶，奇），（偶，偶）設(shè)在 x 個(gè)整點(diǎn)中至少一類中有 4 個(gè)整點(diǎn)，所以，即，1144x 134x所以，即所以 x 的最小值是 13，即至少在 13 個(gè)整點(diǎn)121 16x 1317x中，有 4 個(gè)整點(diǎn)，它們兩兩的中點(diǎn)也是整點(diǎn)2 23 3 抽屜原理在生活中的應(yīng)用抽屜原理在生活中的應(yīng)用抽屜原理在日常生活中的應(yīng)用其實(shí)也非常廣泛，比如前面提到的例 5，再如一組多余 366 個(gè)人中一定有 2 個(gè)人的生日相同，80 個(gè)人中至少有 7 個(gè)人

38、生在同一個(gè)月等等，這樣的例子很多，下面介紹幾個(gè)有意思的例子; 停車場(chǎng)上有 40 輛客車，各種車輛座位數(shù)不同，最少 26 座，最多 44 座，那么，在這些客車中，至少有輛座位是相同的思路點(diǎn)撥是： 已知客車最少 26座，最多 44 座，可知 40 輛客車中有 26,27,28,，44 共 19 種不同座位數(shù)的客車 根據(jù)抽屜原理，把 19 種座位看做 19 只”抽屜”，把 40 輛客車當(dāng)作 40 只”蘋果”放進(jìn)抽屜里，因?yàn)?40=219+2，可知在這些客車中至少有 3 輛客車座位是相同的3.抽屜原理在生活中的應(yīng)用抽屜原理在生活中的應(yīng)用3.13.1 月黑穿襪子月黑穿襪子有一個(gè)晚上你的房間的點(diǎn)燈忽然壞了

39、，伸手不見五指，而你又要出去，于是你就摸底下的襪子你有三雙分別為紅、白、藍(lán)顏色的襪子，可是你平時(shí)做事隨便，一脫襪子就亂丟，在黑暗中不知道哪一雙是顏色相同的你想拿最少數(shù)目的襪子出去，在外面借街燈配成顏色相同的一雙這最少數(shù)目應(yīng)該是多少？運(yùn)用抽屜原理，你就會(huì)知道只拿出去四只襪子就行了因?yàn)槲覀冇腥p紅、16白、藍(lán)的襪子，相當(dāng)于 3 個(gè)抽屜，我們拿出去的 4 只襪子就是 4 個(gè)物體，4 個(gè)物體肯定有 2 個(gè)是同一個(gè)顏色的3.23.2 手指紋和頭發(fā)手指紋和頭發(fā)據(jù)說世界上沒有兩個(gè)人的手指紋是一樣的，因此警方在處理犯罪問題時(shí)很重視手指紋，希望通過手指紋來破案或檢定犯人可是在 13 億中國人當(dāng)中，最少有兩個(gè)人頭

40、發(fā)是一樣多的這是因?yàn)?，人的頭發(fā)數(shù)目是不會(huì)超過 13 億這么大的數(shù)目，假定人最多有 N根頭發(fā)現(xiàn)在我們編上號(hào)碼其中表示由 根頭發(fā)的那些1234,.,nA A A AAiAi人現(xiàn)在假定每個(gè)都有一個(gè)人，那么還剩下“13 億減 N”個(gè)人，這數(shù)目不會(huì)iA等于零，我們現(xiàn)在隨便挑一個(gè)放進(jìn)和他頭發(fā)相同的小組就行，他就會(huì)在里面遇到和他有相同頭發(fā)數(shù)目的人了3.33.3 電腦算命電腦算命“電腦算命”看起來挺玄乎，只要你報(bào)出自己出生的年、月、日和性別一按按鍵，屏幕上就會(huì)出現(xiàn)所謂性格、命運(yùn)的句子，據(jù)說這就是你的“命”這是科學(xué)的嗎？如果以 70 年算，按出生的年、月、日、性別的不同組合數(shù)應(yīng)為，我們把它作為抽屜數(shù)我國現(xiàn)有人口

41、 13 億，我們把它作70 365 251100為物體由于，由抽屜原理，存在 25441 個(gè)以上的人，91.3 10112544151100 盡管他們的出身、經(jīng)歷、天資、機(jī)遇各不相同，但他們卻有完全相同的“命” ，這真是荒謬絕倫！所謂“電腦算命”不過是把人為編好的算命語句像中藥柜那樣事先分別一一存放在各自的柜子里，誰要算命，即根據(jù)出生的年、月、日、性別的不同的組合按不同的編碼機(jī)械地到電腦上的各個(gè)“柜子”里取出所謂命運(yùn)的句子其實(shí)這充其量不過是一種電腦游戲而已抽屜原理應(yīng)用其實(shí)非常廣泛，除了之前介紹的幾個(gè)例子之外，抽屜原理在計(jì)算機(jī)上也有一定的應(yīng)用，由于涉及一些計(jì)算機(jī)專業(yè)問題，本文不再詳細(xì)介17紹4總結(jié)總結(jié)抽屜原理敘述起來比較簡(jiǎn)單，因此本文將重點(diǎn)放在了抽屜原理的應(yīng)用，尤其是構(gòu)造抽屜的幾種方法，這是靈活應(yīng)用抽屜原理的關(guān)鍵從上面的例子中，我們可以看到應(yīng)用抽屜原理時(shí)一般分為三個(gè)步驟：（1） 構(gòu)成分類的對(duì)象有個(gè)元素；m（2） 找出分類的規(guī)則，將個(gè)元素分成個(gè)抽屜，并證明每個(gè)抽屜中的mn元素符合題意；（3） 應(yīng)用抽屜原理證明結(jié)論成立應(yīng)用的關(guān)鍵在于構(gòu)造抽屜的方