抽屜原理及其應用 數(shù)學本科畢業(yè)論文

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

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

3、配等問題進行闡述，更好地突出抽屜原理在實際生活中 的用處. 附：論文本人簽名： 2012 年 5 月 20 日 目錄 中文摘要1 英文摘要1 1.引言2 2.抽屜原理的形式2 3.抽屜原理在高等數(shù)學中的應用3 3.1 數(shù)論中的應用 3 3.2 離散數(shù)學中的應用 5 3.3 高等代數(shù)中的應用 8 3.4 抽象代數(shù)中的應用 9 4.抽屜原理在生活中的應用 10 5.抽屜原理的推廣定理ramsey 定理 12 6.參考文獻 16 抽屜原理及其應用 摘要：本文簡述了抽屜原理普遍使用的簡單形式、各種推廣形式，著重闡述其 在數(shù)論和離散數(shù)學、高等代數(shù)及抽象代數(shù)中的應用,及在生活中的應用，可以巧 妙地解決一些

4、復雜問題，并根據(jù)抽屜原理的不足之處引入抽屜原理的推廣定理 ramsey 定理. 關(guān)鍵詞：抽屜原理；數(shù)論；離散數(shù)學；高等代數(shù)；抽象代數(shù)；ramsey 定理； 應用 dirichlet drawer principle and the application of it abstract:this paper introduces the widespread use of simple forms and all kinds of extended forms of dirichlet drawer principle,focusing on the application of dirichl

5、et drawer principle in the number theory ,discrete mathematics, hight algebra and abstract algebra ,and also the real life. it can solve ably some complicated problems,and according to the principle of drawer the shortcomings of the principle of introducing the drawer theorem ramsey theorem. keyword

6、s:dirichlet drawer principle; number theory; discrete mathematics; higher algebra; abstract algebra; ramsey theorem; application. 1.1.引言引言 抽屜原理又稱鴿巢原理、鞋箱原理或重疊原理，是一個十分簡單又十分重 要的原理.它是由德國著名數(shù)學家狄利克雷(p.g.t.dirichlet 1805-1855)首先發(fā) 現(xiàn)的，因此也叫作狄利克雷原理. 抽屜原理簡單易懂，主要用于證明某些存在性或必然性的問題，不僅在數(shù) 論、組合論以及集合論等領(lǐng)域中有著廣泛應用，在高等數(shù)學的其它

7、幾門學科領(lǐng) 域中也是解決問題的有效方法. 本文總結(jié)了如何運用抽屜原理解決數(shù)論、離散數(shù)學、高等代數(shù)及抽象代數(shù) 中的問題，對抽屜原理在高等數(shù)學中的應用進行了梳理，將抽屜原理的解題思 路拓展到高等數(shù)學的其他領(lǐng)域，有助于更好地理解抽屜原理，并舉例闡述了抽 屜原理在現(xiàn)實生活中的應用，以及根據(jù)抽屜原理的不足引出的 ramsey 定理. 2.2.抽屜原理的形式抽屜原理的形式 什么是抽屜原理？先舉個簡單的例子說明，就是將 3 個球放入 2 個籃子里， 無論怎么放，必有一個籃子中至少要放入 2 個球，這就是抽屜原理.或者假定一 群鴿子飛回巢中，如果鴿子的數(shù)目比鴿巢多，那么一定至少有一個鴿籠里有兩 只或兩只以上的

8、鴿子，這也是鴿巢原理這一名稱的得來. 抽屜原理簡單直觀，很容易理解.而這個看似簡單的原理在高等數(shù)學中有著 很大的用處，對于數(shù)論、離散數(shù)學、高等代數(shù)以及抽象代數(shù)中的一些復雜問題， 可以利用抽屜原理巧妙的解答出來. 下面首先從抽屜原理的形式入手，然后再研究它在高等數(shù)學中的應用. 我們最常用的抽屜原理只是抽屜原理的簡單形式，就是將 n+1 個元素或者 更多的元素放入n個抽屜中，則至少有一個抽屜里放有兩個或兩個以上的元素. 除了這種比較普遍的形式外，抽屜原理還經(jīng)許多學者推廣出其他的形式. 陳景林、閻滿富在他們編著的組合數(shù)學與圖論一書中將抽屜原理抽象 概括成以下三種形式1: 原理 1. 把多于個的元素按

9、任一確定的方式分成個集合，則一定有一個nn 集合中含有兩個或兩個以上的元素. 原理 2. 把個元素任意放到個集合里，則至少有一個集合里至mn)(nm 少有個元素，其中k 原理 3. 把無窮個元素按任一確定的方式分成有限個集合，則至少有一個集合 中仍含無窮個元素. 盧開澄在組合數(shù)學 （第三版）中將抽屜原理（書中稱為鴿巢原理）又進 行了推廣2. 鴿巢原理：設 k 和 n 都是任意正整數(shù)，若至少有 kn+1 只鴿子分配在 n 個鴿 巢中，則至少存在一個鴿巢中有至少 k+1 只鴿子. 推論 1.有 m 只鴿子和 n 個鴿巢，則至少有一個鴿巢中有不少于+1 只 n m 1 鴿子. 推論 2.若將 n(m

10、-1)+1 個球放入 n 個盒子里，則至少有一個盒子有 m 個球. 推論 3.若是 n 個正整數(shù)，而且，則 12 , n m mm 12n mmm n 中至少有一個數(shù)不小于 r. 12 , n m mm 另外，抽屜原理還可以用映射的形式來表示，即:設和是兩個有限集，ab 如果，那么對從到的任何滿射，至少存在,使ababf 1 a 2 a . 12 f af a 3.3.抽屜原理在高等數(shù)學中的應用抽屜原理在高等數(shù)學中的應用 以上的幾種形式就是我們解題時常用到的抽屜原理的表示形式，接下來， 在了解了抽屜原理的基本形式以及多位學者所發(fā)展的推廣形式的基礎上，我們 通過一些比較典型的實例來說明抽屜原理在

11、高等數(shù)學中數(shù)論、離散數(shù)學、高等 代數(shù)以及抽象代數(shù)這五個方面的應用. 3.13.1 數(shù)論問題中的應用數(shù)論問題中的應用 1 m nm n k m nm n ,當能整除時, ,當不能整除時. 例例 1 1.任意 5 個整數(shù)中，有其中 3 個整數(shù)的和為 3 的倍數(shù). 證明證明 將整數(shù)分為形如 3k、3k+1 及 3k+2 這 3 類形式， 則我們可以將這 3 類整數(shù)看作是 3 個抽屜，將這 5 個整數(shù)看作元素放入這 3 個抽屜中. 由抽屜原理可知，至少存在 2=+1 個整數(shù)在同一抽屜中，即它們都是 3 15 形如（3k+m）的整數(shù)，m=0,1 或 2. 如果有 3 個以上的數(shù)在同一個抽屜中，則取其中的

12、任意三個數(shù)，它們的和 是形如 3（3k+m）的整數(shù)，即三者的和為 3 的倍數(shù). 如果有 2 個整數(shù)在同一個抽屜中，則由抽屜原理知，在余下的 3 個數(shù)中有 2 個數(shù)在同一個抽屜中，余下的 1 個數(shù)在另一個抽屜中.在 3 個抽屜中各取一個 數(shù)，這 3 個數(shù)的形式分別為 3k ,3k +1,3k +2,則三者的和為 3（k +k +k ） 123123 +3，即為 3 的倍數(shù). 例例 2 2.設有兩組整數(shù)，而且每一組的數(shù)都是小于 n（nz ）的互不相同的數(shù)，這 兩組數(shù)的數(shù)目個數(shù)n，則存在一對分別取自兩組的數(shù)使這兩個數(shù)的和為 n. 證明證明 設這兩組數(shù)為a ,a ,a、b ,b ,b. 12 p 12

13、 q 已知每一組的數(shù)都是小于 n（nz ）的互不相同的數(shù). 不妨設 a a a,那么對從 a 到 b 的任何滿映ab 射 f，至少存在,使 f()=f().） 1 a 2 a 1 a 2 a s 中至少存在兩個不同的元 nj j j j ni i i i x x x x x x x x 2 2 1 2 2 1 , 使,即,. ji xfxf ji axax 0 ji xxa 令，則即是我們所要求的，是 njni ji ji n xx xx xx 22 22 11 2 2 1 n2 2 1 n2, 21, 不全為零的整數(shù)，且滿足 . nknxxxx jkikjkikk 2 , 2 , 12 例例

14、 7.7. 設為階方陣，證明存在 1，使秩()=秩()=秩anni i a 1i a )( 2i a 證明證明 因為階方陣的秩只能是這+1 個數(shù)之一.nn, 2, 1, 0n ,的個數(shù)多于秩的個數(shù)，由抽屜原理可知，存在,e 120 , nn aaaaaek 滿足 1使lkln 秩()= 秩(), k a l a 但 秩()秩()秩(), k a 1k a l a 所以 秩()=秩(), k a 1k a 利用此式與秩的性質(zhì)得 秩()秩()+秩()-秩(),abcabbcb 這里的是任意三個可乘矩陣，用數(shù)學歸納法可證cba, 秩()=秩(). mk a 1mk a 其中為非負整數(shù)，故命題的結(jié)論成

15、立. 秩()=秩()=秩. m i a 1i a )( 2i a 3.43.4 抽象代數(shù)中的應用抽象代數(shù)中的應用 例例 8.8.證明:有限群中的每個元素的階均有限 證明證明 設 g 為 n 階有限群，任取 ag，則由抽屜原理可知中必 231 , nn a aaaa 有相等的不妨設于是有，從而 a 的階有限,11 st aatsn s t ae 例例 9.9.證明只含有限個理想的非零整環(huán) r 必是域. 證明證明 根據(jù)魏得邦定理，只需證明 r 是除環(huán)即可. (設是環(huán)且，則 r 是除環(huán)當且僅當對 r 中任意元素，方程r1rba, 0 ax=b 或 ya=b 在中有解)r 在 r 中任取元素.ba,

16、0 考慮, 2 , 1, 1 iraryyan tt 易知，都是的理想., 32 rararar 但由于整環(huán) r 只有有限個理想，根據(jù)抽屜原理. 必存在正整數(shù) s 與 t 滿足 s2,則存在最小正整數(shù) r(p,q),使得當 nr(p,q)時，用紅藍兩色涂的邊，則或存在一個藍色的,或存在一個紅色 n k p k 的. p k ramsey 定理（狹義）的內(nèi)容任意六個人中要么至少三個人認識，要么至少 三個不認識. ramsey 定理可以視為抽屜原理的推廣，1947 年，匈牙利數(shù)學家把這一原理 引進到中學生數(shù)學競賽中，當年匈牙利全國數(shù)學競賽有一道這樣的試題：“證 明：任何六個人中，一定可以找到三個互

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

18、找 到了三個互不認識的人； 如果 b、c、d 三人中有兩個互相認識，例如 b 與 c 認 識，那么，a、b、c 就是三個互相認識的人.不管哪種情況，本題的結(jié)論都是成 立的. 或者我們可以用染色的方法.以 6 個頂點分別代表 6 個人，如果兩人相識， 則在相應的兩點間連一條紅邊，否則在相應的兩點間連一藍邊. 命題 1.對 6 個頂點的完全圖任意進行紅、藍兩邊著色，都存在一個紅 6 k 色三角形或藍色三角形. 證明如下 首先，把這 6 個人設為 a、b、c、d、e、f 六個點.由 a 點可以引出 ab、ac、ad、ae、af 五條線段. 設如果兩個人認識，則設這兩個人組成的線段為紅色；如果兩個人不

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

20、6 k 同色三角形. 由于命題 2 是要證明至少存在兩個同色三角形的問題，而抽屜原理一般只 局限在證明至少存在一個或必然存在一個的問題，所以對于上述命題抽屜原理 就顯得無能為力，這時需要運用 ramsey 定理來解決問題. 證明 設是的六個頂點，由上面的命題 1 可知，對, 21 vv 6543 ,vvvv 6 k 任意進行紅、藍兩邊著色都有一個同色三角形，不妨設是紅色三角 6 k 321 vvv 形.以下分各種情況來討論 (1)若均為藍邊，如圖 1 所示，則若之間有一藍邊， 615141 ,vvvvvv 654 ,vvv 不妨設為，則三角形為藍色三角形；否則，為紅色三角形. 54v v 54

21、1 vvv 654 vvv 圖 1 圖 2 (2)若中有一條紅邊，不妨設為紅邊，此時若邊 615141 ,vvvvvv 41v v 中有一條紅邊，不妨設是紅邊，則是一紅色三角形，見圖 4342 ,vvvv 43v v 431 vvv 2. 以下就均為藍邊的情況對與相關(guān)聯(lián)的邊的顏色進行討論. 4342 ,vvvv 4 v ()若中有一藍邊，不妨設為藍邊，如圖 3，此時，若 6454 ,vvvv 54v v 均為紅邊，則是紅色三角形；否則，或是藍 5352 ,vvvv 532 vvv 542 vvv 543 vvv 色三角形. ()若均為紅邊，見圖 4，此時，若之間有一條紅邊，不 6454 ,vv

22、vv 651 ,vvv 妨設為紅邊，則為紅色三角形；否則，為藍色三角形. 51v v 541 vvv 651 vvv 圖 3 圖 4 由以上對各種情況的討論知，對的任意紅、藍兩邊著色均有兩個同色三 6 k 角形. 從以上例子可知，抽屜原理在應用上確有不足之處，之上只是個特例，至 于在別的領(lǐng)域中的不足之處還需我們進一步的探索. 抽屜原理的應用領(lǐng)域十分廣泛，涉及到高等數(shù)學的多個學科，并且在生活 中也有廣泛的應用，可以巧妙的用于解決一些復雜問題，本文主要梳理總結(jié)了 它在數(shù)論、離散、高等代數(shù)及抽象代數(shù)中的應用，其不足之處也由 ramsey 定理 進行了補充，使其能夠更好的應用與問題解決當中. 6.6.

23、參考文獻參考文獻 1陳景林,閻滿富.組合數(shù)學與圖論.北京中國鐵道出版社出版,2000.04 2盧開澄.組合數(shù)學（第 3 版）.北京清華大學出版社，2002.07 3濮安山.“高等代數(shù)中抽屜原理的應用”.哈師大自然科學學報 ，2001.06 4王向東,周士藩等.高等代數(shù)常用方法m.1989.11. 5楊子胥.近世代數(shù).北京.高等教育出版社.2003.12 6嚴士健.抽屜原則及其它的一些應用j.數(shù)學通報,1959 7曹汝成.組合數(shù)學m.華東理工大學出版社,2000. 畢業(yè)論文（設計）選題審批表畢業(yè)論文（設計）選題審批表 學院：數(shù)學科學學院(章)系別/教研室：數(shù)學與應用數(shù)學時間：2011 年 10

24、月 25 日 題目名稱抽屜原理及其應用 課題性質(zhì)a 基礎研究 b 基礎應用研究 c 應用研究 教師姓名 職稱講師學位碩士 課題來源 a.科研 b.生產(chǎn) c.教學 d.其它 e.學生 自擬 課 題 情 況 成果類別a.論文 b.設計 主要 研究 內(nèi)容 與 研究 目標 本文簡述了抽屜原理普遍使用的簡單形式、各種推廣形式，著重闡述其在數(shù) 論和離散數(shù)學、高等代數(shù)及抽象代數(shù)中的應用,及在生活中的應用，可以巧妙地解 決一些復雜問題，并根據(jù)抽屜原理的不足之處引入抽屜原理的推廣定理 ramsey 定 理. 以往抽屜原理的相關(guān)文章或集中于中小學數(shù)學方面或比較零散片面，本文就 本人所學過的高等數(shù)學的幾門學科中抽屜

25、原理的應用進行比較全面的梳理總結(jié). 生活中的應用這一部分本文區(qū)別于其它相關(guān)文章中大量的缺乏實際意義的事 例，選取與生活貼近的如賽程安排、資源分配等問題進行闡述，更好地突出抽屜 原理在實際生活中的用處. 指導教師簽字： 年 月 日 選題學生簽字： 年 月 日 系所 或教 研室 審題 意見負責人簽字: 年 月 日 學院 審批 意見學院學位分委員會主任簽字: 年 月 日 本科畢業(yè)論文（設計）開題報告本科畢業(yè)論文（設計）開題報告 論文題目： 抽屜原理及其應用 學院名稱： 數(shù)學科學學院 專 業(yè)： 數(shù)學與應用數(shù)學 學生姓名： 學 號： 指導教師： 2011 年 11 月 16 日 一、選題的性質(zhì)一、選題的

26、性質(zhì) 基礎應用研究 2 2、選題的目的和意義選題的目的和意義 研究抽屜原理在高等數(shù)學中數(shù)論、離散數(shù)學、高等代數(shù)、抽象代數(shù)等多個學科中的運 用，對其在高等數(shù)學各方面的運用進行較為全面的梳理總結(jié)，加深對抽屜原理的理解，使 復雜的數(shù)學問題能夠在抽屜原理的作用下得到靈活巧妙的解決. 三、與本課題相關(guān)的國內(nèi)外研究現(xiàn)狀，預計可能有所創(chuàng)新的方面三、與本課題相關(guān)的國內(nèi)外研究現(xiàn)狀，預計可能有所創(chuàng)新的方面 以往抽屜原理的相關(guān)文章或集中于中小學數(shù)學方面或比較零散片面，本文的主要創(chuàng)新 點是就本人所學過的高等數(shù)學的幾門學科中抽屜原理的應用進行比較全面的梳理總結(jié). 生活中的應用這一部分本文區(qū)別于其它相關(guān)文章中大量的缺乏實

27、際意義的事例，選取 與生活貼近的如賽程安排、資源分配等問題進行闡述，更好地突出抽屜原理在實際生活中 的用處. 4 4、課題研究的可行性分析課題研究的可行性分析 五、課題研究的策略、方法和步驟五、課題研究的策略、方法和步驟 六、預期成果形式描述六、預期成果形式描述 七、指導教師意見七、指導教師意見 指導教師簽字： 年 月 日 八、學院學位分委員會意見八、學院學位分委員會意見 學院學位分委員會主任簽字： 年 月 日 本科畢業(yè)論文（設計）教師指導記錄表本科畢業(yè)論文（設計）教師指導記錄表 學院：數(shù)學科學學院 系別：_ 專業(yè)：數(shù)學與應用數(shù)學 論文（設計）題目： 抽屜原理及其應用 學生姓名 學號指導教師

28、職稱講師 計劃完成時間：2012 年 5 月 18 日 指導情況紀錄（含指導時間、指導內(nèi)容） 1、2011 年 11 月 20 日，指導老師開始指導論文的選題，對選題的角度，選題 的高度，所選課題所應該涵蓋的范圍及研究內(nèi)容等應該注意的問題都作了一個 詳盡的解釋，經(jīng)過幾次的交流，最終在老師的指導下將題目敲定，并且對論文 的結(jié)構(gòu)框架也有了大體的安排。 2、2012 年 4 月 16 日，在指導老師的指導下，依選定的題目開始搜集資料，整 理數(shù)據(jù)資料。 3、2012 年 5 月 5 日，在老師的指導下，進行論文的撰寫，并將初稿上交。 4、2012 年 5 月 7 日，老師提出第一次的論文修改意見，內(nèi)容

29、包括：論文格式、 標點符號、中英文摘要、關(guān)鍵詞、應用數(shù)據(jù)、措辭、資料來源等。 5、2012 年 5 月 16 日，論文第二次修改完成以及開題報告指導修改完成。 指導教師簽字： 學生簽字： 學院學位分委員會主任簽字： 年 月 日 指導教師意見指導教師意見 （包括選題的意義，資料收集或?qū)嶒灧椒?、?shù)據(jù)處理等方面的能力，論證或?qū)嶒炇欠窈侠恚?主要觀點或結(jié)果是否正確，有何獨到的見解或新的方法，基礎理論、專業(yè)知識的掌握程度 及寫作水平等，并就該論文是否達到本科畢業(yè)論文水平做出評價） 成績： 指導教師（簽名）： 年 月 日 注：成績按優(yōu)、良、中、合格、不合格五級分制計. 評閱人意見評閱人意見 （包括選題的意義，資料收集或?qū)嶒灧椒?、?shù)據(jù)處理等方面的能力，論證或?qū)?驗是否合理，主要觀點或結(jié)果是否正確，有何獨到的見解或新的方法，基礎理 論、專業(yè)知識的掌握程度及寫作水平等，并就該論文是否達到本科畢業(yè)論文水 平做出評價） 成績： 評閱人（簽名