大學數(shù)學本科畢業(yè)論文-鴿籠原理..

1、本科畢業(yè)論文論文題目：抽屜原理及其應(yīng)用學生姓名：學 號:專業(yè)：數(shù)學與應(yīng)用數(shù)學指導(dǎo)教師:學院:數(shù)學科學學院1 1 20142014 年 5 5 月 2020 日畢業(yè)論文內(nèi)容介紹論文題目抽屜原理及其應(yīng)用選題時間2011.10.25完成時間2012.5.18論文（設(shè)計） 字數(shù)12750關(guān)鍵詞抽屜原理；數(shù)論；離散數(shù)學；咼等代數(shù)；抽象代數(shù)；Ramsey 定理；應(yīng)用論文題目的來源、理論和實踐意義：題目來源：學生自擬研究意義：研究抽屜原理在咼等數(shù)學中數(shù)論、離散數(shù)學、咼等代數(shù)、抽象代數(shù)等多個學科中的運用，對其在高等數(shù)學各方面的運用進行較為全面的梳理總結(jié)，加深對抽屜原理的理解，使復(fù)雜的數(shù)學問題能夠在抽屜原理的作

2、用下得到靈活巧妙的解決論文（設(shè)計）的主要內(nèi)容及創(chuàng)新點：主要內(nèi)容：本文簡述了抽屜原理普遍使用的簡單形式、各種推廣形式，著重闡述其在數(shù)論和離散數(shù)學、高等代數(shù)及抽象代數(shù)中的應(yīng)用，及在生活中的應(yīng)用，可以巧妙地解決一些復(fù)雜問題，并根據(jù)抽屜原理的不足之處引入抽屜原理的推廣定理Ramsey定理.創(chuàng)新點：以往抽屜原理的相關(guān)文章或集中于中小學數(shù)學方面或比較零散片面，本文的主要創(chuàng)新點是就本人所學過的高等數(shù)學的幾門學科中抽屜原理的應(yīng)用進行比較全面的梳理總結(jié)生活中的應(yīng)用這一部分本文區(qū)別于其它相關(guān)文章中大量的缺乏實際意義的事例，選取與生活貼近的如賽程安排、資源分配等問題進行闡述，更好地突出抽屜原理在實際生活中的用 處附

3、：論文本人簽名：2012 年 5 月 20 日目錄中文摘要. 1英文摘要. 11. 弓 I 言. 22. 抽屜原理的形式. 23. 抽屜原理在高等數(shù)學中的應(yīng)用. 33.1 數(shù)論中的應(yīng)用 .33.2 離散數(shù)學中的應(yīng)用.53.3 高等代數(shù)中的應(yīng)用.83.4 抽象代數(shù)中的應(yīng)用.94. 抽屜原理在生活中的應(yīng)用 . 105. 抽屜原理的推廣定理Ramse 癥理 . 12錯誤！未定義書簽。6. 參考文獻. 161抽屜原理及其應(yīng)用XXX摘要：本文簡述了抽屜原理普遍使用的簡單形式、各種推廣形式，著重闡述其在數(shù)論和離散數(shù)學、高等代數(shù)及抽象代數(shù)中的應(yīng)用，及在生活中的應(yīng)用，可以巧妙地解決一些復(fù)雜問題， 并根據(jù)抽屜原

4、理的不足之處引入抽屜原理的推廣定理 Ramsey定理.關(guān)鍵詞：抽屜原理；數(shù)論；離散數(shù)學；高等代數(shù)；抽象代數(shù)；Ramsey 定理；應(yīng)用1. 引言抽屜原理又稱鴿巢原理、鞋箱原理或重疊原理，是一個十分簡單又十分重要 的原理.它是由德國著名數(shù)學家狄利克雷(P.GT.Dirichlet 1805-1855)首先發(fā)現(xiàn) 的，因此也叫作狄利克雷原理.抽屜原理簡單易懂，主要用于證明某些存在性或必然性的問題，不僅在數(shù)論、組合論以及集合論等領(lǐng)域中有著廣泛應(yīng)用，在高等數(shù)學的其它幾門學科領(lǐng)域中也 是解決問題的有效方法本文總結(jié)了如何運用抽屜原理解決數(shù)論、 離散數(shù)學、高等代數(shù)及抽象代數(shù)中 的問題，對抽屜原理在高等數(shù)學中的應(yīng)

5、用進行了梳理， 將抽屜原理的解題思路拓 展到高等數(shù)學的其他領(lǐng)域，有助于更好地理解抽屜原理，并舉例闡述了抽屜原理 在現(xiàn)實生活中的應(yīng)用，以及根據(jù)抽屜原理的不足引出的 Ramsey 定理.2. 抽屜原理的形式什么是抽屜原理？先舉個簡單的例子說明，就是將3 個球放入 2 個籃子里,無論怎么放，必有一個籃子中至少要放入 2 個球，這就是抽屜原理.或者假定一 群鴿子飛回巢中，如果鴿子的數(shù)目比鴿巢多，那么一定至少有一個鴿籠里有兩只 或兩只以上的鴿子，這也是鴿巢原理這一名稱的得來 抽屜原理簡單直觀，很容易理解而這個看似簡單的原理在高等數(shù)學中有著2很大的用處，對于數(shù)論、離散數(shù)學、高等代數(shù)以及抽象代數(shù)中的一些復(fù)雜

6、問題， 可以利用抽屜原理巧妙的解答出來下面首先從抽屜原理的形式入手，然后再研究它在高等數(shù)學中的應(yīng)用.我們最常用的抽屜原理只是抽屜原理的簡單形式，就是將 n+1 個元素或者更多的元素放入n個抽屜中，則至少有一個抽屜里放有兩個或兩個以上的元素除了這種比較普遍的形式外，抽屜原理還經(jīng)許多學者推廣出其他的形式.陳景林、閻滿富在他們編著的組合數(shù)學與圖論一書中將抽屜原理抽象概 括成以下三種形式1：原理 1.把多于 n 個的元素按任一確定的方式分成 n 個集合，則一定有一個 集合中含有兩個或兩個以上的元素原理 2.把m個元素任意放到 n(m n)個集合里，則至少有一個集合里至少 有k個元素，其中當 n 能整除

7、 m 時，當 n 不能整除 m 時.原理 3.把無窮個元素按任一確定的方式分成有限個集合，則至少有一個集合中 仍含無窮個元素盧開澄在組合數(shù)學(第三版)中將抽屜原理(書中稱為鴿巢原理)又進行了推廣2.鴿巢原理：設(shè) k 和 n 都是任意正整數(shù)，若至少有 kn+1 只鴿子分配在 n 個鴿 巢中，則至少存在一個鴿巢中有至少 k+1 只鴿子.推論 1.有 m 只鴿子和 n 個鴿巢，則至少有一個鴿巢中有不少于+1 只-n鴿子推論 2.若將 n(m-1)+1 個球放入 n 個盒子里，則至少有一個盒子有 m 個球.推論 3.若m1,m2,l“mn是 n 個正整數(shù)，而且r= 一叫，則nm, m2,1丨I mn中

8、至少有一個數(shù)不小于 r.3另外，抽屜原理還可以用映射的形式來表示，即：設(shè)A和B是兩個有限集,如果 A B，那么對從A到B的任何滿射 f，至少存在ai,a a?,使 f (a )= f (a2).3.抽屜原理在高等數(shù)學中的應(yīng)用以上的幾種形式就是我們解題時常用到的抽屜原理的表示形式，接下來，在了解了抽屜原理的基本形式以及多位學者所發(fā)展的推廣形式的基礎(chǔ)上，我們通過一些比較典型的實例來說明抽屜原理在高等數(shù)學中數(shù)論、 離散數(shù)學、高等代數(shù) 以及抽象代數(shù)這五個方面的應(yīng)用.3.1 數(shù)論問題中的應(yīng)用例 1.任意 5 個整數(shù)中，有其中 3 個整數(shù)的和為 3 的倍數(shù).證明將整數(shù)分為形如 3k、3k+1 及 3k+2

9、 這 3 類形式，則我們可以將這 3 類整數(shù)看作是 3 個抽屜，將這 5 個整數(shù)看作元素放入這 3 個抽屜中.由抽屜原理可知，至少存在 2=匸+1 個整數(shù)在同一抽屜中，即它們都是3形如(3k+m 的整數(shù)，m=o,1 或 2.如果有 3 個以上的數(shù)在同一個抽屜中，則取其中的任意三個數(shù)，它們的和是 形如3( 3k+m 的整數(shù)，即三者的和為 3 的倍數(shù).如果有 2 個整數(shù)在同一個抽屜中，則由抽屜原理知，在余下的3 個數(shù)中有 2個數(shù)在同一個抽屜中，余下的 1 個數(shù)在另一個抽屜中.在 3 個抽屜中各取一個數(shù)， 這 3個數(shù)的形式分別為 3k1,3k2+1,3k3+2,則三者的和為 3(k1+k2+k3)+

10、3，即 為 3 的倍數(shù).例 2.設(shè)有兩組整數(shù)，而且每一組的數(shù)都是小于n (nZ )的互不相同的數(shù)，這兩組數(shù)的數(shù)目個數(shù)三 n,則存在一對分別取自兩組的數(shù)使這兩個數(shù)的和為n.證明設(shè)這兩組數(shù)為a1,a2,ap、b1,b2,bq.已知每一組的數(shù)都是小于 n (n，Z J 的互不相同的數(shù).不妨設(shè) aia2.ap, bib2 bq.4令 ci=n-ai,i=1,2,k.則有 n-1 三 c1三 c2三三 cp三 1.n-1 三 b1= b2三三 bq= 1.這些未知數(shù)只能在 1,2,n-1 中取值，我們可以將 1,2,n-1 這n個數(shù)看作n個抽屜.考察數(shù)集b1,b2,bq, c , C2，,cp.由于 p

11、+q 三 n,運用抽屜原理可知，至少有兩個數(shù)在 1,2,n-1 之中的一個 抽屜，也就是至少有兩個數(shù)取同一個值，且這兩個數(shù)分別來自C1,C2，Cp、b1，b2，bq.（ 此是因為，根據(jù)已知條件，C1，C2，Cp、b1,b2,bq在各 自集合中是互不相同的，假定兩個數(shù)同時取自G，g，Cp，也就是在這 p 個數(shù)當中有兩個數(shù)被同時放在同一抽屜里，則這兩個數(shù)相等，而q = n- ai, ai互 不相同，則 Ci互不相同，兩者矛盾.）即 b =5 = n_aj,aj$ 二 n.3.2 離散數(shù)學中的應(yīng)用例 3.設(shè)有 3 個 7 位的二進制數(shù)&1b1b2b3b4b5b6b?C1C2C3C4C5C6C

12、7試證存在整數(shù)i和 j , 1 G ：j乞7，使得下列之一必然成立a aj= bi= bj,a aj=C 5由已知條件，在每一個縱列中，含有三個元素，分別都只由兩種選擇，即 0 或 1，5則根據(jù)鴿巢原理，ai=6問=Ci,b中至少一個必然成立.成立的時候取值的不同可以有 C22=6 種情況，而每一橫行共有七個元素 再根據(jù)鴿巢原理，必有兩列是相同的即aaj二b= bj, a：= a=G= 5= bj=G二Cj之一必然成立.例 4.三維空間中 9 個坐標為整數(shù)的點，試證在兩兩相連的線段內(nèi)，至少存在一 個坐標為整數(shù)的內(nèi)點.解三維空間中，任意兩坐標為整數(shù)的點，若這兩點相連的線段內(nèi)不存在坐標為 整數(shù)的內(nèi)

13、點，則對于 x,y,z 這三個坐標軸，這兩點至少在一個坐標上的差值正好 是 1.那么，在這 9 個坐標為整數(shù)的點中，任意取出一點，與這個點的三個坐標中， 存在的差值正好是 1 的共有 7 類，即與 x 軸差值正好是 1,與 y 軸差值正好是 1， 與 z 軸差值正好是 1,與 x,y 軸差值都是 1,與 x,z 軸差值都是 1,與 y,z 軸差 值都是 1,與 x,y,z軸差值都是 1.對于剩下的 8 個點，若存在一點 a 不滿足這 7 種情況，那么 a 點與這個點相 連的線段內(nèi)必有一個坐標為整數(shù)的內(nèi)點若剩下的 8 個點都屬于這 7 種情況之一，那么，運用鴿巢原理，則至少存在 兩個點屬于這 7

14、 種情況中的同一個情況，那么，這兩點中必存在一個坐標為整數(shù) 的內(nèi)點例 5.把從 1 到 326 的 326 個整數(shù)任意分為 5 個部分， 試證其中有一部分至少有 一個數(shù)是某兩個數(shù)之和，或是另一個數(shù)的兩倍.解(用反證法)假設(shè)存在劃分RP2P3P4Ps= 1,3261,P(i =1,2,3,4,5)中沒有數(shù)是兩個數(shù)之和， 即 R(i =1,2,3,4,5)中沒有數(shù)是兩個數(shù)之差.根據(jù)鴿巢原理(推論 1)嚴6_1片=66設(shè) 1 到 326 中至少有5-個元素屬于R，并設(shè)為6A=a1,a2,a66，不妨設(shè)a1 Va2a66若 A 中存在一個元素是某兩個元素之差，則滿足題目要求b1 =a2 a1,b2 =

15、a3 a1,b65 =a66 a1令 B = b1,b2,b65顯然 B 中的元素仍然是 1 到 326 之間的數(shù)，即 1Wb326,i=1,2,65.根據(jù) 假定 B中無一屬于R，所以 B 的元素屬于P2，巳，P4，P5.1 + 1=17同理，設(shè) B 中至少存在屬于 F2 的-4個元素.設(shè)為C =C1,C2,c17不妨設(shè) G Vc2 Vc17則根據(jù)假設(shè)，在 C 中不存在一個元素是某兩個元素之差.令d1= C2C1,d2= C3C1,，小花=57 G令 D=d1,d2,d 顯然D中的元素仍然是 1 到 326 之間的數(shù),即 1 di: 326,i =1,2,16 .易知存在整數(shù)I,m使得dk =

16、Ck7 -C1=（ai- 比）-（am-a1）=ai-am所以，D 中的元素不屬于R，也不屬于P2，只能屬于P3，P4，R.否則，令7根據(jù)鴿巢原理（推論 1），設(shè)至少存在-16-131=6個元素屬于F3.設(shè)為f1c f2c f3 Cf4 f5 f6V 326令F = f5,f6則根據(jù)假設(shè)，在 F 中不存在一個元素是某兩個元素之差，令g1g1,g2,g3,g4,g5,顯然 G 中的元素不屬于P3.且對于gi存在p，q，1，m使得f1= （Cp -C1）一（Cq -C1） = Cp- Cq=（a| -a1） -（am -a1） =a| -am故 G 中的元素也不屬于R和P2，貝 U G 中的元素屬

17、于P4，F(xiàn)5.5-1對于 G 中的 5 個元素，根據(jù)鴿巢原理，設(shè)至少存在-21二3個屬于P4.設(shè)為山 h2vhh V326.令H =0山2山3.令 X =h? -= h3- hT = tt?8顯然，T 中的元素不屬于P,P2,P3,巳,故 T 的元素屬于P5但根據(jù)假定打=t2 _ X，令 U =t2 -tl，則 1 X2 X2n適合X2nXi2n ji,2,2n9證明KnjXiX設(shè)集合 s=X=彳2：|Xj|蘭n, j = i,2,2n令A(yù)二aij n2nXiX2則該齊次線性方程組可寫成AX =010* 2n送aijXj2n映射f：迂AX是一個滿射顯然|S=(2n+1)2n,因為引 -1 ,

18、0, 1,所以對 每個 XS,它的 2n 個分量適合2n瓦 a” 閭 aiX#越 x 卅 |+ anxnj牛|彳 x!和|+xjW2n2(i=1,2,n)因此|D|蘭(4n2+1 $又2n2n2n(2n1)=4 n24n 1 4n21根據(jù)抽屜原理.（映射形式設(shè) A 和 B 是兩個有限集，如果 A B 那么對從 A 到 B 的任何滿映射 f,至少存在a1,a2,使 f（ a a”=f（ a a2）.）S中至少存在兩個不同的元Xi2n “D=AXi - -a2jXj j 42nanjXjj 1，: :XSIJXi 2:,XjXj1Xj2aXj 2n使f X二f Xj,即AXi二AXj,AXi Xj

19、=0.令a1:、=X1X2- Xj1一為2、Xi2nXj 2n .:1ot2a2nJ即是我們所要求的，。1尸2。2是則11不全為零的整數(shù)，且滿足12Gk =Xik Xjk蘭Xik+ Xjk蘭2n（k = 1,2，2n）.例 7.設(shè) A 為 n 階方陣，證明存在 1 n n，使秩（A）=秩（Ai+I）=秩（A，42）= 證明因為n階方陣的秩只能是0,1,2,-, n這n+1 個數(shù)之一.E= A0, A,A2,，An,An, E 的個數(shù)多于秩的個數(shù)，由抽屜原理可知，存在 k,l 滿 足 1 乞 k1，則 R 是除環(huán)當且僅當對 R 中任意元素aO,b，方程 ax=b或 ya=b 在R中有解）在 R

20、中任取元素 a =0,b.13考慮N yaty R - Rat,i = 1,2,易知，Ra,Ra2,Ra3,都是R的理想.但由于整環(huán) R 只有有限個理想，根據(jù)抽屜原理.必存在正整數(shù) s 與 t 滿足 s2,則存在最小正整數(shù) R(p,q),使得當 nR(p,q)時，用紅藍兩色涂 Kn的邊，則或存在一個藍色的Kp,或存在一個紅色 的Kp.Ramsey 定理(狹義)的內(nèi)容任意六個人中要么至少三個人認識，要么至少 三個不認識.Ramsey 定理可以視為抽屜原理的推廣，1947 年，匈牙利數(shù)學家把這一原理 引進到中學生數(shù)學競賽中，當年匈牙利全國數(shù)學競賽有一道這樣的試題：“證明： 任何六個人中，一定可以找

21、到三個互相認識的人，或者三個互不認識的人.”在1958 年 6-7 月號美國數(shù)學月刊同樣也登載著這樣一個有趣的問題“任何六 個人的聚會，總會有 3 人互相認識或 3 人互相不認識.”這就是著名的 Ramsey 問題.這個問題乍看起來，似乎令人匪夷所思.但如果懂得抽屜原理，要證明這個 問題是十分簡單的：我們用 A、B、C、D E、F 代表六個人，從中隨便找一個，例如 A 吧，把其余五個人放到“與 A 認識”和“與 A 不認識”兩個“抽屜”里去， 根據(jù)抽屜原理， 至少有一個抽屜里有三個人.不妨假定在“與 A 認識”的抽屜里 有三個人，16他們是 B、C、D.如果 B C D 三人互不認識，那么我們

22、就找到了三 個互不認識的人；如果 B、C、D 三人中有兩個互相認識，例如 B 與 C 認識，那么，A、B、C 就是三個互相認識的人.不管哪種情況，本題的結(jié)論都是成立的.或者我們可以用染色的方法.以 6 個頂點分別代表 6 個人，如果兩人相識， 則在相應(yīng)的兩點間連一條紅邊，否則在相應(yīng)的兩點間連一藍邊.命題 1.對 6 個頂點的完全圖K6任意進行紅、藍兩邊著色，都存在一個紅色 三角形或藍色三角形.證明如下首先，把這 6 個人設(shè)為 A、B、C、D E、F 六個點.由 A 點可以引出 AB AC AD AEAF 五條線段.設(shè)如果兩個人認識，則設(shè)這兩個人組成的線段為紅色；如果兩個人不認識， 則設(shè)這兩個人

23、組成的線段為藍色.由抽屜原則可知這五條線段中至少有三條是同色的 .不妨設(shè) AB AC AD 為紅 色.若BC 或 CD 為紅色，則結(jié)論顯然成立.若 BC 和 CD 均為藍色，則若 BD 為紅色，則一定有三個人相互認識；若 BD 為藍色，則一定有三個人互相不認識.上述的 Ramsey可題等價于下面的命題 1.命題 1.對 6 個頂點的完全圖K6任意進行紅、藍兩邊著色，都存在一個紅色 三角形或藍色三角形.命題 1 運用抽屜原理可以很容易很簡便地對其進行證明.現(xiàn)將命題 1 推廣成 下面的命題 2.命題 2.對六個頂點的完全圖K6任意進行紅、藍兩邊著色，都至少有兩個同 色三角形.由于命題 2 是要證明

24、至少存在兩個同色三角形的問題， 而抽屜原理一般只局17限在證明至少存在一個或必然存在一個的問題， 所以對于上述命題抽屜原理就顯得無能為力，這時需要運用 Ramsey 定理來解決問題.證明 設(shè)w,V2,V3,V4,V5,V6是K6的六個頂點，由上面的命題 1 可知，對K6任 意進行紅、藍兩邊著色都有一個同色三角形，不妨設(shè) V1V2V3是紅色三角形.以下 分各種情況來討論(1)若 V1V4,VM,VIV6均為藍邊，如圖 1 所示，則若 V4,V5,V6之間有一藍邊，不 妨設(shè)為 V4V5，則三角形 V1V4V5為藍色三角形；否則， V4V5V6為紅色三角形.若 V1V4, VMVM 中有一條紅邊，不

25、妨設(shè) V1V4為紅邊，此時若邊 V2V4N3V4中 有一條紅邊，不妨設(shè) V3V4是紅邊，則 V1V3V4是一紅色三角形，見圖 2.以下就 V2V4N3V4均為藍邊的情況對與V4相關(guān)聯(lián)的邊的顏色進行討論.(i)若 V4V5N4V6中有一藍邊，不妨設(shè) V4V5為藍邊，如圖 3，此時，若 V2V5N3V5均為紅邊，則 V2V3V5是紅色三角形；否則， V2V4V5或厶 V3V4V5是藍色三角形.VMV6為藍色三角形圖18(ii)若 V4V5N4V6均為紅邊，見圖 4，此時，若 VV5,V6之間有一條紅邊，不妨 設(shè)V1V5為紅邊，則 V1V4V5為紅色三角形；否則，從以上例子可知，抽屜原理在應(yīng)用上確有

26、不足之處，之上只是個特例，至于 在別的領(lǐng)域中的不足之處還需我們進一步的探索 抽屜原理的應(yīng)用領(lǐng)域十分廣泛，涉及到高等數(shù)學的多個學科，并且在生活 中也有廣泛的應(yīng)用，可以巧妙的用于解決一些復(fù)雜問題，本文主要梳理總結(jié)了它 在數(shù)論、離散、高等代數(shù)及抽象代數(shù)中的應(yīng)用，其不足之處也由Ramsey 定理進行了補充，使其能夠更好的應(yīng)用與問題解決當中6.參考文獻1陳景林，閻滿富組合數(shù)學與圖論北京中國鐵道出版社出版，2000.042盧開澄.組合數(shù)學（第3版）.北京清華大學出版社，2002.073濮安山.“高等代數(shù)中抽屜原理的應(yīng)用”.哈師大自然科學學報，2001.064王向東，周士藩等.高等代數(shù)常用方法M.1989.11.楊子胥.近世代數(shù).北京.高等教育出版社.2003.12嚴士健.抽屜原則及其它的一些應(yīng)用J.數(shù)學通報,19597曹汝成.組合數(shù)學M.華東理工大學出版社,2000.由以上對各種情況的討論知，對角形19山東師范大學本科畢業(yè)論文（設(shè)計）選題審批表學院：數(shù)學科學學院（章）系別/教研室：數(shù)學與應(yīng)用數(shù)學時間：2011 年 10 月 25 日課 題 情況題目名稱抽屜原理及其應(yīng)用課題性質(zhì)A 基礎(chǔ)研究B基礎(chǔ)應(yīng)用研究2C應(yīng)用研究教師姓名職稱 講師學位碩士課題來源A.科研 B. 生產(chǎn) C. 教學 D. 其