2019-2020年高中數(shù)學競賽輔導資料《抽屜原理》.doc

2019-2020年高中數(shù)學競賽輔導資料抽屜原理“抽屜原理”最先是由19世紀的德國數(shù)學家迪里赫萊（Dirichlet）運用于解決數(shù)學問題的，所以又稱“迪里赫萊原理”，也有稱“鴿巢原理”的。這個原理可以簡單地敘述為“把10個蘋果，任意分放在9個抽屜里，則至少有一個抽屜里含有兩個或兩個以上的蘋果”。這個道理是非常明顯的，但應用它卻可以解決許多有趣的問題，并且常常得到一些令人驚異的結果。抽屜原理是國際國內各級各類數(shù)學競賽中的重要內容，本講就來學習它的有關知識及其應用。 （一） 抽屜原理的基本形式 定理1、如果把n+1個元素分成n個集合，那么不管怎么分，都存在一個集合，其中至少有兩個元素。 證明：（用反證法）若不存在至少有兩個元素的集合，則每個集合至多1個元素，從而n個集合至多有n個元素，此與共有n+1個元素矛盾，故命題成立。 在定理1的敘述中，可以把“元素”改為“物件”，把“集合”改成“抽屜”，抽屜原理正是由此得名。 同樣，可以把“元素”改成“鴿子”，把“分成n個集合”改成“飛進n個鴿籠中”?！傍澔\原理”由此得名。 例題講解1 已知在邊長為1的等邊三角形內（包括邊界）有任意五個點（圖1）。證明：至少有兩個點之間的距離不大于2從1-100的自然數(shù)中，任意取出51個數(shù)，證明其中一定有兩個數(shù)，它們中的一個是另一個的整數(shù)倍。 3從前25個自然數(shù)中任意取出7個數(shù)，證明：取出的數(shù)中一定有兩個數(shù)，這兩個數(shù)中大數(shù)不超過小數(shù)的1.5倍。4已給一個由10個互不相等的兩位十進制正整數(shù)組成的集合。求證：這個集合必有兩個無公共元素的子集合，各子集合中各數(shù)之和相等。5在坐標平面上任取五個整點（該點的橫縱坐標都取整數(shù)），證明：其中一定存在兩個整點，它們的連線中點仍是整點。6在任意給出的100個整數(shù)中，都可以找出若干個數(shù)來（可以是一個數(shù)），它們的和可被100整除。7 17名科學家中每兩名科學家都和其他科學家通信，在他們通信時，只討論三個題目，而且任意兩名科學家通信時只討論一個題目，證明：其中至少有三名科學家，他們相互通信時討論的是同一個題目。 課后練習1幼兒園買來了不少白兔、熊貓、長頸鹿塑料玩具，每個小朋友任意選擇兩件，那么不管怎樣挑選，在任意七個小朋友中總有兩個彼此選的玩具都相同，試說明道理.2正方體各面上涂上紅色或藍色的油漆（每面只涂一種色），證明正方體一定有三個面顏色相同.3把1到10的自然數(shù)擺成一個圓圈，證明一定存在在個相鄰的數(shù)，它們的和數(shù)大于17.4有紅襪2雙，白襪3雙，黑襪4雙，黃襪5雙，藍襪6雙（每雙襪子包裝在一起）若取出9雙，證明其中必有黑襪或黃襪2雙.5在邊長為1的正方形內，任意給定13個點，試證：其中必有4個點，以此4點為頂點的四邊開面積不超過（假定四點在一直線上構成面積為零的四邊形）.6在一條筆直的馬路旁種樹，從起點起，每隔一米種一棵樹，如果把三塊“愛護樹木”的小牌分別掛在三棵樹上，那么不管怎樣掛，至少有兩棵掛牌的樹之間的距離是偶數(shù)（以米為單位），這是為什么？課后練習答案1.解 從三種玩具中挑選兩件，搭配方式只能是下面六種：（兔、兔），（兔、熊貓），（兔、長頸鹿），（熊貓、熊貓），（熊貓、長頸鹿），（長頸鹿、長頸鹿）把每種搭配方式看作一個抽屜，把7個小朋友看作物體，那么根據(jù)原則1，至少有兩個物體要放進同一個抽屜里，也就是說，至少兩人挑選玩具采用同一搭配方式，選的玩具相同.原則2 如果把mn+k(k1)個物體放進n個抽屜，則至少有一個抽屜至多放進m+1個物體.證明同原則相仿.若每個抽屜至多放進m個物體,那么n個抽屜至多放進mn個物體,與題設不符，故不可能.原則1可看作原則2的物例（m=1）2.證明把兩種顏色當作兩個抽屜，把正方體六個面當作物體，那么6=22+2，根據(jù)原則二，至少有三個面涂上相同的顏色.3.證明 如圖12-1，設a1，a2，a3，a9，a10分別代表不超過10的十個自然數(shù)，它們圍成一個圈，三個相鄰的數(shù)的組成是（a1，a2，a3），（a2，a3，a4），（a3，a4，a5），,（a9，a10，a1）,（a10，a1，a2）共十組.現(xiàn)把它們看作十個抽屜，每個抽屜的物體數(shù)是a1+a2+a3，a2+a3+a4，a3+a4+a5，a9+a10+a1，a10+a1+a2,由于（a1+a2+a3）+（a2+a3+a4）+（a9+a10+a1）+（a10+a1+a2）=3(a1+a2+a9+a10)=3(1+2+9+10)根據(jù)原則2,至少有一個括號內的三數(shù)和不少于17,即至少有三個相鄰的數(shù)的和不小于17.原則1、原則2可歸結到期更一般形式：原則3把m1+m2+mn+k(k1)個物體放入n個抽屜里，那么或在第一個抽屜里至少放入m1+1個物體，或在第二個抽屜里至少放入m2+1個物體，或在第n個抽屜里至少放入mn+1個物體.證明假定第一個抽屜放入物體的數(shù)不超過m1個，第二個抽屜放入物體的數(shù)不超過m2個，第n個抽屜放入物體的個數(shù)不超過mn，那么放入所有抽屜的物體總數(shù)不超過m1+m2+mn個，與題設矛盾.4.證明 除可能取出紅襪、白襪3雙外.還至少從其它三種顏色的襪子里取出4雙，根據(jù)原理3，必在黑襪或黃襪、藍襪里取2雙.上面數(shù)例論證的似乎都是“存在”、“總有”、“至少有”的問題，不錯，這正是抽屜原則的主要作用.需要說明的是，運用抽屜原則只是肯定了“存在”、“總有”、“至少有”，卻不能確切地指出哪個抽屜里存在多少.制造抽屜是運用原則的一大關鍵首先要指出的是，對于同一問題，?？梢罁?jù)情況，從不同角度設計抽屜，從而導致不同的制造抽屜的方式.5.證明如圖12-2把正方形分成四個相同的小正方形.因13=34+1，根據(jù)原則2，總有4點落在同一個小正方形內（或邊界上），以此4點為頂點的四邊形的面積不超過小正方形的面積，也就不超過整個正方形面積的.事實上，由于解決問題的核心在于將正方形分割成四個面積相等的部分，所以還可以把正方形按圖12-3（此處無圖）所示的形式分割.合理地制造抽屜必須建立在充分考慮問題自身特點的基礎上.6.解如圖12-4（設掛牌的三棵樹依次為A、B、C.AB=a，BC=b，若a、b中有一為偶數(shù)，命題得證.否則a、b均為奇數(shù)，則AC=a+b為偶數(shù)，命題得證.下面我們換一個角度考慮：給每棵樹上編上號，于是兩棵樹之間的距離就是號碼差，由于樹的號碼只能為奇數(shù)和偶數(shù)兩類，那么掛牌的三棵樹號碼至少有兩個同為奇數(shù)或偶數(shù)，它們的差必為偶數(shù)，問題得證.后一證明十分巧妙，通過編號碼，將兩樹間距離轉化為號碼差.這種轉化的思想方法是一種非常重要的數(shù)學方法例題答案：1分析：5個點的分布是任意的。如果要證明“在邊長為1的等邊三角形內（包括邊界）有5個點，那么這5個點中一定有距離不大于的兩點”，則順次連接三角形三邊中點，即三角形的三條中位線，可以分原等邊三角形為4個全等的邊長為的小等邊三角形，則5個點中必有2點位于同一個小等邊三角形中（包括邊界），其距離便不大于。 以上結論要由定理“三角形內（包括邊界）任意兩點間的距離不大于其最大邊長”來保證，下面我們就來證明這個定理。如圖2，設BC是ABC的最大邊，P，M是ABC內（包括邊界）任意兩點，連接PM，過P分別作AB、BC邊的平行線，過M作AC邊的平行線，設各平行線交點為P、Q、N，那么PQN=C，QNP=A 因為BCAB，所以AC，則QNPPQN，而QMPQNPPQN（三角形的外角大于不相鄰的內角），所以 PQPM。顯然BCPQ，故BCPM。 由此我們可以推知，邊長為的等邊三角形內（包括邊界）兩點間的距離不大于。 說明： （1）這里是用等分三角形的方法來構造“抽屜”。類似地，還可以利用等分線段、等分正方形的方法來構造“抽屜”。例如“任取n+1個正數(shù)ai，滿足0ai1（i=1,2,n+1），試證明：這n+1個數(shù)中必存在兩個數(shù)，其差的絕對值小于”。又如：“在邊長為1的正方形內任意放置五個點，求證：其中必有兩點，這兩點之間的距離不大于。 （2）例1中，如果把條件（包括邊界）去掉，則結論可以修改為：至少有兩個點之間的距離小于"，請讀者試證之，并比較證明的差別。 （3）用同樣的方法可證明以下結論： i）在邊長為1的等邊三角形中有n2+1個點，這n2+1個點中一定有距離不大于的兩點。 ii）在邊長為1的等邊三角形內有n2+1個點，這n2+1個點中一定有距離小于的兩點。 （4）將（3）中兩個命題中的等邊三角形換成正方形，相應的結論中的換成，命題仍然成立。 （5）讀者還可以考慮相反的問題：一般地，“至少需要多少個點，才能夠使得邊長為1的正三角形內（包括邊界）有兩點其距離不超過”。 2分析：本題似乎茫無頭緒，從何入手？其關鍵何在？其實就在“兩個數(shù)”，其中一個是另一個的整數(shù)倍。我們要構造“抽屜”，使得每個抽屜里任取兩個數(shù)，都有一個是另一個的整數(shù)倍，這只有把公比是正整數(shù)的整個等比數(shù)列都放進去同一個抽屜才行，這里用得到一個自然數(shù)分類的基本知識：任何一個正整數(shù)都可以表示成一個奇數(shù)與2的方冪的積，即若mN+,KN+，nN,則m=(2k-1)2n，并且這種表示方式是唯一的，如1=12，2=121，3=32， 證明：因為任何一個正整數(shù)都能表示成一個奇數(shù)乘2的方冪，并且這種表示方法是唯一的，所以我們可把1-100的正整數(shù)分成如下50個抽屜（因為1-100中共有50個奇數(shù)）： （1）1，12，122，123，124，125，126；（2）3，32，322，323，324，325；（3）5，52，522，523，524；（4）7，72，722，723；（5）9，92，922，923；（6）11，112，1122，1123；（25）49，492；（26）51；（50）99。 這樣，1-100的正整數(shù)就無重復，無遺漏地放進這50個抽屜內了。從這100個數(shù)中任取51個數(shù)，也即從這50個抽屜內任取51個數(shù)，根據(jù)抽屜原則，其中必定至少有兩個數(shù)屬于同一個抽屜，即屬于（1）-（25）號中的某一個抽屜，顯然，在這25個抽屜中的任何同一個抽屜內的兩個數(shù)中，一個是另一個的整數(shù)倍。 說明： （1）從上面的證明中可以看出，本題能夠推廣到一般情形：從1-2n的自然數(shù)中，任意取出n+1個數(shù)，則其中必有兩個數(shù)，它們中的一個是另一個的整數(shù)倍。想一想，為什么？因為1-2n中共含1，3，2n-1這n個奇數(shù)，因此可以制造n個抽屜，而n+1n，由抽屜原則，結論就是必然的了。給n以具體值，就可以構造出不同的題目。例2中的n取值是50，還可以編制相反的題目，如：“從前30個自然數(shù)中最少要（不看這些數(shù)而以任意方式地）取出幾個數(shù)，才能保證取出的數(shù)中能找到兩個數(shù)，其中較大的數(shù)是較小的數(shù)的倍數(shù)？” （2）如下兩個問題的結論都是否定的（n均為正整數(shù)）想一想，為什么？ 從2，3，4，2n+1中任取n+1個數(shù)，是否必有兩個數(shù)，它們中的一個是另一個的整數(shù)倍？ 從1，2，3，2n+1中任取n+1個數(shù)，是否必有兩個數(shù)，它們中的一個是另一個的整數(shù)倍？你能舉出反例，證明上述兩個問題的結論都是否定的嗎？ （3）如果將（2）中兩個問題中任取的n+1個數(shù)增加1個，都改成任取n+2個數(shù)，則它們的結論是肯定的還是否定的？你能判斷證明嗎？ 3證明：把前25個自然數(shù)分成下面6組： 1； 2，3； 4，5，6； 7，8，9，10； 11，12，13，14，15，16； 17，18，19，20，21，22，23， 因為從前25個自然數(shù)中任意取出7個數(shù)，所以至少有兩個數(shù)取自上面第組到第組中的某同一組，這兩個數(shù)中大數(shù)就不超過小數(shù)的1.5倍。 說明： （1）本題可以改變敘述如下：在前25個自然數(shù)中任意取出7個數(shù)，求證其中存在兩個數(shù)，它們相互的比值在內。 顯然，必須找出一種能把前25個自然數(shù)分成6（7-1=6）個集合的方法，不過分類時有一個限制條件：同一集合中任兩個數(shù)的比值在內，故同一集合中元素的數(shù)值差不得過大。這樣，我們可以用如上一種特殊的分類法：遞推分類法： 從1開始，顯然1只能單獨作為1個集合1；否則不滿足限制條件。 能與2同屬于一個集合的數(shù)只有3，于是2，3為一集合。 如此依次遞推下去，使若干個連續(xù)的自然數(shù)屬于同一集合，其中最大的數(shù)不超過最小的數(shù)的倍，就可以得到滿足條件的六個集合。 （2）如果我們按照（1）中的遞推方法依次造“抽屜”，則第7個抽屜為 26，27，28，29，30，31，32，33，34，35，36，37，38，39；第8個抽屜為：40，41，42，60；第9個抽屜為：61，62，63，90，91； 那么我們可以將例3改造為如下一系列題目： （1）從前16個自然數(shù)中任取6個自然數(shù)；（2）從前39個自然數(shù)中任取8個自然數(shù)；（3）從前60個自然數(shù)中任取9個自然數(shù)；（4）從前91個自然數(shù)中任取10個自然數(shù)；都可以得到同一個結論：其中存在2個數(shù)，它們相互的比值在內。 上述第（4）個命題，就是前蘇聯(lián)基輔第49屆數(shù)學競賽試題。如果我們改變區(qū)間（pq）端點的值，則又可以構造出一系列的新題目來。 4.分析與解答：一個有著10個元素的集合，它共有多少個可能的子集呢？由于在組成一個子集的時候，每一個元素都有被取過來或者不被取過來兩種可能，因此，10個元素的集合就有210=1024個不同的構造子集的方法，也就是，它一共有1024個不同的子集，包括空集和全集在內?？占c全集顯然不是考慮的對象，所以剩下1024-2=1022個非空真子集。 再來看各個真子集中一切數(shù)字之和。用N來記這個和數(shù)，很明顯： 10N91+92+93+94+95+96+97+98+99=855這表明N至多只有855-9=846種不同的情況。由于非空真子集的個數(shù)是1022，1022846，所以一定存在兩個子集A與B，使得A中各數(shù)之和=B中各數(shù)之和。 若AB=，則命題得證，若AB=C，即A與B有公共元素，這時只要剔除A與B中的一切公有元素，得出兩個不相交的子集A1與B1，很顯然 A1中各元素之和=B1中各元素之和，因此A1與B1就是符合題目要求的子集。 說明：本例能否推廣為如下命題： 已給一個由m個互不相等的n位十進制正整數(shù)組成的集合。求證：這個集合必有兩個無公共元素的子集合，各子集合中各數(shù)之和相等。 請讀者自己來研究這個問題。 5分析與解答：由中點坐標公式知，坐標平面兩點（x1,y1）、（x2,y2）的中點坐標是。欲使都是整數(shù)，必須而且只須x1與x2，y1與y2的奇偶性相同。坐標平面上的任意整點按照橫縱兩個坐標的奇偶性考慮有且只有如下四種：（奇數(shù)、奇數(shù)），（偶數(shù)，偶數(shù)），（奇數(shù)，偶數(shù)），（偶數(shù)，奇數(shù)）以此構造四個“抽屜”，則在坐標平面上任取五個整點，那么至少有兩個整點，屬于同一個“抽屜”因此它們連線的中點就必是整點。 說明：我們可以把整點的概念推廣：如果（x1,x2,xn）是n維（元）有序數(shù)組，且x1,x2,xn中的每一個數(shù)都是整數(shù)，則稱（x1,x2,xn）是一個n維整點（整點又稱格點）。如果對所有的n維整點按每一個xi的奇偶性來分類，由于每一個位置上有奇、偶兩種可能性，因此共可分為222=2n個類。這是對n維整點的一種分類方法。當n=3時，23=8，此時可以構造命題：“任意給定空間中九個整點，求證它們之中必有兩點存在，使連接這兩點的直線段的內部含有整點”。這就是1971年的美國普特南數(shù)學競賽題。在n=2的情形，也可以構造如下的命題：“平面上任意給定5個整點”，對“它們連線段中點為整點”的4個命題中，為真命題的是： （A）最少可為0個，最多只能是5個 （B）最少可為0個，最多可取10個（C）最少為1個，最多為5個 （D）最少為1個，最多為10個（正確答案（D） 6分析：本題也似乎是茫無頭緒，無從下手，其關鍵何在？仔細審題，它們的“和”能“被100整除”應是做文章的地方。如果把這100個數(shù)排成一個數(shù)列，用Sm記其前m項的和，則其可構造S1，S2，S100共100個"和"數(shù)。討論這些“和數(shù)”被100除所得的余數(shù)。注意到S1，S2，S100共有100個數(shù)，一個數(shù)被100除所得的余數(shù)有0，1，2，99共100種可能性。“蘋果”數(shù)與“抽屜”數(shù)一樣多，如何排除“故障”？ 證明：設已知的整數(shù)為a1,a2,a100考察數(shù)列a1,a2,a100的前n項和構成的數(shù)列S1，S2，S100。 如果S1，S2，S100中有某個數(shù)可被100整除，則命題得證。否則，即S1，S2，S100均不能被100整除，這樣，它們被100除后余數(shù)必是1，2，99中的元素。由抽屜原理I知，S1，S2，S100中必有兩個數(shù)，它們被100除后具有相同的余數(shù)。不妨設這兩個數(shù)為Si，Sj（ij），則100（Sj-Si），即100。命題得證。 說明：有時候直接對所給對象作某種劃分，是很難構造出恰當?shù)某閷系摹＿@時候，我們需要對所給對象先作一些變換，然后對變換得到的對象進行分類，就可以構造出恰當?shù)某閷?。本題直接對an進行分類是很難奏效的。但由an構造出Sn后，再對Sn進行分類就容易得多。 另外，對Sn按模100的剩余類劃分時，只能分成100個集合，而Sn只有100項，似乎不能應用抽屜原則。但注意到余數(shù)為0的類恰使結論成立，于是通過分別情況討論后，就可去掉余數(shù)為0的類，從而轉化為100個數(shù)分配在剩下的99個類中。這種處理問題的方法應當學會，它會助你從“山窮水盡疑無路”時，走入“柳暗花明又一村”中。 最后，本例的結論及證明可以推廣到一般情形（而且有加強的環(huán)節(jié)）： 在任意給定的n個整數(shù)中，都可以找出若干個數(shù)來（可以是一個數(shù)），它們的和可被n整除，而且，在任意給定的排定順序的n個整數(shù)中，都可以找出若干個連續(xù)的項（可以是一項），它們的和可被n整除。 將以上一般結論中的n賦以相應的年份的值如xx，xx，xx，就可以編出相應年份的試題來。如果再賦以特殊背景，則可以編出非常有趣的數(shù)學智力題來，如下題： 有100只猴子在吃花生，每只猴子至少吃了1?；ㄉ?，多者不限。請你證明：一定有若干只猴子（可以是一只），它們所吃的花生的粒數(shù)總和恰好是100的倍數(shù)。 7證明：視17個科學家為17個點，每兩個點之間連一條線表示這兩個科學家在討論同一個問題，若討論第一個問題則在相應兩點連紅線，若討論第2個問題則在相應兩點連條黃線，若討論第3個問題則在相應兩點連條藍線。三名科學家研究同一個問題就轉化為找到一個三邊同顏色的三角形。 考慮科學家A，他要與另外的16位科學家每人通信討論一個問題，相應于從A出發(fā)引出16條線段，將它們染成3種顏色，而16=35+1，因而必有6=5+1條同色，不妨記為AB1，AB2，AB3，AB4，AB5，AB6同紅色，若Bi（i=1，2，6）之間有紅線，則出現(xiàn)紅色三角線，命題已成立；否則B1，B2，B3，B4，B5，B6之間的連線只染有黃藍兩色。 考慮從B1引出的5條線，B1B2，B1B3，B1B4，B1B5，B1B6，用兩種顏色染色，因為5=22+1，故必有3=2+1條線段同色，假設為黃色，并記它們?yōu)锽1B2，B1B3，B1B4。這時若B2，B3，B4之間有黃線，則有黃色三角形，命題也成立，若B2，B3，B4，之間無黃線，則B2，B3，B4，必為藍色三角形，命題仍然成立。 說明：（1）本題源于一個古典問題-世界上任意6個人中必有3人互相認識，或互相不認識。（美國普特南數(shù)學競賽題）。 （2）將互相認識用紅色表示，將互相不認識用藍色表示，（1）將化為一個染色問題，成為一個圖論問題：空間六個點，任何三點不共線，四點不共面，每兩點之間連線都涂上紅色或藍色。求證：存在三點，它們所成的三角形三邊同色。 （3）問題（2）可以往兩個方向推廣：其一是顏色的種數(shù)，其二是點數(shù)。 本例便是方向一的進展，其證明已知上述。如果繼續(xù)沿此方向前進，可有下題： 在66個科學家中，每個科學家都和其他科學家通信，在他們的通信中僅僅討論四個題目，而任何兩個科學家之間僅僅討論一個題目。證明至少有三個科學家，他們互相之間討論同一個題目。 （4）回顧上面證明過程，對于17點染3色問題可歸結為6點染2色問題，又可歸結為3點染一色問題。反過來，我們可以繼續(xù)推廣。從以上（3，1）（6，2）（17，3）的過程，易發(fā)現(xiàn)6=（3-1）2+2，17=（6-1）3+2，66=（17-1）4+2，同理可得（66-1）5+2=327，（327-1）6+2=1958記為r1=3，r2=6，r3=17，r4=66，r5=327，r6=1958，我們可以得到遞推關系式：rn=n(rn-1-1)+2，n=2,3,4這樣就可以構造出327點染5色問題，1958點染6色問題，都必出現(xiàn)一個同色三角形。