抽屜原理范文合集-文庫吧

【正文】 相識，那么可能出現(xiàn)這種情況：他們中的任何4人中都一定有2人不相識（假定相識是互相的）。分析：注意到題中的說法“可能出現(xiàn)……”，說明題的結(jié)論并非是條件的必然結(jié)果，而僅僅是一種可能性，因此只需要設(shè)法構(gòu)造出一種情況使之出現(xiàn)題目中所說的結(jié)論即可。解：將禮堂中的99人記為a1，a2，…，a99，將99人分為3組：（a1，a2，…，a33），（a34，a35，…，a66），（a67，a68，…，a99），將3組學生作為3個抽屜，分別記為A，B，C，并約定A中的學生所認識的66人只在B，C中，同時，B，C中的學生所認識的66人也只在A，C和A，B中。如果出現(xiàn)這種局面，那么題目中所說情況/ 7就可能出現(xiàn)。因為禮堂中任意4人可看做4個蘋果，放入A，B，C三個抽屜中，必有2人在同一抽屜，即必有2人來自同一組，那么他們認識的人只在另2組中，因此他們兩人不相識。例4 如右圖，分別標有數(shù)字1，2，…，8的滾珠兩組，放在內(nèi)外兩個圓環(huán)上，開始時相對的滾珠所標數(shù)字都不相同。當兩個圓環(huán)按不同方向轉(zhuǎn)動時，必有某一時刻，內(nèi)外兩環(huán)中至少有兩對數(shù)字相同的滾珠相對。分析：此題中沒有直接提供我們用以構(gòu)造抽屜和蘋果的數(shù)量關(guān)系，需要轉(zhuǎn)換一下看問題的角度。解：內(nèi)外兩環(huán)對轉(zhuǎn)可看成一環(huán)靜止，只有一個環(huán)轉(zhuǎn)動。一個環(huán)轉(zhuǎn)動一周后，每個滾珠都會有一次與標有相同數(shù)字的滾珠相對的局面出現(xiàn)，那么這種局面共要出現(xiàn)8次。將這8次局面看做蘋果，再需構(gòu)造出少于8個抽屜。注意到一環(huán)每轉(zhuǎn)動45176。角就有一次滾珠相對的局面出現(xiàn)，轉(zhuǎn)動一周共有8次滾珠相對的局面，而最初的8對滾珠所標數(shù)字都不相同，所以數(shù)字相同的滾珠相對的情況只出現(xiàn)在以后的7次轉(zhuǎn)動中，將7次轉(zhuǎn)動看做7個抽屜，8次相同數(shù)字滾珠相對的局面看做8個蘋果，則至少有2次數(shù)字相對的局面出現(xiàn)在同一次轉(zhuǎn)動中，即必有某一時刻，內(nèi)外兩環(huán)中至少有兩對數(shù)字相同的滾珠相對。例5 有一個生產(chǎn)天平上用的鐵盤的車間，由于工藝上的原因。，問：最少要生產(chǎn)多少個盤子，才能保證一定能從中挑出符合要求的兩只盤子？解：把20～：第1組：；第2組：；……第20組：。這樣，只要有21個盤子，就一定可以從中找到兩個盤子屬于同一組，這2個盤子就符合要求。例6 在圓周上放著100個籌碼，其中有41個紅的和59個藍的。那么總可以找到兩個紅籌碼，在它們之間剛好放有19個籌碼，為什么？分析：此題需要研究“紅籌碼”的放置情況，因而涉及到“蘋果”的具體放置方法，由此我們可以在構(gòu)造抽屜時，使每個抽屜中的相鄰“蘋果”之間有19個籌碼。解：依順時針方向?qū)⒒I碼依次編上號碼：1，2，…，100。然后依照以下規(guī)律將100個籌碼分為20組：（1，21，41，61，81）；（2，22，42，62，82）；……（20，40，60，80，100）。將41個紅籌碼看做蘋果，放入以上20個抽屜中，因為41=220＋1，所以至少有一個抽屜中有2+1=3（個）蘋果，也就是說必有一組5個籌碼中有3個紅色籌碼，而每組的5個籌碼在圓周上可看做兩兩等距，且每2個相鄰籌碼之間都有19個籌碼，那么3個紅色籌碼中必有2個相鄰（這將在下一個內(nèi)容——第二抽屜原理中說明），即有2個紅色籌碼之間有19個籌碼。下面我們來考慮另外一種情況：若把5個蘋果放到6個抽屜中，則必然有一個抽屜空著。這種情況一般可以表述為：/ 7第二抽屜原理：把（mn1）個物體放入n個抽屜，其中必有一個抽屜中至多有（m1）個物體。例7 在例6中留有一個疑問，現(xiàn)改述如下：在圓周上放有5個籌碼，其中有3個是同色的，那么這3個同色的籌碼必有2個相鄰。分析：將這個問題加以轉(zhuǎn)化：如右圖，將同色的3個籌碼A，B，C置于圓周上，看是否能用另外2個籌碼將其隔開。解：如圖，將同色的3個籌碼放置在圓周上，將每2個籌碼之間的間隔看做抽屜，將其余2個籌碼看做蘋果，將2個蘋果放入3個抽屜中，則必有1個抽屜中沒有蘋果，即有2個同色籌碼之間沒有其它籌碼，那么這2個籌碼必相鄰。例8 甲、乙二人為一個正方形的12條棱涂紅和綠2種顏色。首先，甲任選3條棱并把它們涂上紅色；然后，乙任選另外3條棱并涂上綠色；接著甲將剩下的6條棱都涂上紅色。問：甲是否一定能將某一面的4條棱全部涂上紅色？解：不能。如右圖將12條棱分成四組：第一組：{A1B1，B2B3，A3A4}，第二組：{A2B2，B3B4，A4A1}，第三組：{A3B3，B4B1，A1A2}，第四組：{A4B4，B1B2，A2A3}。無論甲第一次將哪3條棱涂紅，由抽屜原理知四組中必有一組的3條棱全未涂紅，而乙只要將這組中的3條棱涂綠，甲就無法將某一面的4條棱全部涂紅了。下面我們討論抽屜原理的一個變形——平均值原理。我們知道n個數(shù)a1，a2，…，an的和與n的商是a1，a2，…，an這n個數(shù)的平均值。平均值原理：如果n個數(shù)的平均值為a，那么其中至少有一個數(shù)不大于a，也至少有一個不小于a。例9 圓周上有2000個點，在其上任意地標上0，1，2，…，1999（每一點只標一個數(shù)，不同的點標上不同的數(shù)）。求證：必然存在一點，與它緊相鄰的兩個點和這點上所標的三個數(shù)之和不小于2999。解：設(shè)圓周上各點的值依次是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）＝31999000。這2000組和中必至少有一組和大于或等于但因每一個和都是整數(shù)，故有一組相鄰三數(shù)之和不小于2999，亦即存在一個點，與它緊相鄰的兩點和這點上所標的三數(shù)之和不小于2999。例10 一家旅館有90個房間，住有100名旅客，如果每次都恰有90名旅客同時回來，那么至少要準備多少把鑰匙分給這100名旅客，才能使得每次客人回來時，每個客人都能用自己分到的鑰匙打開一個房門住進去，并且避免發(fā)生兩人同時住進一個房間？解：如果鑰匙數(shù)小于990，那么90個房間中至少有一個房間的鑰匙數(shù)少房間就打不開，因此90個人就無法按題述的條件住下來。/ 7另一方面，990把鑰匙已經(jīng)足夠了，這只要將90把不同的鑰匙分給90個人，而其余的10名旅