抽屜原理的應用與推廣-畢業(yè)論文設計

PAGEvPAGEi目錄1引言 12抽屜原理的形式 13抽屜原理在高等數(shù)學中的應用 33.1數(shù)論問題中的應用 33.2高等代數(shù)中的應用 63.3集合論中的應用 83.4不等式中的應用 94抽屜原理的推廣 104.1抽屜原理在無限集上的推廣 114.2抽屜原理的推廣定理-定理 125抽屜原理在實際生活中的應用 15參考文獻 17致謝 18抽屜原理的應用與推廣Xxxxxx系本xxxxx班xxxxxx指導教師：xxxxxxx摘要：本文簡述了抽屜原理普遍使用的簡單形式、各種推廣形式，著重簡述其在數(shù)論和高等數(shù)學及無限集中的應用，及在生活中的應用，可以巧妙地解決一些復雜問題，并根據(jù)抽屜原理的不足之處引入抽屜原理的推廣定理Ramsey定理。關(guān)鍵詞：抽屜原理，有限集，無限集，Ramsey定理。TheDraweroftheprincipleofpromotionLixxxxxxxxxxxClassxxxx,MathematicsDepartmentTutor:xxxxxxxxxxAbstract:Thispaperintroducesthewidespreaduseofsimpleformsandallkindsofextendedformsofthedrawerprinciple,focusingontheapplicationofThedrawerprincipleinthenumbertheory,highermathematicsandinfiniteseta,andalsothereallife.Itcansolveablysomecomplicatedproblems,andaccordingtotheprincipleofdrawertheshortcomingsoftheprincipleofintroducingthedrawertheoremRamseytheorem.Keywords:thedrawerprinciple,finiteset,infinitesets,Rameytheorem. 1引言抽屜原理又稱鴿巢原理、鞋箱原理或重疊原理，是一個十分簡單又十分重要的原理。它是由德國著名數(shù)學家狄利克雷首先發(fā)現(xiàn)的，因此也叫狄利克雷原理。抽屜原理簡單易懂，主要用于證明某些存在性或必然性的問題，不僅在數(shù)論、組合論以及集合論等領(lǐng)域中有著廣泛應用，在高等數(shù)學中的應用進行了梳理，將抽屜原理的解題思路拓展到高等數(shù)學的其他領(lǐng)域，有助于更好的理解抽屜原理，并舉例闡述了抽屜原理在現(xiàn)實生活中的應用，以及根據(jù)抽屜原理的不足引出的定理及其推廣。2抽屜原理的形式什么是抽屜原理？舉個簡單的例子說明，就是將3個球放入2個籃子里，無論怎么放，必有一個籃子中至少要放入2個球，這就是抽屜原理?；蛘呒俣ㄒ蝗壶澴语w回巢中，如果鴿子的數(shù)目比鴿巢多，那么一定至少有一個鴿籠有糧食或兩只以上的鴿子，這也是鴿巢原理這一名稱的得來。抽屜原理簡單直觀，很容易理解。而這個看似簡單的原理在高等數(shù)學中有著很大的用處，對于數(shù)論、高等數(shù)學、集合論以及無限集中的復雜問題，可以利用抽屜原理巧妙的解答出來。下面首先從抽屜原理的形式入手，然后研究它在高等數(shù)學中的應用。我們最常用的抽屜原理只是抽屜原理的簡單形式，就是將個元素或者更多的元素放入個抽屜中，則至少有一個抽屜里放有兩個或兩個以上的元素。除了這種普遍的形式外，抽屜原理還有其他形式的推廣、原理及形式。推廣1若將個物品放入個盒子中，則至少有一個盒子中有個物品。推廣2設是個整數(shù)，而且,則中至少有一個數(shù)不小于.推廣3若將個物品放入個盒子中，則至少有一個盒子中有不少于[]個物品。其中，[]是不少于的最小整數(shù)。原理1把多于(乘以)個的物體放到個抽屜里，則至少有一個抽屜里有個或多于個的物體。原理2把無窮多個元素放入有限個集合里，則一定有一個集合里含有無窮多個元素。原理3把個物體放入個抽屜中，其中必有一個抽屜中至多有個物體。原理4設是兩個有限集合，對于任意從到的函數(shù)，D必有個元素,使得.原理5設為無限集，為有限集，對于任意有到的函數(shù)，用表示的值域，則的各個元素的原象的集合中，必有一個是無限集。原理6設是不可數(shù)集，是有限集或可數(shù)集，對于任意從到的函數(shù)，用表示的值域，則的各個元素的原象的集合中，必有一個是不可數(shù)集。原理7設同是不可數(shù)(或可數(shù))集,,對于任意從到的函數(shù),中必有兩個元素,,使.原理8設都是正整數(shù)，如果把個物品放入個盒子，那么或者第1個盒子至少包含個物品，或者第2個盒子至少包含個物品，……，或者第個盒子至少包含個物品。形式1個元素分為個集合中，那么至少有一個集合中存在個元素。形式2個元素分為個集合中，幾種必有一個集合中元素個數(shù)大于或等于.形式3元素分為個集合，那么必有一個,在第個集合中元素的個數(shù).形式4設有無窮多個元素按任一確定的方式分成有限個集合，那么至少有一個集合含有無窮多個元素。3抽屜原理在高等數(shù)學中的應用以上的幾種形式就是我們解題時常用到的抽屜原理的表示形式，接下來，在了解了抽屜原理的基本形式以及多位學者所發(fā)展的推廣形式的基礎上，我們通過一些比較典型的實例來說明抽屜原理在高等數(shù)學中的數(shù)論、集合論、高等數(shù)學、不等式這四個方面的應用。3.1數(shù)論問題中的應用狄利克雷定理為無理數(shù)，則對任意的正整數(shù)，存在整數(shù)，滿足.（狄利克雷是經(jīng)典的數(shù)論問題）。而抽屜原理的應用是：如果有個正整數(shù)被除，則必有兩個設為對模同余，即，因此，｜.例1證明任意五個整數(shù)中，必有三個整數(shù)的和是3的倍數(shù)。分析與證明任一整數(shù)被3除余數(shù)只可能是0,1,2.若給定的五個整數(shù)被3除所得的余數(shù)中0,1,2都出現(xiàn)，那么余數(shù)分別為0,1,2的三個數(shù)的的和一定能被3整除，如果余數(shù)中至多出現(xiàn)，0,1,2,中的兩個，那么由抽屜原理，其中必有一個余數(shù)至少出現(xiàn)三次，而這余數(shù)相同的三個數(shù)的和一定能被3整除。因此在任意五個整數(shù)中，必有三個整數(shù)的和是3的倍數(shù)。例2中國剩余定理令和為兩個互素的正整數(shù)，并令和為整數(shù)，且以及,則存在一個正整數(shù)，使得除以的余數(shù)是,并且除以的余數(shù)為.即可以寫成的同時又可以寫成的形式，這里和是整數(shù)。分析與證明為了證明這個結(jié)論考慮個整數(shù)這些整數(shù)中的每一個除以都余，設其中的兩個除以有相同的余數(shù)，令這兩個數(shù)為和,其中,因此,存在兩整數(shù)和,使得及，這兩個方程相減可得.于是是的一個因子，由于和沒有除1之外的公因子，因此是的因子，然而，意味著，也就是說不可能是的因子，該矛盾產(chǎn)生于我們的假設：個整數(shù)中有兩個除以會有相同的余數(shù)。因此這個數(shù)中的每一個數(shù)除以都有不同的余數(shù)，根據(jù)抽屜原理，個數(shù)中的每一個作為余數(shù)都要出現(xiàn)，特別地，數(shù)也是如此。令為整數(shù)，滿足，且使數(shù)除以余數(shù)為，則對于某個適當?shù)?，有因此，且，從而具有所要求的性質(zhì)。例3求證在有40個不同的正整數(shù)所組成的等差數(shù)列中,至少有一項不能表示成的形式。證明假設存在一個各項不同且均能表示成的形式的40項等差數(shù)列。設這個等差數(shù)列為，其中，.設,,其中,表示不超過實數(shù)的最大整數(shù)。則.接下來研究這個數(shù)列中最大的14項.首先證明中至多有一個不能表示成或的形式。若中的某一個()不能表示成或的形式,由假設知一定存在非負整數(shù),使得.由的定義可知又因為不能表示成或的形式,所以若,則與矛盾。若,則與矛盾。因此,只有.故中至多有一個不能表示成或的形式。所以,中至少有13個能表示成或的形式。由抽屜原理知，至少有七個能表示成或中的同一種形式。有七個能表示成的形式。設，其中，.則是某個公差為的14項等差數(shù)列中的七項,所以,.顯然,.故矛盾。有七個能表示成的形式。設,其中,.則是某個公差為的14項等差數(shù)列中的七項。而,矛盾。綜上,假設不成立.故原題得證。3.2高等代數(shù)中的應用例4已知齊次線性方程組其中,證明存在不全為零的整數(shù)適合證明令，，則該齊次線性方程組可寫成設集合S={}D={:XS}映射是一個滿射.顯然=,因為{-1，0，1}，所以對每個XS，它的2n個分量適合≤（i=1,2,,n）因此又根據(jù)抽屜原理映射形式設和是兩個有限集，如果>那么對從到的任何滿映射，至少存在,,使.S中至少存在兩個不同的元使,即.令，則即是我們所要求的，是不全為零的整數(shù)，且滿足.例5設為階方陣，證明存在1，使秩=秩=秩證明因為階方陣的秩只能是這+1個數(shù)之一。令,的個數(shù)多于秩的個數(shù)，由抽屜原理可知，存在,滿足1<使秩=秩,但秩秩…秩,所以秩=秩,利用此式與秩的性質(zhì)得秩秩+秩-秩,這里的是任意三個可乘矩陣，用數(shù)學歸納法可證秩=秩.其中為非負整數(shù)，故命題的結(jié)論成立.秩=秩=秩=….3.3集合論中的應用從集合論的原理來討論抽屜原理,主要應用集合論的映射來闡述抽屜原理,有在倍數(shù)問題、幾何問題、涂色問題、經(jīng)濟問題等方面的應用，本文主要介紹倍數(shù)問題和經(jīng)濟問題。例6（倍數(shù)問題的應用）自1至100這一百個自然數(shù)中，如果任取51個數(shù)，那么其中至少有兩個數(shù)，使一個數(shù)是另一個數(shù)的倍數(shù)。證明我們知道形如（為自然數(shù)，）的數(shù)之間有倍數(shù)關(guān)系，對任何一個偶數(shù)，經(jīng)反復提取因數(shù)2，最后總能表示為：奇數(shù)乘以的形式，因此設其中：………,∴對任意.使,即至少存在兩個元素同時對應到中某個中，這兩個數(shù)必有倍數(shù)關(guān)系，證畢。例7（經(jīng)濟問題的應用）十七家公司中的每一家公司都要與其余十六家公司洽談業(yè)務，在他們洽談中所討論的問題僅三個，而任何兩家公司洽談中所討論的是同一個問題，證明有三家公司洽談時所討論的是同一個問題。證明設為某一公司向其十六公司洽談業(yè)務，則，為洽談時所討論的問題，則∴每一家公司與其余十六家洽談業(yè)務時至少對六家討論的是某一個問題，若這六家中至少有兩家也討論這一個問題，則原題得證。若六家中沒有任何兩家討論這個問題，那么他們之間只能討論另外兩個問題，又∴這六家中至少有三家在討論相同的問題，證畢。3.4不等式中的應用例8若實數(shù)滿足，求證:.證明由于,所以中必存在2個同時不大于1,或者同時不小于1,不妨設為則有所以.例9已知,求證:.證明根據(jù)抽屜原理可知:中至少有兩個同時不大于常數(shù)，或者不小于常數(shù)，于是,不妨設為這樣就得到,變形,得由柯西不等式,易得于是,有即①再根據(jù)柯西不等式,便得②由①+②,得故.4抽屜原理的推廣抽屜原理有很多推廣，但一般都只局限于有限集范圍。下面將用函數(shù)的觀點敘述抽屜原理，進而在可數(shù)集和不可數(shù)集上推廣它。即:設是兩個有限集合,對于任意從到的函數(shù),必有個元素,使得.同時對于一些更加復雜的有關(guān)存在性的組合問題,抽屜原理顯得無能為力,這是我們就需要運用抽屜原理的推廣定理定理來解決問題。因此我們通過一些比較典型的實例和定理來說明抽屜原理在無限集中的推廣和抽屜原理的推廣定理定理。4.1抽屜原理在無限集上的推廣例10證明存在長度趨于零的區(qū)間列而它的每個區(qū)間都是不可數(shù)的。解決這個問題,一般可先任意造一個長度趨于零的區(qū)間列,不妨用表示這個區(qū)間列,又由于區(qū)間是不可數(shù)的,從而可以通過在與之間建立一個雙射,使問題得到解決。證明取的中點,設顯然,根據(jù)原理6，與中必有一個是不可數(shù)的,不妨設其為而.再取的中點,同上證法,又可得到不可數(shù)的區(qū)間,而.如此繼續(xù)下去,可得不可數(shù)的區(qū)間,而.顯然就是所要找的區(qū)間列。例11有一棋手,賽前要訓練77天,他計劃在訓練期間,每天至少賽一場,總共要賽132場.試證明無論怎樣安排,總有連續(xù)的一些天共賽21場。證明用表示從第一天起,到第天為止共賽的次數(shù),顯然數(shù)列是嚴格單調(diào)增加的,且.當數(shù)列中,有的數(shù)加21后,恰等于數(shù)列中的另一個數(shù)時,則問題得證。當數(shù)列中,任何數(shù)加21后,都不等于數(shù)列中的數(shù)時,數(shù)列也是嚴格單調(diào)增加的,且數(shù)列中的數(shù)均不同于數(shù)列中的數(shù),而.把函數(shù)關(guān)系看做是“數(shù)列與數(shù)列中的每個元素都唯一對應一個數(shù)”由此,可以確認“集”是數(shù)列數(shù)列;“集”是,根據(jù)抽屜原理“集”中必有兩個元素對應同一個數(shù),由于與都是嚴格單調(diào)增加的數(shù)列,這兩個元素不可能在一個數(shù)列中.即這兩個元素分別在與這兩個數(shù)列中.不妨設此二元素分別為和即.(顯然),即從第天以后(不包括第天)到第天為止(包括第天)共賽了21場。4.2抽屜原理的推廣定理-定理(1903-1930)是英國數(shù)理邏輯學家,他把抽屜原理加以推廣，得出廣義抽屜原理，也稱為定理。定理設是正整數(shù)，,則存在最小正整數(shù),使得當時，用紅藍兩色涂的邊，則或存在一個藍色的,或存在一個紅色的.定理可以視為抽屜原理的推廣，1947年，匈牙利數(shù)學家把這一原理引進到中學生數(shù)學競賽中，當年匈牙利全國數(shù)學競賽有一道這樣的試題：“證明：任何六個人中，一定可以找到三個互相認識的人，或者三個互不認識的人.”在1958年6-7月號美國《數(shù)學月刊》同樣也登載著這樣一個有趣的問題“任何六個人的聚會，總會有3人互相認識或3人互相不認識.”這就是著名的問題。這個問題乍看起來，似乎令人匪夷所思.但如果懂得抽屜原理，要證明這個問題是十分簡單的：我們用代表六個人，從中隨便找一個，例如A把其余五個人放到“與認識”和“與不認識”兩個“抽屜”里去，根據(jù)抽屜原理，至少有一個抽屜里有三個人.不妨假定在“與認識”的抽屜里有三個人，他們是.如果三人互不認識，那么我們就找到了三個互不認識的人；如果三人中有兩個互相認識，例如與認識，那么，就是三個互相認識的人.不管哪種情況，本題的結(jié)論都是成立的?；蛘呶覀兛梢杂萌旧姆椒āＲ?個頂點分別代表6個人，如果兩人相識，則在相應的兩點間連一條紅邊，否則在相應的兩點間連一藍邊。命題1對6個頂點的完全圖任意進行紅、藍兩邊著色，都存在一個紅色三角形或藍色三角形。證明：首先，把這6個人設為六個點.由點可以引出五條線段。設如果兩個人認識，則設這兩個人組成的線段為紅色；如果兩個人不認識，則設這兩個人組成的線段為藍色。由抽屜原理可知這五條線段中至少有三條是同色的。不妨設為紅色。若或為紅色，則結(jié)論顯然成立。若和均為藍色，則若為紅色，則一定有三個人相互認識；若為藍色，則一定有三個人互相不認識。上述的問題等價于下面的命題1.命題1對6個頂點的完全圖任意進行紅、藍兩邊著色，都存在一個紅色三角形或藍色三角形。命題1運用抽屜原理可以很容易很簡便地對其進行證明.現(xiàn)將命題1推廣成下面的命題2.命題2對六個頂點的完全圖任意進行紅、藍兩邊著色，都至少有兩個同色三角形。由于命題2是要證明至少存在兩個同色三角形的問題，而抽屜原理一般只局限在證明至少存在一個或必然存在一個的問題，所以對于上述命題抽屜原理就顯得無能為力，這時需要運用定理來解決問題。證明設是的六個頂點，由上面的命題1可知，對任意進行紅、藍兩邊著色都有一個同色三角形，不妨設△是紅色三角形.以下分各種情況來討論(1)若均為藍邊，如圖1所示，則若之間有一藍邊，不妨設為，則三角形△為藍色三角形；否則，△為紅色三角形。圖1圖2(2)若中有一條紅邊，不妨設為紅邊，此時若邊中有一條紅邊，不妨設是紅邊，則△是一紅色三角形，見圖2.以下就均為藍邊的情況對與相關(guān)聯(lián)的邊的顏色進行討論。(ⅰ)若中有一藍邊，不妨設為藍邊，如圖3，此時，若均為紅邊，則△是紅色三角形；否則，△或△是藍色三角形。(ⅱ)若均為紅邊，見圖4，此時，若之間有一條紅邊，不妨設為紅邊，則△為紅色三角形；否則，△為藍色三角形。圖3圖4由以上對各種情況的討論知，對的任意紅、藍兩邊著色均有兩個同色三角形。從以上例子可知，抽屜原理在應用上有不足之處，之上只是個特例，至于在別的領(lǐng)域中的不足之處還需我們進一步的探索。5抽屜原理在實際生活中的應用抽屜原理不僅在高等數(shù)學中具有廣泛應用，在我們的實際生活中，也能處處發(fā)現(xiàn)抽屜原理的影子.如招生錄取、賽程安排、資源分配、職稱評定等等，都不難看到抽屜原理的作用。其實早在中國古代的春秋戰(zhàn)國時期就有了運用抽屜原理的例子，那就是《晏子春秋》中的“二桃殺三士”的典故，將兩個桃子賞賜給三名勇士，在這里可以將桃子看作抽屜，三個人作為元素放進抽屜，則根據(jù)抽屜原理，一定有一個抽屜要放入兩個或兩個以上的元素，回到問題情境中就是一定要有兩個人吃一個桃子，導致這三名勇士最后自相殘殺而亡，這就是著名的“二桃殺三士”。后來宋朝時期費袞在他的《梁谿漫志》中就曾運用抽屜原理來駁斥但是流行的“算命”一說，費袞指出算命是把一個人出生的年、月、日、時作為依據(jù)，把這些作為“抽屜”，則不同的抽屜有12×360×60＝259200個。把所有的人作為“物品”，則進入同一抽屜的人有成千上萬個，因此“生時同者必不為少矣”.既然“八字”相同，“又何貴賤貧富之不同也?這是大基數(shù)的社會現(xiàn)象，常給人感覺世事很奇巧，碰到同生日、同名的人，這也是抽屜原理在生活中的應用。而生活中也有常見的抽屜原理的應用之處，如“搶凳子”游戲，一群人搶凳子，凳子數(shù)比人少，必然淘汰一些人,又或者是13個人中總有2人是同一個月份出生，52張撲克牌中取出5張總有2張花色相同，在100米長的小路上種101棵小樹，不管怎么種，至少有兩棵樹苗之間的距離不超過1米等等。下面我們再來看幾個例子。例1220名運動員進行乒乓球比賽,每兩名運動員都要比賽一場,每場比賽五局三勝(采取11分制).全部比賽結(jié)束后所有格局比賽最高得分為15:13.那么至少有多少局的比分是相同的?解20名運動員，每兩名運動員都要比賽一場，根據(jù)乘法原理，一共賽了190（2019）場(因為甲同乙比賽與乙同甲比賽只能算同一場,所以要除以2).因為每場比賽至少三局,所以一共至少比賽570(1903)局。根據(jù)題目條件,乒乓球比賽的可能比分為(11:0).(11:1).(11:2).…(11:9).(12:10).(13:11).(14:12).(15:13)共計14種.把這14種情況看作14個抽屜。因為570＞1440.所以至少有41局的比分是相同的。例1349名學生回答3個問題,每個問題的得分是0,1,…,7,證明:存在兩個學生對于每個問題,的得分不少于的得分。證明設在三個題目的得分為,即證:若存在兩位同學在一二題的得分相同,則結(jié)論成