高二數(shù)學(xué)競(jìng)賽班講義第六講組合問(wèn)題

數(shù)學(xué)高二數(shù)學(xué)競(jìng)賽班二試第六講組合問(wèn)題班級(jí)姓名一、知識(shí)要點(diǎn)：組合數(shù)學(xué)是一個(gè)既古老又年輕的離散數(shù)學(xué)分支，競(jìng)賽中的組合問(wèn)題主要包括組合計(jì)數(shù)問(wèn)題、組合極值問(wèn)題、存在性問(wèn)題、操作變換問(wèn)題、組合幾何問(wèn)題以及圖論中的問(wèn)題，求解競(jìng)賽中的組合問(wèn)題并不是需要復(fù)雜的數(shù)學(xué)知識(shí)，然而在趣味性命題的陳述下包含了高超的解題技巧，無(wú)論是從智力訓(xùn)練的角度，還是從競(jìng)賽準(zhǔn)備的角度考慮，理解和鉆研這些問(wèn)題都是十分有意義的．在解決組合問(wèn)題時(shí)，有時(shí)會(huì)用到以下幾個(gè)原理．1、極端原理原理1設(shè)M是自然數(shù)集的一個(gè)非空子集，則M中必有最小數(shù)．原理2設(shè)M是實(shí)數(shù)集的一個(gè)有限的非空子集，則M中必有最小數(shù)．2、抽屜原理把5個(gè)蘋(píng)果放到4個(gè)抽屜中，必然有一個(gè)抽屜中至少有2個(gè)蘋(píng)果，這是抽屜原理的通俗解釋。一般地，我們將它表述為：把（mn＋1）個(gè)物體放入n個(gè)抽屜，其中必有一個(gè)抽屜中至少有（m＋1）個(gè)物體。使用抽屜原理解題，關(guān)鍵是構(gòu)造抽屜。一般說(shuō)來(lái)，數(shù)的奇偶性、剩余類、數(shù)的分組、染色、線段與平面圖形的劃分等，都可作為構(gòu)造抽屜的依據(jù)。第一抽屜原理若將m個(gè)小球放入n個(gè)抽屜中，則必有一個(gè)抽屜內(nèi)至少有個(gè)小球．第二抽屜原理若將m個(gè)小球放入n個(gè)抽屜中，則必有一個(gè)抽屜內(nèi)至多有個(gè)小球．3、算兩次原理所謂算兩次原理（又稱富比尼原理）就是對(duì)同一個(gè)量，如果用兩種不同的方法去計(jì)算，所得的結(jié)果應(yīng)相等．二、經(jīng)典例題例1．（2008年山西省預(yù)賽試題）設(shè)M＝｛1，2，…，2008｝是前2008個(gè)正整數(shù)組成的集合，A＝｛，，…｝是M的一個(gè)30元子集，已知A中的元素兩兩互質(zhì)，證明A中至少一半元素是質(zhì)數(shù)．分析考查集合A中的合數(shù)a，設(shè)p是a的最小質(zhì)因數(shù)，則p≤.又a≤2008，于是p≤45，再由A中的元素兩兩互質(zhì)，可以證明A中16個(gè)元素中必有一個(gè)是質(zhì)數(shù)，進(jìn)而可以導(dǎo)出結(jié)論．證明先證明：A中16個(gè)元素中必有一個(gè)是質(zhì)數(shù)．為此，任取16個(gè)元素，不妨設(shè)為，，…，，若其中沒(méi)有質(zhì)數(shù)，則它們中至多一個(gè)為1，其余15個(gè)皆為合數(shù)．設(shè)，，…，都是合數(shù)，則每個(gè)數(shù)皆可分解成至少兩個(gè)質(zhì)因數(shù)的乘積，若是的最小質(zhì)因數(shù)，則≤（i＝1，2，…，15）．由于A中的數(shù)兩兩互質(zhì)，則，，…，互不相同，而將全體質(zhì)數(shù)自小到大排列，第15個(gè)質(zhì)數(shù)是47，所以，若是，，…，中的最大數(shù)，即有≥47，于是≥≥＞2008，即M，矛盾！因此，，，…，中必有質(zhì)數(shù)，不妨設(shè)為質(zhì)數(shù)，今從集合A中去掉，在剩下的29個(gè)元素中，再次進(jìn)行同樣的討論，可知其中的16個(gè)元素中也必有一個(gè)是質(zhì)數(shù)，設(shè)為.如此下去，可以連續(xù)進(jìn)行15次，每次都可從A中取到一個(gè)新的質(zhì)數(shù)，因此A中至少有15個(gè)質(zhì)數(shù)．說(shuō)明本題利用極端原理，通過(guò)對(duì)合數(shù)的最小質(zhì)因數(shù)的考查，獲取集合A中元素的性質(zhì)，進(jìn)而完成了證明，這種方法也是數(shù)論中研究合數(shù)的一種重要策略．例2．已知A與B是集合｛1，2，3，…，100｝的兩個(gè)子集，滿足：A與B的元素個(gè)數(shù)相同，且A∩B為空集，若nA時(shí)總有2n+2B，則集合A∪B的元素個(gè)數(shù)最多為多少？分析該問(wèn)題是組合構(gòu)造，由條件“A與B的元素個(gè)數(shù)相同且若n∈A時(shí)總有2n+2∈B”知|A|＝|B|，且2n+2≤100，從而可知A中的元素不超過(guò)49個(gè)，為此需要進(jìn)行分類考慮．解首先證明|A∪B|≤66，只需要證明|A|≤33，由分析知需要證明：若A是｛1，2，3，…，49｝的任何一個(gè)34元子集，則必存在nA，使得2n+2A.證明如下：將｛1，2，3，…，49｝分成如下33個(gè)集合：｛1，4｝，｛3，8｝，｛5，12｝，…，｛23，48｝，共12個(gè)；｛2，6｝，｛10，22｝，｛14，30｝，｛18，38｝，共4個(gè)；｛25｝，｛27｝，｛29｝，…，｛49｝，共13個(gè)；｛26｝，｛34｝，｛42｝，｛46｝，共4個(gè)．若A是｛1，2，3，…，49｝的任何一個(gè)34元的子集，則由抽屜原理可知上述33個(gè)集合中至少有一個(gè)2元集合中的兩個(gè)數(shù)均屬于A，即存在n∈A，2n+2∈A.所以|A|≤33.事實(shí)上，如取A＝｛1，3，5，…，23，2，10，14，18，25，27，29，…，49，26，34，42，46｝，B＝｛2n+2|n∈A｝，則A，B滿足題中要求，且|A∪B|＝66.所以集合A∪B的元素個(gè)數(shù)最多為66.說(shuō)明將集合中的元素進(jìn)行適當(dāng)分會(huì)組，并結(jié)合抽屜原理使問(wèn)題得以解決，這是解決類問(wèn)題的常用手段.例3．(2007年浙江省預(yù)賽試題)設(shè)M＝｛1，2，…，65｝，AM為子集，若|A|＝33，且存在x，y∈A，x＜y，x|y，則稱A為“好集”，求最大的a∈M，使含a的任意33元子集為好集．分析首先要準(zhǔn)確理解“好集”的含義，搞清楚“好集”中元素的構(gòu)成規(guī)律，再來(lái)分析a的可能的取值．解令P＝｛21+i|i＝1，2，…，44｝—｛2（21+i）|i＝1，2，…，11｝，|p|＝33.顯然對(duì)任意1≤i＜j≤44，不存在n≥3，使得21+j＝n(21+i)成立，故P是非好集．因此a≤21，下面證明：包含21的任意一個(gè)33元子集A一定為好集．設(shè)A＝｛，，…，，21｝．若1，3，7，42，63中之一為集合A的元素，顯然A為好集現(xiàn)考慮1，3，7，42，63都不屬于集合A．構(gòu)造集合：＝｛2，4，8，16，32，64｝，＝｛5，10，20，40｝，＝｛6，12，24，48｝，＝｛9，18，36｝，＝｛11，22，44｝，＝｛13，26，52｝，＝｛14，28，56｝，＝｛15，30，60｝，＝｛17，34｝，＝｛19，38｝，＝｛23，36｝，＝｛25，50｝，＝｛27，54｝，＝｛29，58｝，＝｛31，62｝，＝｛33，35，37，…，61，65｝，由上可見(jiàn)，，，…，每個(gè)集合中兩個(gè)元素都是倍數(shù)關(guān)系，考慮最不利的情況，即A，也即中16個(gè)元素全部選作A的元素，A中剩下16個(gè)元素必須從，，…，這15個(gè)集合中選取，根據(jù)抽屜原理，至少有一個(gè)集合有兩個(gè)元素被選，即集合A中至少有兩個(gè)元素存在倍數(shù)關(guān)系．綜上所述，包含21的任意一個(gè)33元子集A一定為好集，即a的最大值為21．說(shuō)明對(duì)于這一類型的集合問(wèn)題，一般都需要通過(guò)適當(dāng)?shù)姆绞綐?gòu)造出符合某種要求的集合，抽屜原理是解決集合構(gòu)造問(wèn)題的常用工具．例4．（2008年甘肅省預(yù)賽試題）一個(gè)20行若干列的0、1數(shù)陣滿足：各列互不相同且任意兩列同一行都取1的行數(shù)不超過(guò)2．求當(dāng)列數(shù)最多時(shí)，數(shù)陣中1的個(gè)數(shù)的最小值．分析由題設(shè)，對(duì)于數(shù)陣中1的個(gè)數(shù)超過(guò)3的列，保留其中任意3個(gè)1，而將其余的都變成0，得到的新數(shù)陣仍然滿足要求，于是可知當(dāng)列數(shù)最多時(shí)，數(shù)陣中至多包含1的個(gè)數(shù)不超過(guò)3的所有的列.這樣可得列數(shù)最大值，進(jìn)而求得此時(shí)數(shù)陣中1的個(gè)數(shù)的最小值．解對(duì)于滿足條件的列數(shù)最大的一個(gè)數(shù)陣，如果這個(gè)數(shù)陣中某一列1的個(gè)數(shù)超過(guò)3個(gè)，那么就保留其中任意3個(gè)1，其余的都改變成0，這樣就會(huì)得到一個(gè)列數(shù)相同并有仍然滿足要求的一個(gè)新數(shù)陣，如果這個(gè)新數(shù)陣中還有1的個(gè)數(shù)超過(guò)3的列，則重復(fù)上述過(guò)程，最后可以得到一個(gè)列數(shù)最多，且每列中1的個(gè)數(shù)最多為3的滿足要求的數(shù)列，它的列數(shù)最多為1+++.另一方面，構(gòu)造一個(gè)滿足要求的數(shù)陣如下：它包括沒(méi)有1的列以及所有互不相同的只有一個(gè)1的列，2個(gè)1的列和3個(gè)1的列，由上所說(shuō)，可知這個(gè)數(shù)陣的列數(shù)是最多的，同時(shí)在滿足要求的列數(shù)最多的所有數(shù)陣中所有數(shù)陣中，該數(shù)陣中的1是最少的，此數(shù)陣的列數(shù)為1+++，此數(shù)列中1的個(gè)數(shù)是++＝20+380+3420＝3820說(shuō)明本題中求數(shù)陣的列數(shù)的最大值的方法叫做局部整法，它是解決最值問(wèn)題的一種行之有效的方法，尤其是離散變量最值問(wèn)題常常需要用到這種方法．例5．（2008年浙江省預(yù)賽試題）將3k（k為正整數(shù)）個(gè)石子分成五堆，如果通過(guò)每次從其中3堆中各取走一個(gè)石子，而最后取完，則稱這樣的分法是“和諧的”，試給出和諧分法的充分必要條件，并加以證明．分析從整體上看，就是從3k個(gè)石子中每次取3個(gè)，恰好k次取完，于是和諧的分法就是要求每堆石子的個(gè)數(shù)不超過(guò)k，再用數(shù)學(xué)歸納法證明，最多一堆石子的個(gè)數(shù)不超過(guò)k的分法是和諧的．解分析是和諧的充分必要條件是最多一堆石子的個(gè)數(shù)不超過(guò)k．下面設(shè)五堆石子的個(gè)數(shù)分別為a、b、c、d、e（其中a≥b≥c≥d≥e）．“必要性”的證明：若分法是和諧的，則把a(bǔ)所對(duì)應(yīng)的石子取完至少要取a次，這a次每次都要取走3個(gè)石子，如果a＞k，則3a＞3k，即把a(bǔ)所對(duì)應(yīng)的一堆取完時(shí)，需取走的石子多于五堆石子的總數(shù)，矛盾，因此最多一堆石子的個(gè)數(shù)不能超過(guò)k.“充分性”的證明：（數(shù)學(xué)歸納法）（1）當(dāng)k＝1時(shí)，滿足a≤k的分法只能是1、1、1、0、0．顯然這樣的分法是和諧的．（2）假設(shè)k≤n時(shí)，若a≤k的分法是和諧的．當(dāng)k＝n+1時(shí)，若a≤n+1，且分法a、b、c、d、e是不和諧的，則分法a－1、b－1、c－1、d、e也是不和諧的．由（2）及必要性的證明，可知max｛a－1，b－1，c－1，d，e｝＞n．因?yàn)閍≥b≥c≥d≥e，所以max｛a－1，b－1，c－1，d，e｝＝max｛a－1，d｝＞n．若a－1≥d，則有a－1＞n．這與a≤n+1矛盾．若a－1＜d，則有n＜d≤c≤b≤a≤n+1，從而有a＝b＝c＝d＝n+1，于是有3（n+1）＝a+b+c+d+e＝4(n+1)+e，這是不可能的．因此，當(dāng)a≤n+1時(shí)，分法a、b、c、d、e是和諧的說(shuō)明本題充分性的證明采用的是數(shù)學(xué)歸納法，這是一種歸納構(gòu)造，它是利用構(gòu)造思想解決存在性問(wèn)題的一種重要手段例6．（1988年全國(guó)聯(lián)賽試題）在坐標(biāo)平面上是否存在一個(gè)含有無(wú)窮多條直線，，…，，…的直線族，滿足條件：（1）點(diǎn)（1，1）∈，n＝1，2，3，…；（2）＝－，其中是的斜率，和分別是在x軸和y軸上的截距，是的斜率，n＝1，2，3，…；（3）≥0，n＝1，2，3，…并證明你的結(jié)論分析假設(shè)這樣的直線族存在，先利用直線的方程求出與，即可得到｛｝的遞推關(guān)系，再結(jié)合條件（3）求解解題中給出的是以點(diǎn)（1，1）為公共點(diǎn)的中心直線族，若這樣的直線族存在，則的方程為y－1＝當(dāng)y＝0時(shí)，－1＝，＝1－當(dāng)x＝0時(shí)，－1＝－，＝1－因?yàn)榇嬖?，所以和都存在，從而?，n＝1，2，3，…，利用條件（2）有＝－＝－繼續(xù)有＝－……＝－以上諸式相加得到＝－（++…+）①由≠0及條件(3)得＞0，故所有的（i＝1，2，3，…）同號(hào)，不妨設(shè)＞0，則＝－＜，即數(shù)列｛｝是正項(xiàng)遞減數(shù)列，從而＞，于是++…+＞這樣，由式得＜－＝當(dāng)n＞時(shí)，由式推出＜0．由假設(shè)＞0，得＜0，與己知矛盾同理可證，當(dāng)＜0時(shí)，也導(dǎo)致矛盾所以，同時(shí)滿足條件（1），（2），（3）的直線族不存在說(shuō)明本題是探索性質(zhì)的存在性問(wèn)題，解決問(wèn)題時(shí)，常常需要先作出判斷，明確解題方法，再求解，這對(duì)學(xué)生的能力提出了更高的要求例7．（2007年吉林省預(yù)賽試題）一個(gè)空間中的點(diǎn)組成的集合Ｓ滿足性質(zhì)：Ｓ中任意兩點(diǎn)之間的距離互不相同，假設(shè)Ｓ中的點(diǎn)的坐標(biāo)（x，y，z）都是整數(shù)，并且１≤x，y，z≤n，證明：集合S的元素個(gè)數(shù)小于min｛（n+2）·，｝證明記|S|＝t，則對(duì)任意（），（）∈S，都有++≤3（因?yàn)闈M足1≤x，y，z≤n的整點(diǎn)之間的距離不超過(guò)（1，1，1）與（n，n，n）之間的距離）并且依題意，S中任意兩點(diǎn)之間的距離互不相同，故≤3，得－t≤6，于是t≤+＜(最后一個(gè)不等式價(jià)于1+24＜，展開(kāi)后移項(xiàng)即可得到)另一方面，對(duì)S中的任意兩點(diǎn)（）、（），考慮集合｛a，b，c｝(允許出現(xiàn)重復(fù)元素)，這里a＝||，b＝||，c＝||，依題意，所得的｛a，b，c｝兩兩不同，且0≤a，b，c≤n－1，a、b、c不全為0，于是，我們有≤ ①故＜解得t＜．當(dāng)n≥3時(shí)，有t＜．這只需證明≤，等價(jià)于≤，展開(kāi)后移項(xiàng)即可知此不等式在n≥3時(shí)成立）．于是，當(dāng)n≥3時(shí)，總有t≤ ②而當(dāng)n＝1時(shí)，t＝1；當(dāng)n＝2時(shí)，由①知t≤3，這時(shí)②都成立，命題獲證．說(shuō)明：本題從兩個(gè)不同的角度，分別得到了的上界，從而完成了證明．這種思想的實(shí)質(zhì)是算兩次原理．它是研究跟計(jì)算有關(guān)的組合問(wèn)題的一種重要策略．例8．（2009年山西省預(yù)賽試題）有七種顏色的珍珠，共計(jì)14顆，其中每種顏色的珍珠各兩顆；今把這珍珠分裝于七個(gè)珠盒中，使得每個(gè)珠盒中各有一對(duì)不同顏色的珍珠．（1）證明：不論各盒中的珍珠怎樣搭配，總可以將這七個(gè)珠盒分別放置于一個(gè)正七邊形的七個(gè)頂點(diǎn)之上，使得七邊形的任兩個(gè)相鄰頂點(diǎn)處所放置的盒中的四顆珍珠互不同色．（2）如將以上條件與待證結(jié)論中的“七”一律改為“五”，“14”改為“10”，則情況如何？分析：本題的文字?jǐn)⑹鲭y以找出一般規(guī)律，把文字語(yǔ)言首先轉(zhuǎn)化為圖論語(yǔ)言，再借助圖的性質(zhì)找出問(wèn)題的解決思路．解：（1）用點(diǎn)v1，v2，…，v7分別表示這七種顏色，如果一個(gè)色的珍珠和一個(gè)色的珍珠裝在同一盒中（i≠j），則在點(diǎn)與間連一條邊，這樣就得到一個(gè)圖G（點(diǎn)與之間有可能連出兩條邊），由于同一色的珍珠有兩顆，每顆珍珠都需與一顆其他顏色的珍珠共盒，則圖G的每點(diǎn)恰好發(fā)出兩條邊；從G的任一點(diǎn)A出發(fā)，沿一條邊走到點(diǎn)B，再由B沿另一條邊走到C，…，如此下去，最后必定回到出發(fā)點(diǎn)A（這是由于，途中經(jīng)過(guò)的每個(gè)點(diǎn)P都有兩條邊，若參沿一條邊進(jìn)入點(diǎn)P，則必沿另一條邊可離開(kāi)點(diǎn)P，而由點(diǎn)P不能再加到途中已經(jīng)過(guò)的點(diǎn)，因?yàn)檫@種點(diǎn)所發(fā)出的兩條邊都已走過(guò)，因此只能到達(dá)新點(diǎn)或回到出發(fā)點(diǎn)，而新點(diǎn)終將逐漸耗盡，最后必定回到出發(fā)點(diǎn)A），這樣就得到一個(gè)圈．去掉這個(gè)圈，若剩下還有點(diǎn)，依上述方法，又將得到新的圈，若稱兩點(diǎn)的的圈為“兩邊形”，則圖G的結(jié)構(gòu)只有如下四種情況：1°一個(gè)七邊形2°一個(gè)五邊形和一個(gè)兩邊形3°一個(gè)四邊形和一個(gè)三角形4°一個(gè)三角形和兩個(gè)兩邊形對(duì)于每種情況，我們都對(duì)相應(yīng)的邊作出適當(dāng)編號(hào)，并將這些邊所對(duì)應(yīng)的珠盒放置于七邊形的頂點(diǎn)之上，如圖5所示．因此所證結(jié)論成立．（2）當(dāng)14顆七以珍珠改為10顆五色珍珠后，結(jié)論不成立．例如，對(duì)于五色，我們?nèi)魧?0顆珍珠這樣裝盒：，，，，，則無(wú)論怎樣擺放于正五邊形的頂點(diǎn)上，都不能滿足條件（因?yàn)?、、中，任兩盒都有同色的珠，無(wú)論怎樣擺放于正五邊形的頂點(diǎn)上，必有兩盒相鄰）．第13講抽屜原理例1從1，2，3，…，100這100個(gè)數(shù)中任意挑出51個(gè)數(shù)來(lái)，證明在這51個(gè)數(shù)中，一定：（1）有2個(gè)數(shù)互質(zhì)；（2）有2個(gè)數(shù)的差為50；（3）有8個(gè)數(shù)，它們的最大公約數(shù)大于1。證明：（1）將100個(gè)數(shù)分成50組：{1，2}，{3，4}，…，{99，100}。在選出的51個(gè)數(shù)中，必有2個(gè)數(shù)屬于同一組，這一組中的2個(gè)數(shù)是兩個(gè)相鄰的整數(shù)，它們一定是互質(zhì)的。（2）將100個(gè)數(shù)分成50組：{1，51}，{2，52}，…，{50，100}。在選出的51個(gè)數(shù)中，必有2個(gè)數(shù)屬于同一組，這一組的2個(gè)數(shù)的差為50。（3）將100個(gè)數(shù)分成5組（一個(gè)數(shù)可以在不同的組內(nèi)）：第一組：2的倍數(shù)，即{2，4，…，100}；第二組：3的倍數(shù)，即{3，6，…，99}；第三組：5的倍數(shù)，即{5，10，…，100}；第四組：7的倍數(shù)，即{7，14，…，98}；第五組：1和大于7的質(zhì)數(shù)即{1，11，13，…，97}。第五組中有22個(gè)數(shù)，故選出的51個(gè)數(shù)至少有29個(gè)數(shù)在第一組到第四組中，根據(jù)抽屜原理，總有8個(gè)數(shù)在第一組到第四組的某一組中，這8個(gè)數(shù)的最大公約數(shù)大于1。例2求證：可以找到一個(gè)各位數(shù)字都是4的自然數(shù)，它是1996的倍數(shù)。證明：因1996÷4＝499，故只需證明可以找到一個(gè)各位數(shù)字都是1的自然數(shù)，它是499的倍數(shù)就可以了。得到500個(gè)余數(shù)r1，r2，…，r500。由于余數(shù)只能取0，1，2，…，499這499個(gè)值，所以根據(jù)抽屜原理，必有2個(gè)余數(shù)是相同的，這2個(gè)數(shù)的差就是499的倍數(shù)，這個(gè)差的前若干位是1，后若干位是0：11…100…0，又499和10是互質(zhì)的，故它的前若干位由1組成的自然數(shù)是499的倍數(shù)，將它乘以4，就得到一個(gè)各位數(shù)字都是4的自然數(shù)，它是1996的倍數(shù)。例3在一個(gè)禮堂中有99名學(xué)生，如果他們中的每個(gè)人都與其中的66人相識(shí)，那么可能出現(xiàn)這種情況：他們中的任何4人中都一定有2人不相識(shí)（假定相識(shí)是互相的）。分析：注意到題中的說(shuō)法“可能出現(xiàn)……”，說(shuō)明題的結(jié)論并非是條件的必然結(jié)果，而僅僅是一種可能性，因此只需要設(shè)法構(gòu)造出一種情況使之出現(xiàn)題目中所說(shuō)的結(jié)論即可。解：將禮堂中的99人記為a1，a2，…，a99，將99人分為3組：（a1，a2，…，a33），（a34，a35，…，a66），（a67，a68，…，a99），將3組學(xué)生作為3個(gè)抽屜，分別記為A，B，C，并約定A中的學(xué)生所認(rèn)識(shí)的66人只在B，C中，同時(shí)，B，C中的學(xué)生所認(rèn)識(shí)的66人也只在A，C和A，B中。如果出現(xiàn)這種局面，那么題目中所說(shuō)情況就可能出現(xiàn)。因?yàn)槎Y堂中任意4人可看做4個(gè)蘋(píng)果，放入A，B，C三個(gè)抽屜中，必有2人在同一抽屜，即必有2人來(lái)自同一組，那么他們認(rèn)識(shí)的人只在另2組中，因此他們兩人不相識(shí)。例4如右圖，分別標(biāo)有數(shù)字1，2，…，8的滾珠兩組，放在內(nèi)外兩個(gè)圓環(huán)上，開(kāi)始時(shí)相對(duì)的滾珠所標(biāo)數(shù)字都不相同。當(dāng)兩個(gè)圓環(huán)按不同方向轉(zhuǎn)動(dòng)時(shí)，必有某一時(shí)刻，內(nèi)外兩環(huán)中至少有兩對(duì)數(shù)字相同的滾珠相對(duì)。分析：此題中沒(méi)有直接提供我們用以構(gòu)造抽屜和蘋(píng)果的數(shù)量關(guān)系，需要轉(zhuǎn)換一下看問(wèn)題的角度。解：內(nèi)外兩環(huán)對(duì)轉(zhuǎn)可看成一環(huán)靜止，只有一個(gè)環(huán)轉(zhuǎn)動(dòng)。一個(gè)環(huán)轉(zhuǎn)動(dòng)一周后，每個(gè)滾珠都會(huì)有一次與標(biāo)有相同數(shù)字的滾珠相對(duì)的局面出現(xiàn)，那么這種局面共要出現(xiàn)8次。將這8次局面看做蘋(píng)果，再需構(gòu)造出少于8個(gè)抽屜。注意到一環(huán)每轉(zhuǎn)動(dòng)45°角就有一次滾珠相對(duì)的局面出現(xiàn)，轉(zhuǎn)動(dòng)一周共有8次滾珠相對(duì)的局面，而最初的8對(duì)滾珠所標(biāo)數(shù)字都不相同，所以數(shù)字相同的滾珠相對(duì)的情況只出現(xiàn)在以后的7次轉(zhuǎn)動(dòng)中，將7次轉(zhuǎn)動(dòng)看做7個(gè)抽屜，8次相同數(shù)字滾珠相對(duì)的局面看做8個(gè)蘋(píng)果，則至少有2次數(shù)字相對(duì)的局面出現(xiàn)在同一次轉(zhuǎn)動(dòng)中，即必有某一時(shí)刻，內(nèi)外兩環(huán)中至少有兩對(duì)數(shù)字相同的滾珠相對(duì)。例5有一個(gè)生產(chǎn)天平上用的鐵盤(pán)的車間，由于工藝上的原因，只能控制盤(pán)的重量在指定的20克到20.1克之間?，F(xiàn)在需要重量相差不超過(guò)0.005克的兩只鐵盤(pán)來(lái)裝配一架天平，問(wèn)：最少要生產(chǎn)多少個(gè)盤(pán)子，才能保證一定能從中挑出符合要求的兩只盤(pán)子？解：把20～20.1克之間的盤(pán)子依重量分成20組：第1組：從20.000克到20.005克；第2組：從20.005克到20.010克；……第20組：從20.095克到20.100克。這樣，只要有21個(gè)盤(pán)子，就一定可以從中找到兩個(gè)盤(pán)子屬于同一組，這2個(gè)盤(pán)子就符合要求。例6在圓周上放著100個(gè)籌碼，其中有41個(gè)紅的和59個(gè)藍(lán)的。那么總可以找到兩個(gè)紅籌碼，在它們之間剛好放有19個(gè)籌碼，為什么？分析：此題需要研究“紅籌碼”的放置情況，因而涉及到“蘋(píng)果”的具體放置方法，由此我們可以在構(gòu)造抽屜時(shí)，使每個(gè)抽屜中的相鄰“蘋(píng)果”之間有19個(gè)籌碼。解：依順時(shí)針?lè)较驅(qū)⒒I碼依次編上號(hào)碼：1，2，…，100。然后依照以下規(guī)律將100個(gè)籌碼分為20組：（1，21，41，61，81）；（2，22，42，62，82）；……（20，40，60，80，100）。將41個(gè)紅籌碼看做蘋(píng)果，放入以上20個(gè)抽屜中，因?yàn)?1=2×20＋1，所以至少有一個(gè)抽屜中有2+1=3（個(gè)）蘋(píng)果，也就是說(shuō)必有一組5個(gè)籌碼中有3個(gè)紅色籌碼，而每組的5個(gè)籌碼在圓周上可看做兩兩等距，且每2個(gè)相鄰籌碼之間都有19個(gè)籌碼，那么3個(gè)紅色籌碼中必有2個(gè)相鄰（這將在下一個(gè)內(nèi)容——第二抽屜原理中說(shuō)明），即有2個(gè)紅色籌碼之間有19個(gè)籌碼。下面我們來(lái)考慮另外一種情況：若把5個(gè)蘋(píng)果放到6個(gè)抽屜中，則必然有一個(gè)抽屜空著。這種情況一般可以表述為：第二抽屜原理：把（mn-1）個(gè)物體放入n個(gè)抽屜，其中必有一個(gè)抽屜中至多有（m-1）個(gè)物體。例7在例6中留有一個(gè)疑問(wèn)，現(xiàn)改述如下：在圓周上放有5個(gè)籌碼，其中有3個(gè)是同色的，那么這3個(gè)同色的籌碼必有2個(gè)相鄰。分析：將這個(gè)問(wèn)題加以轉(zhuǎn)化：如右圖，將同色的3個(gè)籌碼A，B，C置于圓周上，看是否能用另外2個(gè)籌碼將其隔開(kāi)。解：如圖，將同色的3個(gè)籌碼放置在圓周上，將每2個(gè)籌碼之間的間隔看做抽屜，將其余2個(gè)籌碼看做蘋(píng)果，將2個(gè)蘋(píng)果放入3個(gè)抽屜中，則必有1個(gè)抽屜中沒(méi)有蘋(píng)果，即有2個(gè)同色籌碼之間沒(méi)有其它籌碼，那么這2個(gè)籌碼必相鄰。例8甲、乙二人為一個(gè)正方形的12條棱涂紅和綠2種顏色。首先，甲任選3條棱并把它們涂上紅色；然后，乙任選另外3條棱并涂上綠色；接著甲將剩下的6條棱都涂上紅色。問(wèn)：甲是否一定能將某一面的4條棱全部涂上紅色？解：不能。如右圖將12條棱分成四組：第一組：{A1B1，B2B3，A3A4}，第二組：{A2B2，B3B4，A4A1}，第三組：{A3B3，B4B1，A1A2}，第四組：{A4B4，B1B2，A2A3}。無(wú)論甲第一次將哪3條棱涂紅，由抽屜原理知四組中必有一組的3條棱全未涂紅，而乙只要將這組中的3條棱涂綠，甲就無(wú)法將某一面的4條棱全部涂紅了。下面我們討論抽屜原理的一個(gè)變形——平均值原理。我們知道n個(gè)數(shù)a1，a2，…，an的和與n的商是a1，a2，…，an這n個(gè)數(shù)的平均值。平均值原理：如果n個(gè)數(shù)的平均值為a，那么其中至少有一個(gè)數(shù)不大于a，也至少有一個(gè)不小于a。例9圓周上有2000個(gè)點(diǎn)，在其上任意地標(biāo)上0，1，2，…，1999（每一點(diǎn)只標(biāo)一個(gè)數(shù)，不同的點(diǎn)標(biāo)上不同的數(shù)）。求證：必然存在一點(diǎn)，與它緊相鄰的兩個(gè)點(diǎn)和這點(diǎn)上所標(biāo)的三個(gè)數(shù)之和不小于2999。解：設(shè)圓周上各點(diǎn)的值依次是a1，a2，…，a2000，則其和a1＋a2+…＋a2000=0+1+2+…+1999=1999000。下面考慮一切相鄰三數(shù)組之和：（a1＋a2＋a3）+（a2＋a3＋a4）＋…＋（a1998+a1999＋a2000）＋（a1999＋a2000＋a1）＋（a2000＋a1＋a2）=3（a1＋a2＋…＋a2000）＝3×1999000。這2000組和中必至少有一組和大于或等于但因每一個(gè)和都是整數(shù)，故有一組相鄰三數(shù)之和不小于2999，亦即存在一個(gè)點(diǎn)，與它緊相鄰的兩點(diǎn)和這點(diǎn)上所標(biāo)的三數(shù)之和不小于2999。例10一家旅館有90個(gè)房間，住有100名旅客，如果每次都恰有90名旅客同時(shí)回來(lái)，那么至少要準(zhǔn)備多少把鑰匙分給這100名旅客，才能使得每次客人回來(lái)時(shí)，每個(gè)客人都能用自己分到的鑰匙打開(kāi)一個(gè)房門(mén)住進(jìn)去，并且避免發(fā)生兩人同時(shí)住進(jìn)一個(gè)房間？解：如果鑰匙數(shù)小于990，那么90個(gè)房間中至少有一個(gè)房間的鑰匙數(shù)少房間就打不開(kāi)，因此90個(gè)人就無(wú)法按題述的條件住下來(lái)。另一方面，990把鑰匙已經(jīng)足夠了，這只要將90把不同的鑰匙分給90個(gè)人，而其余的10名旅客，每人各90把鑰匙（每個(gè)房間一把），那么任何90名旅客返回時(shí)，都能按要求住進(jìn)房間。最后，我們要指出，解決某些較復(fù)雜的問(wèn)題時(shí)，往往要多次反復(fù)地運(yùn)用抽屜原理，請(qǐng)看下面兩道例題。例11設(shè)有4×28的方格棋盤(pán)，將每一格涂上紅、藍(lán)、黃三種顏色中的任意一種。試證明：無(wú)論怎樣涂法，至少存在一個(gè)四角同色的長(zhǎng)方形。證明：我們先考察第一行中28個(gè)小方格涂色情況，用三種顏色涂28個(gè)小方格，由抽屜原理知，至少有10個(gè)小方格是同色的，不妨設(shè)其為紅色，還可設(shè)這10個(gè)小方格就在第一行的前10列。下面考察第二、三、四行中前面10個(gè)小方格可能出現(xiàn)的涂色情況。這有兩種可能：（1）這三行中，至少有一行，其前面10個(gè)小方格中，至少有2個(gè)小方格是涂有紅色的，那么這2個(gè)小方格和第一行中與其對(duì)應(yīng)的2個(gè)小方格，便是一個(gè)長(zhǎng)方形的四個(gè)角，這個(gè)長(zhǎng)方形就是一個(gè)四角同是紅色的長(zhǎng)方形。（2）這三行中每一行前面的10格中，都至多有一個(gè)紅色的小方格，不妨設(shè)它們分別出現(xiàn)在前三列中，那么其余的3×7個(gè)小方格便只能涂上黃、藍(lán)兩種顏色了。我們先考慮這個(gè)3×7的長(zhǎng)方形的第一行。根據(jù)抽屜原理，至少有4個(gè)小方格是涂上同一顏色的，不妨設(shè)其為藍(lán)色，且在第1至4列。再考慮第二行的前四列，這時(shí)也有兩種可能：（1）這4格中，至少有2格被涂上藍(lán)色，那么這2個(gè)涂上藍(lán)色的小方格和第一行中與其對(duì)應(yīng)的2個(gè)小方格便是一個(gè)長(zhǎng)方形的四個(gè)角，這個(gè)長(zhǎng)方形四角同是藍(lán)色。（2）這4格中，至多有1格被涂上藍(lán)色，那么，至少有3格被涂上黃色。不妨設(shè)這3個(gè)小方格就在第二行的前面3格。下面繼續(xù)考慮第三行前面3格的情況。用藍(lán)、黃兩色涂3個(gè)小方格，由抽屜原理知，至少有2個(gè)方格是同色的，無(wú)論是同為藍(lán)色或是同為黃色，都可以得到一個(gè)四角同色的長(zhǎng)方形?？傊?，對(duì)于各種可能的情況，都能找到一個(gè)四角同色的長(zhǎng)方形。例12試卷上共有4道選擇題，每題有3個(gè)可供選擇的答案。一群學(xué)生參加考試，結(jié)果是對(duì)于其中任何3人，都有一道題目的答案互不相同。問(wèn)：參加考試的學(xué)生最多有多少人？解：設(shè)每題的三個(gè)選擇分別為a，b，c。（1）若參加考試的學(xué)生有10人，則由第二抽屜原理知，第一題答案分別為a，b，c的三組學(xué)生中，必有一組不超過(guò)3人。去掉這組學(xué)生，在余下的學(xué)生中，定有7人對(duì)第一題的答案只有兩種。對(duì)于這7人關(guān)于第二題應(yīng)用第二抽屜原理知，其中必可選出5人，他們關(guān)于第二題的答案只有兩種可能。對(duì)于這5人關(guān)于第三題應(yīng)用第二抽屜原理知，可以選出4人，他們關(guān)于第三題的答案只有兩種可能。最后，對(duì)于這4人關(guān)于第四題應(yīng)用第二抽屜原理知，必可選出3人，他們關(guān)于第四題的答案也只有兩種。于是，對(duì)于這3人來(lái)說(shuō)，沒(méi)有一道題目的答案是互不相同的，這不符合題目的要求。可見(jiàn)，所求的最多人數(shù)不超過(guò)9人。另一方面，若9個(gè)人的答案如下表所示，則每3人都至少有一個(gè)問(wèn)題的答案互不相同。所以，所求的最多人數(shù)為9人。練習(xí)131.六（1）班有49名學(xué)生。數(shù)學(xué)王老師了解到在期中考試中該班英文成績(jī)除3人外均在86分以上后就說(shuō)：“我可以斷定，本班同學(xué)至少有4人成績(jī)相同?！闭?qǐng)問(wèn)王老師說(shuō)得對(duì)嗎？為什么？2.現(xiàn)有64只乒乓球，18個(gè)乒乓球盒，每個(gè)盒子里最多可以放6只乒乓球，至少有幾個(gè)乒乓球盒子里的乒乓球數(shù)目相同？3.某校初二年級(jí)學(xué)生身高的厘米數(shù)都為整數(shù)，且都不大于160厘米，不小于150厘米。問(wèn)：在至少多少個(gè)初二學(xué)生中一定能有4個(gè)人身高相同？4.從1，2，…，100這100個(gè)數(shù)中任意選出51個(gè)數(shù)，證明在這51個(gè)數(shù)中，一定：（1）有兩個(gè)數(shù)的和為101；（2）有一個(gè)數(shù)是另一個(gè)數(shù)的倍數(shù)；（3）有一個(gè)數(shù)或若干個(gè)數(shù)的和是51的倍數(shù)。5.在3×7的方格表中，有11個(gè)白格，證明（1）若僅含一個(gè)白格的列只有3列，則在其余的4列中每列都恰有兩個(gè)白格；（2）只有一個(gè)白格的列只有3列。6.某個(gè)委員會(huì)開(kāi)了40次會(huì)議，每次會(huì)議有10人出席。已知任何兩個(gè)委員不會(huì)同時(shí)開(kāi)兩次或更多的會(huì)議。問(wèn)：這個(gè)委員會(huì)的人數(shù)能夠多于60人嗎？為什么？7.一個(gè)車間有一條生產(chǎn)流水線，由5臺(tái)機(jī)器組成，只有每臺(tái)機(jī)器都開(kāi)動(dòng)時(shí)，這條流水線才能工作。總共有8個(gè)工人在這條流水線上工作。在每一個(gè)工作日內(nèi)，這些工人中只有5名到場(chǎng)。為了保證生產(chǎn)，要對(duì)這8名工人進(jìn)行培訓(xùn)，每人學(xué)一種機(jī)器的操作方法稱為一輪。問(wèn)：最少要進(jìn)行多少輪培訓(xùn)，才能使任意5個(gè)工人上班而流水線總能工作？8.有9名數(shù)學(xué)家，每人至多能講3種語(yǔ)言，每3人中至少有2人能通話。求證：在這9名中至少有3名用同一種語(yǔ)言通話。練習(xí)131.對(duì)。解：因?yàn)?9-3=3×（100-86+1）+1，即46=3×15+1，也就是說(shuō)，把從100分至86分的15個(gè)分?jǐn)?shù)當(dāng)做抽屜，49-3=46（人）的成績(jī)當(dāng)做物體，根據(jù)第二抽屜原理，至少有4人的分?jǐn)?shù)在同一抽屜中，即成績(jī)相同。2.4個(gè)。解：18個(gè)乒乓球盒，每個(gè)盒子里至多可以放6只乒乓球。為使相同乒乓球個(gè)數(shù)的盒子盡可能少，可以這樣放：先把盒子分成6份，每份有18÷6=3（只），分別在每一份的3個(gè)盒子中放入1只、2只、3只、4只、5只、6只乒乓球，即3個(gè)盒子中放了1只乒乓球，3個(gè)盒中放了2只乒乓球……3個(gè)盒子中放了6只乒乓球。這樣，18個(gè)盒子中共放了乒乓球（1+2+3+4+5+6）×3=63（只）。把以上6種不同的放法當(dāng)做抽屜，這樣剩下64-63=1（只）乒乓球不管放入哪一個(gè)抽屜里的任何一個(gè)盒子里（除已放滿6只乒乓球的抽屜外），都將使該盒子中的乒乓球數(shù)增加1只，這時(shí)與比該抽屜每盒乒乓數(shù)多1的抽屜中的3個(gè)盒子里的乒乓球數(shù)相等。例如剩下的1只乒乓球放進(jìn)原來(lái)有2只乒乓球的一個(gè)盒子里，該盒乒乓球就成了3只，再加上原來(lái)裝有3只乒乓球的3個(gè)盒子，這樣就有4個(gè)盒子里裝有3個(gè)乒乓球。所以至少有4個(gè)乒乓球盒里的乒乓球數(shù)目相同。3.34個(gè)。解：把初二學(xué)生的身高厘米數(shù)作為抽屜，共有抽屜160-150+1=11（個(gè)）。根據(jù)抽屜原理，要保證有4個(gè)人身高相同，至少要有初二學(xué)生3×11+1=34（個(gè)）。4.證：（1）將100個(gè)數(shù)分成50組：｛1，100｝，｛2，99｝，…，｛50，51｝。在選出的51個(gè)數(shù)中，必有兩數(shù)屬于同一組，這一組的兩數(shù)之和為101。（2）將100個(gè)數(shù)分成10組：｛1,2,4,8,16,32,64｝,｛3,6,12,24,48,96｝,｛5,10,20,40,80｝,｛7,14,28,56｝,｛9,18,36,72｝,｛11,22,44,88｝,｛13,26,52｝,｛15,30,60｝,…,｛49,98｝,｛其余數(shù)｝。其中第10組中有41個(gè)數(shù)。在選出的51個(gè)數(shù)中，第10組的41個(gè)數(shù)全部選中，還有10個(gè)數(shù)從前9組中選，必有兩數(shù)屬于同一組，這一組中的任意兩個(gè)數(shù)，一個(gè)是另一個(gè)的倍數(shù)。（3）將選出的51個(gè)數(shù)排成一列：a1，a2，a3，…，a51。考慮下面的51個(gè)和：a1，a1+a2，a1+a2+a3，…，a1+a2+a3+…+a51。若這51個(gè)和中有一個(gè)是51的倍數(shù)，則結(jié)論顯然成立；若這51個(gè)和中沒(méi)有一個(gè)是51的倍數(shù)，則將它們除以51，余數(shù)只能是1，2，…，50中的一個(gè)，故必然有兩個(gè)的余數(shù)是相同的，這兩個(gè)和的差是51的倍數(shù)，而這個(gè)差顯然是這51個(gè)數(shù)（a1，a2，a3，…，a51）中的一個(gè)數(shù)或若干個(gè)數(shù)的和。5.證：（1）在其余4列中如有一列含有3個(gè)白格，則剩下的5個(gè)白格要放入3列中，將3列表格看做3個(gè)抽屜，5個(gè)白格看做5個(gè)蘋(píng)果，根據(jù)第二抽屜原理，5（=2×3-1）個(gè)蘋(píng)果放入3個(gè)抽屜，則必有1個(gè)抽屜至多只有（2-1）個(gè)蘋(píng)果，即必有1列只含1個(gè)