數(shù)學(xué)奧賽輔導(dǎo)第七講抽屜原則容斥原理

1、數(shù)學(xué)奧賽輔導(dǎo) 第七講 抽屜原則、容斥原理知識(shí)、方法、技能i抽屜原則10個(gè)蘋(píng)果放入9個(gè)抽屜中，無(wú)論怎么放，一定有一個(gè)抽屜里放了2個(gè)或更多個(gè)蘋(píng)果.這個(gè)簡(jiǎn)單的事實(shí)就是抽屜原則.由德國(guó)數(shù)學(xué)家狄利克雷首先提出來(lái)的.因此，又稱為狄利克雷原則.將蘋(píng)果換成信、鴿子或鞋，把抽屜換成信筒、鴿籠或鞋盒，這個(gè)原則又叫做信筒原則、鴿籠原則或鞋盒原則.抽屜原則是離散數(shù)學(xué)中的一個(gè)重要原則，把它推廣到一般情形就得到下面幾種形式：原則一：把m個(gè)元素分成n類（m>n），不論怎么分，至少有一類中有兩個(gè)元素.原則二：把m個(gè)元素分成n類（m>n）（1）當(dāng)n|m時(shí)，至少有一類中含有至少個(gè)元素；（2）當(dāng)n|m時(shí)，至少有一類中含

2、有至少+1個(gè)元素.其中n m表示n是m的約數(shù)，n m表示n不是m的約數(shù)，表示不超過(guò)的最大整數(shù).原則三：把個(gè)元素分成n類，則存在一個(gè)k，使得第k類至少有個(gè)元素.原則四：把無(wú)窮多個(gè)元素分成有限類，則至少有一類包含無(wú)窮多個(gè)元素.以上這些命題用反證法極易得到證明，這里從略.一般來(lái)說(shuō)，適合應(yīng)用抽屜原則解決的數(shù)學(xué)問(wèn)題具有如下特征：新給的元素具有任意性.如10個(gè)蘋(píng)果放入9個(gè)抽屜，可以隨意地一個(gè)抽屜放幾個(gè)，也可以讓抽屜空著. 問(wèn)題的結(jié)論是存在性命題，題目中常含有“至少有”、“一定有”、“不少于”、“存在”、“必然有”等詞語(yǔ)，其結(jié)論只要存在，不必確定，即不需要知道第幾個(gè)抽屜放多少個(gè)蘋(píng)果.對(duì)一個(gè)具體的可以應(yīng)用抽屜

3、原則解決的數(shù)學(xué)問(wèn)題還應(yīng)搞清三個(gè)問(wèn)題：（1）什么是“蘋(píng)果”？（2）什么是“抽屜”？（3）蘋(píng)果、抽屜各多少？用抽屜原則解題的本質(zhì)是把所要討論的問(wèn)題利用抽屜原則縮小范圍，使之在一個(gè)特定的小范圍內(nèi)考慮問(wèn)題，從而使問(wèn)題變得簡(jiǎn)單明確.用抽屜原則解題的基本思想是根據(jù)問(wèn)題的自身特點(diǎn)和本質(zhì)，弄清對(duì)哪些元素進(jìn)行分類，找出分類的規(guī)律.用抽屜原則解題的基本思想是根據(jù)問(wèn)題的自身特點(diǎn)和本質(zhì)，弄清對(duì)哪些元素進(jìn)行分類，找出分類的規(guī)律.用抽屜原則解題的關(guān)鍵是利用題目中的條件構(gòu)造出與題設(shè)相關(guān)的“抽屜”. 容斥原則當(dāng)我們?cè)噲D對(duì)某些對(duì)象的數(shù)目從整體上計(jì)數(shù)碰到困難時(shí)，考慮將整體分解為部分，通過(guò)對(duì)每個(gè)部分的計(jì)數(shù)來(lái)實(shí)現(xiàn)對(duì)整體的計(jì)數(shù)是一種明

4、智的選擇.將整體分解為部分也就是將有限集x表示成它的一組兩兩互異的非空真子集a1，a2，an的并集，即叫做集合x(chóng)的一個(gè)覆蓋.一個(gè)特殊情況是，集族中的任意兩個(gè)集合都不相交，這時(shí)我們稱集族為集合x(chóng)的一個(gè)（完全）劃分.如為集合x(chóng)的劃分，則對(duì)集合x(chóng)的計(jì)數(shù)可通過(guò)熟知的加法公式 進(jìn)行，但是，要找到一個(gè)劃分并且其中所有子集易于計(jì)數(shù)的有時(shí)并非易事. 我們可以考慮通過(guò)對(duì)任意的集族中的子集的計(jì)數(shù)來(lái)計(jì)算|x|，當(dāng)集族中至少存在兩個(gè)集合的交非空時(shí)，我們稱這個(gè)覆蓋為集合x(chóng)的不完全劃分. 對(duì)于集合x(chóng)的不完全劃分，顯然有有 因?yàn)樵谟?jì)算|ai|時(shí)出現(xiàn)了對(duì)某些元素的重復(fù)計(jì)數(shù)，為了計(jì)算|x|，就得將式右邊重復(fù)計(jì)算的部分減去，如果

5、減得超出了，還得再加上，也就是說(shuō)我們要做“多退少補(bǔ)”的工作.完成這項(xiàng)工作的準(zhǔn)則就是容斥原理. 是十九世紀(jì)英國(guó)數(shù)學(xué)家西爾維斯提出的. 容斥原理有兩個(gè)公式.1容斥公式定理1 設(shè) 證明：當(dāng)由加法公式有 結(jié)論成立.若n=k時(shí)結(jié)論成立，則由 知，時(shí)結(jié)論成立.由歸納原理知，對(duì)任意自然數(shù)n，公式成立.公式稱為容斥公式，顯然它是公式的推廣.如果將看成具有性質(zhì)的元素的集合，那么就是至少具有n個(gè)性質(zhì)之一的元素的集合. 因此，容斥公式常用來(lái)計(jì)算至少具有某幾個(gè)性質(zhì)之一的元素的數(shù)目.2篩法公式與容斥公式討論的計(jì)數(shù)問(wèn)題相反，有時(shí)需要計(jì)算不具有某幾個(gè)性質(zhì)中的任何一個(gè)性質(zhì)的元素的個(gè)數(shù)，即. 為此，我們先引入下面的引理.引理1

6、 設(shè)a關(guān)于全集i的補(bǔ)集為，則引理2 引理簡(jiǎn)單證略. 利用二引理改寫(xiě)公式便是定理2 設(shè)為有限集i的子集，則 賽題精講例1設(shè)abc為一等邊三角形，e是三邊上點(diǎn)的全體. 對(duì)于每一個(gè)把e分成兩個(gè)不相交子集的劃分，問(wèn)這兩個(gè)子集中是否至少有一個(gè)子集包含著一個(gè)直角三角形的三個(gè)頂點(diǎn)？（第24屆imo第4題）【證明】如圖i321，在邊bc、ca、ab上分別取三點(diǎn)p、q、r，使顯然arq，bpr，cqp都是直角三角形. 它們的銳角是30°及60°. 設(shè)e1，e2是e的兩個(gè)非空子集，且 由抽屜原則p、q、r中至少有兩點(diǎn)屬于同一子集，不妨設(shè)p、qe1. 如果bc邊上除p之外還有屬于e1的點(diǎn)，那么結(jié)

7、論已明.設(shè)bc的點(diǎn)除p之外全屬于e2，那么只要ab上有異于b的點(diǎn)s屬于e2，設(shè)s在bc上的投影點(diǎn)為，則ssb為直角三角形.再設(shè)ab內(nèi)的每一點(diǎn)均不屬于e2，即除b之外全屬于e1，特別，r、ae1，于是a、q、re1，且aqr為一直角三角形. 從而命題得證.【評(píng)述】此例通過(guò)分割圖形構(gòu)造抽屜. 在一個(gè)幾何圖形內(nèi)有若干已知點(diǎn)，我們可以根據(jù)問(wèn)題的要求把圖形進(jìn)行適當(dāng)?shù)姆指?，用這些分割成的圖形作為抽屜，再對(duì)已知點(diǎn)進(jìn)行分類，集中對(duì)某一個(gè)或幾個(gè)抽屜進(jìn)行討論，使問(wèn)題得到解決. 例2：在1，4，7，10，13，100中任選出20個(gè)數(shù)，其中至少有不同的兩組數(shù)，其和都等于104，試證明之. （第39屆美國(guó)普特南數(shù)學(xué)競(jìng)賽

8、題）【證明】給定的數(shù)共有34個(gè)，其相鄰兩數(shù)的差均為3，我們把這些數(shù)分成如下18個(gè)不相交的集合.1，52，4，100，7，97，49，55.且把它們分作是18個(gè)抽屜，從已知的34個(gè)數(shù)中任取20個(gè)數(shù)，即把前面兩個(gè)抽屜中的數(shù)1和52都取出，則剩下的18個(gè)數(shù)在后面的16個(gè)抽屜中至少有不同的兩個(gè)抽屜中的數(shù)全被取出，這兩個(gè)抽屜中的數(shù)互不相同，每個(gè)抽屜中的兩個(gè)數(shù)的和都是104.【評(píng)述】此例是根據(jù)某兩個(gè)數(shù)的和為104來(lái)構(gòu)造抽屜. 一般地，與整數(shù)集有關(guān)的存在性問(wèn)題也可根據(jù)不同的需要利用整數(shù)間的倍數(shù)關(guān)系、同余關(guān)系來(lái)適當(dāng)分組而構(gòu)成抽屜.例3 設(shè)是嚴(yán)格上升的自然數(shù)列：，求證：在這個(gè)數(shù)列中有無(wú)窮多個(gè)可以表示為，這里是兩

9、個(gè)正整數(shù)，而是兩個(gè)適當(dāng)?shù)恼麛?shù). （第17屆imo第2題）【證明】對(duì)嚴(yán)格上升的自然數(shù)列，取以為模的剩余類，則可分為類 0，1，2，.考慮無(wú)窮數(shù)列由抽屜原則，其中有無(wú)窮多項(xiàng)屬于同一類，不妨設(shè)這一剩余類是r，且記其中數(shù)值最小的那一項(xiàng)為，顯然，于是其中的u是某個(gè)正整數(shù)，其他的屬于這一剩余類的任一項(xiàng)可表示為由于所以有令，這是一個(gè)正整數(shù)，再令，則上式成為顯然，這里的.例4：設(shè)為實(shí)數(shù)，滿足，求證：對(duì)于每一整數(shù)，存在不全為零的整數(shù)并且【證明】由柯西不等式得即.所以，當(dāng) 把區(qū)間等分成個(gè)小區(qū)間，每個(gè)小區(qū)間的長(zhǎng)度為，由于每個(gè)能取k個(gè)整數(shù)，因此個(gè)正數(shù)，由抽屜原則知必有二數(shù)會(huì)落在同一個(gè)小區(qū)間之內(nèi)，設(shè)它們分別是，因此有

10、很明顯，我們有現(xiàn)在取這里i=1,2,n，于是可表示為這里為整數(shù)，適合【評(píng)述】如上例所示，在證明存在某些有界量使相關(guān)的不等式成立時(shí)，可類似地把某區(qū)間劃分為若干小區(qū)間作為抽屜，借用抽屜原則來(lái)證明.例5：一個(gè)國(guó)際社團(tuán)的成員來(lái)自六個(gè)國(guó)家共有1978人，用1，2，1977，1978來(lái)編號(hào)，試證明：該社團(tuán)至少有一個(gè)成員的編號(hào)或者與他的兩個(gè)同胞的編號(hào)之和相等，或者是其中一個(gè)同胞的編號(hào)的兩倍. （第20屆imo第6題）【證明】可用反證法來(lái)證明與本題完全相當(dāng)?shù)南铝袉?wèn)題：把整列1，2，1978按任一方式分成六組，則至少有一組具有這樣的性質(zhì)：其中有一個(gè)數(shù)或等于四組中其他兩數(shù)之和，或等于其中某一個(gè)數(shù)的兩倍.假設(shè)這六組

11、中的每一組數(shù)都不具備上述性質(zhì)，也就是說(shuō)每一組數(shù)都具備下列性質(zhì)，記作性質(zhì)（p）：同組中任何兩數(shù)之差必不在此組中.因?yàn)槿绻羞B同都在同一組中，那么由可知，這組已具備題目所要求的性質(zhì).因1978÷6>329，所以由抽屜原則可以肯定有一個(gè)組a，其中至少有380個(gè)正整數(shù)，現(xiàn)在從a中任意取出330個(gè)數(shù)業(yè)，記其中最大的那個(gè)數(shù)為，把分別減去其余329個(gè)數(shù)而得到329個(gè)差，它們互不相等且均小于1978. 由性質(zhì)（p），它們不會(huì)再在組a中，即應(yīng)屬于其余五組. 又因329÷5÷>65.再由抽屜原則可以肯定有一組b，其中至少含有上述329個(gè)數(shù)中的66個(gè)數(shù)，從b中任取66個(gè)數(shù)且

12、記其中最大的那個(gè)數(shù)為b1，再把b1減去其余65個(gè)數(shù)，得出的差顯然不再屬于b，當(dāng)然也不會(huì)屬于a.假如其中的某一個(gè)數(shù)屬于a，由于與b分別可以寫(xiě)為 其中都屬于a，于是 這就同a具備性質(zhì)（p）的假設(shè)相違背，這就是說(shuō)上述65個(gè)數(shù)必屬其余四個(gè)數(shù)組.由于65÷4>16，所以至少有一組，稱為c，至少會(huì)有上述65個(gè)整數(shù)中的17個(gè)，反復(fù)進(jìn)行上述推理，最后可得一數(shù)組f，其中至少會(huì)有兩個(gè)數(shù)，大數(shù)與小數(shù)之差是一個(gè)小于1978的正整數(shù)，可是它不在a、b、c、d、e、f的任一組中，這顯然是一個(gè)矛盾，這矛盾說(shuō)明至少有一組數(shù)不具備性質(zhì)（p）.即題目的結(jié)論是正確的.【評(píng)述】我們?nèi)菀装l(fā)現(xiàn)，如果把此題中1978改為任

13、何一個(gè)不小于1957的正整數(shù)后其結(jié)論仍是成立的. 上例的解答過(guò)程說(shuō)明了對(duì)有些數(shù)學(xué)問(wèn)題需要我們連續(xù)運(yùn)用抽屜原則，而且每構(gòu)造一次抽屜都把范圍縮小一些.例6：已知1與90之間的19個(gè)（不同的）正整數(shù)，兩兩的差中是否一定有三個(gè)相等？（匈牙利數(shù)學(xué)競(jìng)賽題，1990年）【證明】設(shè)這19個(gè)數(shù)為 由于， 若右邊的18個(gè)差中無(wú)三個(gè)相等，而只有兩個(gè)相等，且取最小的，則 這與矛盾. 所以兩兩的差中定有三個(gè)相等. 抽屜原則實(shí)際上都是重疊原則，這里再介紹抽屜原則的幾種變形：平均量重疊原則：把一個(gè)量s任意分成n份，則其中至少有一份不大于，也至少有一份不少于.面積的重疊原則：在平面上有n個(gè)面積分別是a1，a2，an的圖形，把

14、這n個(gè)圖形按任何方式一一搬到某一個(gè)面積為a的固定圖形上去，（1）如果a1+a2+an>a，則至少有兩個(gè)圖形有公共點(diǎn)；（2）如果a1+a2+an<a，則固定圖形中至少有一個(gè)點(diǎn)未被蓋住.例7：在一個(gè)面積為20×25的長(zhǎng)方形內(nèi)任意放進(jìn)120個(gè)面積為1×1的正方形，證明：在這個(gè)長(zhǎng)方形內(nèi)一定還可以放下一個(gè)直徑為1的圓，它和這120個(gè)正方形的任何一個(gè)都不相重疊. （第1屆全俄數(shù)學(xué)奧林匹克試題）【證明】要使直徑為1的圓完全放在一個(gè)矩形里，它的圓心應(yīng)與矩形任何一條邊的距離不小于，這可從20×25的長(zhǎng)方形abcd的每一邊剪去一個(gè)寬為的長(zhǎng)條，則余下的長(zhǎng)方形abcd的面積為19×24=456如圖i322（a）.這樣，任意放進(jìn)長(zhǎng)方形abcd內(nèi)的直徑為1的圓心都在長(zhǎng)方形abcd中，此外，圓心應(yīng)與任何一個(gè)正方形的邊界的距離也大于，即在任何一個(gè)小正方形以外加上的框如圖i322（b）所得圖形的面積是 . 用這樣的120個(gè)圖形互不相交地去覆蓋長(zhǎng)方形abcd，它們的總面積等于 但是 這說(shuō)明用這樣的120圖形不能覆蓋一個(gè)面積為456的長(zhǎng)方形，從而可以在長(zhǎng)方形abcd內(nèi)放置一個(gè)直徑為1的圓，它不與所有的小正方形中的任何一個(gè)重疊.例8：設(shè)n與k是正整數(shù)，平面上有n個(gè)