抽屜原理的應(yīng)用及其推廣優(yōu)秀畢業(yè)論文

1、數(shù)學(xué)與計算機科學(xué)學(xué)院畢業(yè)論文抽屜原理的應(yīng)用及其推廣數(shù)學(xué)與計算機科學(xué)學(xué)院數(shù)學(xué)與應(yīng)用數(shù)學(xué)指導(dǎo)老師： 王美能摘要：抽屜原理也叫鴿巢原理，是研究如何將元素分類的一個原理，也是組合數(shù)學(xué)里最簡單、最基本的原理。本文簡述了抽屜原理普遍使用的簡單形式，重點介紹了抽屜原理在我們數(shù)學(xué)競賽，通過由淺到深，由簡單到復(fù)雜，循序漸進的了解抽屜原理。同時，通過對抽屜原理的學(xué)習(xí)，我們可以發(fā)現(xiàn)在我們?nèi)粘Ｉ钪泻芏嗟胤蕉加谐閷显淼膽?yīng)用。通過本文的介紹，相信大家對抽屜原理會有一個更為全面的認(rèn)識。關(guān)鍵詞：抽屜原理、狄利克雷原理、數(shù)學(xué)競賽、拉姆塞定理Abstract：This paper describes the simple f

2、orm of the widespread use of drawer principle,focuses on the drawer principle in mathematics our primary school mathematics,advanced mathematics,form shallow to deep,form simple to complex,step by step to understand the principle of drawer.At the same time,the drawer principle of learning,we can fin

3、d applications in our daily life,there are a lot of places of drawer principle,such as computer divination,schedule,resource allocation and so on. Keywords: Drawer principle,de Lickley principle,Mathematics competition,Ramsrys theorem mathematics competition mathematics competition mathematics compe

4、tition1 引言 抽屜原理又稱鴿巢原理、鞋箱原理或重疊原理，是一個十分簡單又十分重要的原理.它是由德國著名數(shù)學(xué)家狄利克雷(P.G.T.Dirichlet 1805-1855)首先發(fā)現(xiàn)的，因此也叫作狄利克雷原理。抽屜原理簡單易懂，主要用于證明某些存在性或至少類的問題，在生活中抽屜原理的應(yīng)用非常廣泛，解決了生活中一些模糊不清的問題，方便了人們的生活。本文歸納了抽屜原理在小學(xué)數(shù)學(xué)競賽、中學(xué)數(shù)學(xué)競賽中的一些簡單應(yīng)用，由淺入深將抽屜原理推廣到更高的領(lǐng)域，并舉例闡述了抽屜原理在現(xiàn)實生活中的應(yīng)用。2 抽屜原理的定義 第一抽屜原理 原理1：把多于n個的物體放在n個抽屜里，則至少有一個抽屜里的東西不少于兩件

5、。 證明（反證法）：如果每個抽屜至多只能放進一個物體，那么物體的總數(shù)至多是 n，而不是題設(shè)的，故不可能。 原理2：把多于（m乘于n）個的物體放到n個抽屜里，則至少有一個抽屜里有不少于的物體。 證明（反證法）：若每個抽屜至多放進m個物體，那么n個抽屜至多放進個物體，與題設(shè)不符，故不可能。 原理3：把無窮多件物體放入n個抽屜，則至少有一個抽屜里有無窮個物體。 第二抽屜原理 把個物體放入n個抽屜中，其中必有一個抽屜中至多有個物體（例如，將個物體放入5個抽屜中，則必定有一個抽屜中的物體數(shù)少于等于）。 證明（反證法）：若每個抽屜都有不少于m個物體，則總共至少有個物體，與題設(shè)矛盾，故不可能。3 抽屜原理在

6、數(shù)學(xué)競賽以及實際生活中的應(yīng)用 數(shù)學(xué)競賽是以開發(fā)智力為根本目的、以問題解決為基本形式、以競賽數(shù)學(xué)為主要內(nèi)容。最本質(zhì)的是對中學(xué)生進行“競賽數(shù)學(xué)”的教育，這種教育的性質(zhì)是：較高層次的基礎(chǔ)教育、開發(fā)智力的素質(zhì)教育、生動活潑的業(yè)余教育、現(xiàn)代數(shù)學(xué)的普及教育。數(shù)學(xué)競賽與體育競賽相類似，它是青少年的一種智力競賽，所以蘇聯(lián)人首創(chuàng)了數(shù)學(xué)奧林匹克這個名詞。在類似的以基礎(chǔ)科學(xué)為競賽內(nèi)容的智力競賽中，數(shù)學(xué)競賽歷史最悠久，參賽國最多，影響也最大。數(shù)學(xué)競賽活動也是由淺入深逐步發(fā)展的。幾乎每個國家的數(shù)學(xué)競賽活動都是先由一些著名數(shù)學(xué)家出面提倡組織，試題的命題在背景的深刻度和構(gòu)題的藝術(shù)性上也有較高的要求，較為突出的有四條：內(nèi)容的

7、科學(xué)性、結(jié)構(gòu)的新穎性、功能的選拔性、解法的靈活性。數(shù)學(xué)競賽命題的基本途徑主要有：高等初等化，歷史名題的再生，成題改編，模型法。抽屜原理由于它自身的特點，簡單并且思維方法在解題過程中可以演變出很多奇妙的變化和頗具匠心的運用，所以抽屜原理經(jīng)常是命題人出題方向及思路。3.1 抽屜原理在小學(xué)數(shù)學(xué)競賽中的應(yīng)用 其實在抽屜原理在小學(xué)數(shù)學(xué)中已經(jīng)有雛形了，在人教版六年級下冊中的“數(shù)學(xué)廣角”中，就已經(jīng)出現(xiàn)了一些抽屜原理的簡單應(yīng)用。當(dāng)時就有很多教師反應(yīng)教學(xué)存在一定的困難性，不僅如此，學(xué)生也普遍覺得難以理解，學(xué)習(xí)起來也很困難！在數(shù)學(xué)問題中，經(jīng)常碰到有關(guān)“存在性”的問題。如某地區(qū)醫(yī)院一月共接生32名嬰兒，那么一定存在

8、兩名嬰兒，他們是在同一天出生的。在解決這類問題中，只需要確定某個人（或某件物），也不需要嚴(yán)格說明通過什么方式把這個存在的人（或物）找出來。這就是我們小學(xué)初次接觸的比較簡單的“抽屜原理”，即把多于n個的物體放在n個抽屜里，則至少有一個抽屜里的東西不少于兩件。在教學(xué)過程中，教學(xué)者普遍認(rèn)為在這類問題上很難向?qū)W生講清其中的來龍去脈，所以在理解算法的基礎(chǔ)上，采用“總有至少”的語言敘述出來，以加固理解，采用這種教學(xué)方法，學(xué)生相對來說容易理解一些。 下面我們將問題建立兩類模型來解決：模型一 求至少的問題這類問題的特點是：已知“抽屜”的個數(shù)，求某個“抽屜”里至少能裝多少的問題。例1 在任意的49個人中，至少有

9、幾個人的屬相相同？ 解：因為共有12個生肖，將12個生肖看成12個“抽屜”，問題就轉(zhuǎn)換成尋求一個“抽屜”里至少能“裝”多少人。我們可以先算出平均每個“抽屜”“裝”多少個人：，多出來的1個人總會隨機的進入到某個“抽屜”中，所以總有一個抽屜里有四個人，也就是總有一種生肖屬相里至少有4個人。即：至少有4個人的屬相相同。 例2 平面上有六個點A、B、C、D、E、F，其中不存在三個點在同一條直線上的情況，每兩點之間都用紅線或藍線連接。試說明：不管如何連接，至少存在有一個三角形是三條邊的顏色都相同。 解：從六個點當(dāng)中任取一點，設(shè)為A，在用它連接其余五點的五條線段中，至少有3條同色（把紅、藍兩色作為兩個“抽

10、屜”，）。假設(shè)其中的AB、AC、AD為紅色線段（如下圖所示）。 這時，在三條線段BC、BD、CD中，若有一條為紅色，則得到一個三邊為紅色的三角形；（如下圖所示）若沒有一條為紅色，則BC、BD、CD都是藍色，也得到一個三邊都是的三角形BCD。（如下圖所示）所以不管怎樣連接，至少有一個三邊同色的三角形。對于求至少性的這類問題，我們首先確定有多少個抽屜，然后可以把物體平均分給這幾個抽屜，剩余的物體再平均分一次，最后就可以確定一個抽屜至少有幾個物體。解這類問題的原理是把多于（m乘于n）個的物體放到n個抽屜里，則至少有一個抽屜里有不少于的物體。 模型二 作“最壞”的打算 理論依據(jù)：把多于n個的物體放在n

11、個抽屜里，則至少有一個抽屜里的東西不少于兩件。即：一定有一個“抽屜”里至少有兩個元素。例3 有紅、黃、綠三種顏色的手套各6雙，裝在一個黑色的布袋里，從袋子里任意取出手套來，為確保至少有2雙手套不同顏色，則至少要取出的手套只數(shù)是？ 分析：“為確保至少有”，考慮最壞的情況，首先取出了一種顏色的全部6雙手套和其他兩種顏色的手套各一只，再任意取出一只，必然得到2雙不同顏色的手套。因此至少要取出只。 例4 有120名職工投票從甲、乙、丙三人中選舉一人為勞模，每人只能投一次，且只能選一個人，得票最多的人當(dāng)選。統(tǒng)計票數(shù)的過程發(fā)現(xiàn)，在前81張票中，甲得21票，乙得25票，丙得35票。在余下的選票中，丙至少再得

12、幾張選票就一定能當(dāng)選？ 分析：此題是問丙至少再得幾張選票就一定能當(dāng)選，由題干中可以看出共有三位候選人，甲得21票， 乙得25票，丙得35票，要使至少再得到幾張選票丙一定能當(dāng)選，那么還是首先應(yīng)該考慮到，丙競選中遇到的最不利的情況，丙遇到的最不利的情況其實就是來看，誰對丙當(dāng)選的競爭最大，從開始的選票中，可以看到甲的選票比較少，對丙當(dāng)選的威脅較小，可以排除；而乙得到的選票與丙是最接近的，對丙的當(dāng)選最有威脅。120名職工投票，已有的81張票中，得票最少的是甲21張，只考慮乙丙即可。，若丙最后當(dāng)選，至少得50張票，所以丙至少再得503515張票。 綜上所述，抽屜原理在小學(xué)數(shù)學(xué)中主要是上述兩方面的應(yīng)用，實

13、質(zhì)上就是抽屜原理的兩種常用形式。在教學(xué)中，可以歸類進行學(xué)習(xí)，建立兩種模型，學(xué)生熟練掌握，進而能簡單應(yīng)用。為孩子后續(xù)學(xué)習(xí)和理解打下堅實的基礎(chǔ)。3.2 抽屜原理在中學(xué)數(shù)學(xué)競賽中的應(yīng)用 在小學(xué)數(shù)學(xué)中我們已經(jīng)學(xué)習(xí)了“抽屜原理”的雛形，在初中數(shù)學(xué)中我們主要學(xué)習(xí)的是抽屜原理的基本形式和如何使用抽屜原理，并通過實例了解抽屜原理中的一些構(gòu)造方法，以及抽屜原理在中學(xué)數(shù)學(xué)競賽題中的應(yīng)用。 抽屜原理的基本形式： （1）把個元素分為n個集合，那么必有一個集合中含有兩個或兩個以上的元素。 （2）把個元素分成n個集合，那么必有一組中含有個或個以上元素。（3） 把n個元素分成k個集合，那么必有一個集合中元素的個數(shù)，也必有一

14、個集合中元素的個數(shù)。（4）把個元素分為n個集合，那么必有一個i，在第i個集合中元素的個數(shù)。（5）把無窮多個元素分成為有限個集合，那么必有一個集合含有無窮多個元素。抽屜原理的基本構(gòu)造： 利用抽屜原理解題的過程中首先要注意指明什么是元素，什么是抽屜，元素進入抽屜的規(guī)則是什么，以及在同一個盒子中，所有元素具有的性質(zhì)。構(gòu)造抽屜是用抽屜原理解題的關(guān)鍵。有的題目運用一次抽屜原理就能解決，有的則需要反復(fù)多次。 下面我們通過一些具體的例題來介紹抽屜原理的應(yīng)用：例5 求證：從任意給定的2010個自然數(shù)，中可以找到若干數(shù)，使得它們的和是2010的倍數(shù)。 證明 以，即被2010除的余數(shù)分類制造抽屜，將下列數(shù)：作為抽

15、屜中的元素。若上述2010個數(shù)中有一個是2010的倍數(shù)，則問題得證；否則，根據(jù)抽屜原理，至少存在兩個數(shù)（它們的差仍為中若干數(shù)的和），它們被2010除的余數(shù)相同，則它們的差是，即中若干數(shù)的和能被2010整除，命題得證。 此例是抽屜原理中常見的題型“存在至少”性問題，解決此類問題的關(guān)鍵就是抽屜的中元素的選擇。例6 在邊長為1的正方形內(nèi)任意放入九個點，求證：存在三個點，以這三個點為頂點的三角形的面積不超過。（1963年北京競賽題） 分析與解答：如圖，四等分正方形，得到A1，A2，A3，A4四個矩形。在正方形內(nèi)任意放入九個點，則至少有一個矩形Ai內(nèi)存在個或3個以上的點，設(shè)三點為A、B、C，具體考察Ai

16、（如圖所示），過A、B、C三點分別作矩形長邊的平行線，過A點的平行線交BC于A點，A點到矩形長邊的距離為，則ABC的面積 說明：把正方形分成四個區(qū)域，可以得出“至少有一個區(qū)域內(nèi)有3個點”的結(jié)論，這就為確定三角形面積的取值范圍打下了基礎(chǔ)。本題構(gòu)造“抽屜”的辦法不是唯一的，還可以將正方形等分成邊長為的四個小正方形等。但是如將正方形等分成四個全等的小三角形卻是不可行的。所以適當(dāng)?shù)貥?gòu)造“抽屜”，正是應(yīng)用抽屜原則解決問題的關(guān)鍵所在。此例是通過分割圖形構(gòu)造抽屜，在一個幾何圖形內(nèi)有若干已知點，我們可以根據(jù)問題的要求把圖形進行適當(dāng)?shù)姆指睿眠@些分割成的圖形作為抽屜，在對其中需要用到的抽屜進行討論，使問題得到解

17、決。例7 在中任選出20個數(shù)，其中至少有不同的兩組數(shù)，其和都等于104，試證明之。（美國普特南） 證明 給定的數(shù)共有34個，其相鄰兩數(shù)的差均為3，我們把這些數(shù)分成如下18個不想交的集合并且把他們看做是18個抽屜。從已知的34個數(shù)中任選20個數(shù)，即使把前兩個抽屜中的數(shù)1和52都取出來，則剩下的18個數(shù)在后面的16個抽屜中至少有不同的兩個抽屜中的數(shù)全被取出來，這兩個抽屜中的數(shù)互不相同，每個抽屜中的兩個數(shù)的和都是104.此例是根據(jù)某兩個數(shù)之和為104來構(gòu)造抽屜。一般的，與整數(shù)集有關(guān)的存在性問題也可以根據(jù)不同的需要利用整數(shù)間的倍數(shù)關(guān)系，同余關(guān)系來適當(dāng)分組而構(gòu)造抽屜。例8 設(shè)實數(shù)，則其中必有兩個數(shù)，滿足

18、.證 把分成n個小區(qū)間：它們兩兩不相交?，F(xiàn)有n+1個點在中，則至少有兩點設(shè)為和屬于同一小區(qū)間，從而有. 在例8中，如記是任意的無理數(shù)，則，由例8有.（不妨設(shè)kl） 如記都是整數(shù)可得. 只要n充分大，我們可用有理數(shù)比較精確的逼近一個無理數(shù). 抽屜原理還有其他表現(xiàn)形式： 把個元素任意分成類，則至少有類的元素個數(shù)一樣多. 逆向抽屜原則不難用反證法給予證明. 如果至少有k類的元素一樣多，那么元素個數(shù)最少的方法是k類0個元素，k類1個元素，k類2個元素，k類個元素，這樣最少需要出現(xiàn)矛盾. 以上證明方法對于證明元素個數(shù)多于抽屜個數(shù)的問題時有普遍意義. 平均量重疊原則 把一個量S任意分成n份，則其中至少有一

19、份不大于，也至少有一份不少于. 不等式重疊原則 若,且，則至少有一個成立. 面積重疊原則 在平面上有n個面積分別是的圖形，把這n個圖形按任何方式一一搬到某一面積為A的固定圖形上去， （1）如果,則至少有兩個圖形有公共點； （2）如果，則固定圖形中至少有一個點未被蓋住.總而言之，抽屜原理的應(yīng)用比較靈活，在競賽輔導(dǎo)中教給學(xué)生一些簡單的思想方法有助于培養(yǎng)學(xué)生的構(gòu)造的解題思想，可以使學(xué)生的思維能力得到一定的提升，不僅有助于現(xiàn)階段的學(xué)習(xí)，也可以為將來的高等數(shù)學(xué)學(xué)習(xí)帶來一定的幫助。3.3 總結(jié)應(yīng)用抽屜原理解題的步驟在應(yīng)用抽屜原理進行解題的過程中，我們把解題步驟分成三步：第一步：分析題意，分清什么是“東西”

20、，什么是“抽屜”，也就是把什么看作“東西”，什么看作“抽屜”。第二步：制造抽屜。這是關(guān)鍵，這一步就是如何設(shè)計抽屜，根據(jù)題目條件和結(jié)論，結(jié)合有關(guān)的數(shù)學(xué)知識，抓住最基本的數(shù)量關(guān)系，設(shè)計和確定解決問題所需的抽屜及其個數(shù)，為使用抽屜原理鋪平道路。第三步：運用抽屜原理，觀察題設(shè)條件，恰當(dāng)應(yīng)用各個原則或綜合運用幾個原則，以求問題之解決。在今后的學(xué)習(xí)中，我們可以根據(jù)抽屜原理的這三步來解決問題，這樣既可以節(jié)約我們的解題時間，也可以為我們解決這一類題型指明了一個方向。3.4 抽屜原理在生活中的應(yīng)用抽屜原理不僅在小學(xué)數(shù)學(xué)、中學(xué)數(shù)學(xué)、高等數(shù)學(xué)中具有廣泛應(yīng)用，在我們的實際生活中，也能處處發(fā)現(xiàn)原理的影子。如電腦算命、賽

21、程安排、資源分配等等，都不難看到抽屜原理的作用。在當(dāng)今信息化、電子化的社會中，我們經(jīng)常在網(wǎng)絡(luò)世界中經(jīng)常看到“電腦算命”。所謂“電腦算命”不過是把人為編好的算命語句像中藥柜那樣事先分別一一存放在各自的柜子里，誰要算命，即根據(jù)出生年、月、日、性別的不同的組合按不同的編碼機械地到電腦的各個“柜子”里，取出所謂命運的句子。其實這充其量不過是一種電腦游戲而已。我們用數(shù)學(xué)上的抽屜原理很容易說明它的荒謬。如果以70年計算，按出生年、月、日、性別的不同組合數(shù)應(yīng)為，我們把它作為“抽屜”數(shù)。由于，根據(jù)原理，存在21526個以上的人，盡管他們的出身、經(jīng)歷、天資、機遇各不相同，但他們卻具有完全相同的“命”，這真是荒謬

22、絕倫！其實早在中國古代的春秋戰(zhàn)國時期就有了運用抽屜原理的例子，那就是晏子春秋中的“二桃殺三士”的典故，將兩個桃子賞賜給三名勇士，在這里可以將桃子看作抽屜，三個人作為元素放進抽屜，則根據(jù)抽屜原理，一定有一個抽屜要放入兩個或兩個以上的元素，回到問題情境中就是一定要有兩個人吃一個桃子，導(dǎo)致這三名勇士最后自相殘殺而亡，這就是著名的“二桃殺三士”。在實際生活中，運用抽屜原理的事情還有很多很多。比如我們在安排一場比賽時，該如何安排才能做到最公平。 假設(shè)：你所在的年級有5個班，每班一支球隊在同一塊場地上進行單循環(huán)賽, 共要進行10場比賽. 則各隊每兩場比賽中間至少隔多少場才最公平呢？下面是隨便安排的一個賽程

23、: 記5支球隊為A, B, C, D, E，在下表左半部分的右上三角的10個空格中, 隨手填上1,2,，10, 就得到一個賽程, 即第1場A對B, 第2場B對C, 第10場C對E. 表的右半部分是各隊每兩場比賽間相隔的場次數(shù), 顯然這個賽程對A, E有利, 對D則不公平.答案是. 證明因，所以分兩種情況討論.（1）當(dāng)為偶數(shù)時，這支球隊為.順次安排場比賽需要支球隊參賽，由抽屜原理，必然有重復(fù)出現(xiàn)的球隊，由單循環(huán)賽知，重復(fù)出現(xiàn)的球隊中一定存在某球隊.其兩場比賽中間相隔的場次數(shù)最多為.（2)當(dāng)為奇數(shù)時，這支球隊為.順次安排場比賽需要支球隊參賽，由抽屜原理，必然有重復(fù)出現(xiàn)的球隊，其兩場比賽中間相隔的場

24、次數(shù)最多為.因此，當(dāng)n支球隊比賽時，若安排的賽程使各隊每兩場比賽中間至少相隔場，則該賽程稱為完美賽程.抽屜原理的應(yīng)用非常廣泛，除了以上介紹的幾個例子之外，在計算機，警方處理指紋或者是頭發(fā)上也有一定的應(yīng)用，由于涉及到一些專業(yè)問題，在此就不再詳細(xì)介紹。4 抽屜原理的推廣抽屜原理的內(nèi)容簡明樸素，易于接受，它在數(shù)學(xué)問題中有許多重要的作用。許多有關(guān)存在性的證明題都可以用抽屜原理來解決。1958年6/7月號的美國數(shù)學(xué)月刊上有一道關(guān)于抽屜原理推廣的應(yīng)用題：“證明在任意6個人的集會上，或者3個人以前彼此認(rèn)識，或者有三個人以前彼此不相識。”這個問題可以用如下方法簡單明了地證出：這個問題看起來，似乎令人匪夷所思。

25、但如果你懂得抽屜原理，要證明這個問題是十分簡單的。我們用A、B、C、D、E、F代表六個人，從中隨便著一個，例如A吧，把其余五個人放到“與A認(rèn)識”和“與A不認(rèn)識”兩個“抽屜”里去，根據(jù)抽屜原理，至少有一個抽屜原理里有三個人。不妨假定在“與A認(rèn)識”的抽屜里有三個人，他們是B、C、D。如果B、C、D三個互不認(rèn)識，那么我們就找到了三個互不認(rèn)識的人；如果B、C、D三人中有兩個互相認(rèn)識，例如B與C認(rèn)識，那么A、B、C就是三個互相認(rèn)識的人。不管哪種情況，本題的結(jié)論都是成立的。由于這個試題的形式新穎，解法巧妙，很快在全世界廣泛流傳，使不少人知道了這一原理。 六個人集會問題是組合數(shù)學(xué)中著名的拉姆塞定理的一個最簡單的特例，這個簡單的問題的證明思想可用來得出另外一些深入的結(jié)論。這些結(jié)論構(gòu)成了組合數(shù)學(xué)中的重要內(nèi)容拉姆塞定理。從六人集會問題的證明中，我們又一次看到了抽屜原理的應(yīng)用。5 總結(jié) 抽屜原理在我們小學(xué)、初中、高中課本上雖然沒有明確的學(xué)習(xí)與定義，但是他的價值是非常高的。它雖然只是一個小原理，但是在數(shù)學(xué)競賽中確是必不可少的，它的數(shù)學(xué)思想和技巧是我們值得深刻了解和探索的。在我們學(xué)習(xí)