六年級(jí)奧數(shù)-第九講.復(fù)雜抽屜原理.教師版

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第九講 復(fù)雜抽屜原理內(nèi)容概述運(yùn)用抽屜原理求解的較為復(fù)雜的組合計(jì)算與證明問題這里不僅“抽屜”與“蘋果”需要恰當(dāng)?shù)卦O(shè)計(jì)與選取，而且有時(shí)還應(yīng)構(gòu)造出達(dá)到最佳狀態(tài)的例子典型問題1從1，2，3，1988，1989這些自然數(shù)中，最多可以取出多少個(gè)數(shù)，使得其中每?jī)蓚€(gè)數(shù)的差不等于4？ 【分析與解】1，2，3，4，9，10，1l，12，17，18，19，20，25， 這些數(shù)中任何兩個(gè)數(shù)的差都不為4，這些數(shù)是每8個(gè)連續(xù)的數(shù)中選取前4個(gè)連續(xù)的數(shù) 有1989÷8=2485，所以最多可以選248×4+4=996個(gè)數(shù) 評(píng)注：對(duì)于這類問題，一種方法是先盡可能的多選擇，然后再找出這

2、些數(shù)的規(guī)律，再計(jì)算出最多可以選出多少個(gè).2從1至1993這1993個(gè)自然數(shù)中最多能取出多少個(gè)數(shù)，使得其中任意的兩數(shù)都不連續(xù)且差不等于4？ 【分析與解】1，3，6，8，11，13，16，18，21， 這些數(shù)中任何兩個(gè)數(shù)不連續(xù)且差不等于4，這些數(shù)是每5個(gè)連續(xù)的數(shù)中選擇第1、3個(gè)數(shù) 1993÷5=3983.所以最多可以選398×2+2=798個(gè)數(shù) 評(píng)注：當(dāng)然還可以是1，4，6，9，11，14，16，19，21， 這些數(shù)滿足條件，是每5個(gè)連續(xù)的數(shù)中選擇第1、4個(gè)數(shù)但是此時(shí)最多只能選出398×2+l=797個(gè)數(shù)3. 從1，2，3，4，5，6，7，8，9，10，11，12中最

3、多能選出幾個(gè)數(shù)，使得在選出的數(shù)中，每一個(gè)數(shù)都不是另一個(gè)數(shù)的2倍? 【分析與解】 方法一：直接從1開始選1，3，4，5，7，9，11，12，這樣可以選出8個(gè)數(shù)； 而從2開始選2，3，5，7，8，9，11，12，這樣也是可以選出8個(gè)數(shù) 3包含在組內(nèi)，因此只用考慮這兩種情況即可 所以，在滿足題意情況下，最多可以選出8個(gè)數(shù) 方法二：我們知道選多少個(gè)奇數(shù)均滿足，有1，3，5，7，9，11均為奇數(shù)，并且有偶數(shù)中4的倍數(shù)，但不是8的倍數(shù)的也滿足，有4，12是這樣的數(shù)所以，在滿足題意情況下最多可以選出8個(gè)數(shù)4從1，3，5，7，97，99中最多可以選出多少個(gè)數(shù)，使得選出的數(shù)中，每一個(gè)數(shù)都不是另一個(gè)數(shù)的倍數(shù)? 【

4、分析與解】 方法一：因?yàn)榫瞧鏀?shù)，所以如果存在倍數(shù)關(guān)系，那么也一定是3、5、7等奇數(shù)倍. 3×33：99，于是從35開始，199的奇數(shù)中沒有一個(gè)是3599的奇數(shù)倍(不包括1倍)，所以選出35，37，39，99這些奇數(shù)即可 共可選出33個(gè)數(shù)，使得選出的數(shù)中，每一個(gè)數(shù)都不是另一個(gè)數(shù)的倍數(shù) 方法二：利用3的若干次冪與質(zhì)數(shù)的乘積對(duì)這50個(gè)奇數(shù)分組 (1，3，9，27，81)，(5，15，45)，(7，21，63)，(11，33)，(13，39)，(17，51)，(19，57)，(23，69)，(25，75)，(29，87)，(31，93)，(35)，(37)，(41)，(43)，(97)共3

5、3組 前11組，每組內(nèi)任意兩個(gè)數(shù)都存在倍數(shù)關(guān)系，所以每組內(nèi)最多只能選擇一個(gè)數(shù) 即最多可以選出33個(gè)數(shù)，使得選出的數(shù)中，每一個(gè)數(shù)都不是另一個(gè)數(shù)的倍數(shù) 評(píng)注：12n個(gè)自然數(shù)中，任意取出n+1個(gè)數(shù)，則其中必定有兩個(gè)數(shù)，它們一個(gè)是另一個(gè)的整數(shù)倍； 從2，3，2n+1中任取n+2個(gè)數(shù)，必有兩個(gè)數(shù)，它們一個(gè)是另一個(gè)的整數(shù)倍； 從1，2，33n中任取2n+1個(gè)數(shù)，則其中必有兩個(gè)數(shù)，它們中一個(gè)是另一個(gè)的整數(shù)倍，且至少是3倍；從1，2，3， mn中任取(m-1)n+1個(gè)數(shù)，則其中必有兩個(gè)數(shù)，它們中一個(gè)是另一個(gè)的整數(shù)倍，且至少是m倍(m、n為正整數(shù)).5證明：任給12個(gè)不同的兩位數(shù)，其中一定存在著這樣的兩個(gè)數(shù)，它

6、們的差是個(gè)位與十位數(shù)字相同的兩位數(shù) 【分析與解】 因?yàn)閮蓚€(gè)不同的兩位數(shù)相減得到的差不可能為三位或三位以上的數(shù)如果這個(gè)差是1l的倍數(shù)，那么一定有這個(gè)差的個(gè)位與十位數(shù)字相同 兩個(gè)數(shù)的差除以1l的余數(shù)有0、1、2、3、10這11種情況將這11種情況視為11個(gè)抽屜 將12個(gè)數(shù)視為12個(gè)蘋果，那么必定有兩個(gè)蘋果在同一抽屜，也就是說有兩個(gè)數(shù)除以11的余數(shù)相同，那么它們的差一定是11的倍數(shù) 而兩個(gè)兩位數(shù)的差一定是一個(gè)兩位數(shù)，如果這個(gè)差是11的倍數(shù)，那么就有個(gè)數(shù)與十位數(shù)字相等問題得證 評(píng)注：抽屜原理一：將n+1個(gè)元素放到n個(gè)抽屜中去，則無論怎么放，必定有一個(gè)抽屜至少有兩個(gè)元素 抽屜原理二：將nr+1個(gè)元素放到

7、n個(gè)抽屜中去，則無論怎么放，必定有一個(gè)抽屜至少有r+1個(gè)元素抽屜原理三：將m個(gè)元素放到n個(gè)抽屜中去(mn)，則無論怎么放，必定有一個(gè)抽屜至少有個(gè)元素6從1，2，3，49，50這50個(gè)數(shù)中取出若干個(gè)數(shù)，使其中任意兩個(gè)數(shù)的和都不能被7整除，則最多能取出多少個(gè)數(shù)? 【分析與解】 利用除以7的余數(shù)分類： 余0：(7，14，21，28，35，42，49)； 余1：(1，8，15，22，29，36，43，50)； 余2：(2，9，16，23，30，37，44)； 余3：(3，10，17，24，31，38，45)； 余4：(4，11，18，25，32，39，46)； 余5：(5，12，19，26，33，40

8、，47)； 余6：(6，13，20，27，34，41，48) 第一組內(nèi)的數(shù)最多只能取1個(gè)；如果取第二組，那么不能取第七組內(nèi)任何一個(gè)數(shù)；取第三組，不能取第六組內(nèi)任何一個(gè)數(shù)；取第四組，不能取第五組內(nèi)任意一個(gè)數(shù)第二、三、四、五、六、七組分別有8、7、7、7、7、7個(gè)數(shù)，所以最多可以取1+8+7+7=23個(gè)數(shù)7從1，2，3，99，100這100個(gè)數(shù)中任意選出51個(gè)數(shù)證明： (1)在這51個(gè)數(shù)中，一定有兩個(gè)數(shù)互質(zhì)； (2)在這51個(gè)數(shù)中，一定有兩個(gè)數(shù)的差等于50； (3)在這51個(gè)數(shù)中，一定存在9個(gè)數(shù)，它們的最大公約數(shù)大于1 【分析與解】 (1)我們將1100分成(1，2)，(3，4)，(5，6)，(7

9、，8)，(99，100)這50組，每組內(nèi)的數(shù)相鄰而相鄰的兩個(gè)自然數(shù)互質(zhì) 將這50組數(shù)作為50個(gè)抽屜，同一個(gè)抽屜內(nèi)的兩個(gè)數(shù)互質(zhì) 而現(xiàn)在51個(gè)數(shù)，放進(jìn)50個(gè)抽屜，則必定有兩個(gè)數(shù)在同一抽屜，于是這兩個(gè)數(shù)互質(zhì)問題得證 (2)我們將1100分成(1，51)，(2，52)，(3，53)，(40，90)，(50，100)這50組，每組內(nèi)的數(shù)相差50將這50組數(shù)視為抽屜，則現(xiàn)在有51個(gè)數(shù)放進(jìn)50個(gè)抽屜內(nèi)，則必定有2個(gè)數(shù)在同一抽屜，那么這兩個(gè)數(shù)的差為50問題得證 (3)我們將1100按2的倍數(shù)、3的奇數(shù)倍、既不是2又不是3的倍數(shù)的情況分組，有(2，4，6，8，98，100)，(3，9，15，21，27，93，9

10、9)，(5，7，11，13，17，19，23，95，97)這三組第一、二、三組分別有50、17、33個(gè)元素最不利的情況下，51個(gè)數(shù)中有33個(gè)元素在第三組，那么剩下的18個(gè)數(shù)分到第一、二兩組內(nèi)，那么至少有9個(gè)數(shù)在同一組所以這9個(gè)數(shù)的最大公約數(shù)為2或3或它們的倍數(shù)，顯然大于1問題得證8求證：可以找到一個(gè)各位數(shù)字都是4的自然數(shù)，它是1996的倍數(shù) 【分析與解】注意到1996=4×499； 對(duì)于l，1l，11l， 中必定有兩個(gè)數(shù)關(guān)于499同余 于是(mod 499)(m>n) 有-=，所以499 ，因?yàn)?499，)=l，所以499；于是有(499×4)（4），即1996 于是

11、，就找到這樣的全部都是由4組成的數(shù)字，是1996的倍數(shù) 評(píng)注：、可整除不合2，5因數(shù)的任何整數(shù)； 、整除不含因數(shù)5(因數(shù)2分別只能含1，2，2，3個(gè))的任何整數(shù)； 整除不含因數(shù)2(因數(shù)5只能含1個(gè))的任何整數(shù)9有49個(gè)小孩，每人胸前有一個(gè)號(hào)碼，號(hào)碼從1到49各不相同現(xiàn)在請(qǐng)你挑選若干個(gè)小孩，排成一個(gè)圓圈，使任何相鄰兩個(gè)小孩的號(hào)碼數(shù)的乘積小于100，那么你最多能挑選出多少個(gè)孩子? 【分析與解】 將1至49中相乘小于100的兩個(gè)數(shù)，按被乘數(shù)分成9組，如下： (1×2)、(1×3)、(1×4)、(1×49)； (2×3)、(2×4)、(2&#

12、215;5)、(2×49)； (8×9)、(8×10)、(8 ×11)、(8×12)； (9×10)、(9×11). 因?yàn)槊總€(gè)數(shù)只能與左右兩個(gè)數(shù)相乘，也就是每個(gè)數(shù)作為被乘數(shù)或乘數(shù)最多兩次，所以每一組中最多會(huì)有兩對(duì)數(shù)出現(xiàn)在圓圈中，最多可以取出18個(gè)數(shù)對(duì)，共18 ×2=36次，但是每個(gè)數(shù)都出現(xiàn)兩次，故出現(xiàn)了18個(gè)數(shù) 例如：(10×9)、(9×11)、(1×8)、(8×12)、(12×7)、(7×13)、(13×6)、(6×14)、(14&#

13、215;5)、(5×15)、(15×4)、(4 ×16)、(16 X 3)、(3×17)、(17×2)、(2×18)、(18 ×1)、(1×10)共出現(xiàn)l18號(hào)，共18個(gè)孩子 若隨意選取出19個(gè)孩子，那么共有19個(gè)號(hào)碼，由于每個(gè)號(hào)碼數(shù)要與旁邊兩數(shù)分別相乘，則會(huì)形成19個(gè)相乘的數(shù)對(duì) 那么在9組中取出19個(gè)數(shù)時(shí)，有19=9×2+1，由抽屜原則知，必有三個(gè)數(shù)對(duì)落入同一組中，這樣某個(gè)數(shù)字會(huì)在數(shù)對(duì)中出現(xiàn)三次(或三次以上)，由分析知，這是不允許的故最多挑出18個(gè)孩子10. 在邊長(zhǎng)為1的正方形內(nèi)隨意放進(jìn)9個(gè)點(diǎn)，證明其中

14、必有3個(gè)點(diǎn)構(gòu)成的三角形的面積不大于 【分析與解】 如下圖，把正方形分成四個(gè)形狀相同、大小相等的正方形9個(gè)點(diǎn)任意放人這四個(gè)正方形中 根據(jù)抽屜原理，多于2×4個(gè)點(diǎn)放入四個(gè)長(zhǎng)方形中，至少有2+1個(gè)點(diǎn)(即3個(gè)點(diǎn))落在某一個(gè)正方形之內(nèi)現(xiàn)在，特別取出這個(gè)正方形來加以討論 把落在這正方形中的三點(diǎn)組成的三角形記為ABC，其面積不超過小正方形面積的，所以其面積不超過這樣就得到了需要證明的結(jié)論 評(píng)注：在邊長(zhǎng)為1的等邊三角形中有個(gè)點(diǎn)，這個(gè)點(diǎn)中一定有距離不大于的兩點(diǎn)； 在邊長(zhǎng)為l的等邊三角形內(nèi)有個(gè)點(diǎn)，這個(gè)點(diǎn)中一定有距離小于的兩點(diǎn) 已知平行四邊形中，其面積為l，現(xiàn)有個(gè)點(diǎn)，則必定有三點(diǎn)組成的三角形，其面積不大于

15、； 已知三角形中，其面積為1，現(xiàn)有個(gè)點(diǎn)，則必定有三點(diǎn)組成的三角形，其面積不大于11某班有16名學(xué)生，每個(gè)月教師把學(xué)生分成兩個(gè)小組問最少要經(jīng)過幾個(gè)月，才能使該班的任意兩個(gè)學(xué)生總有某個(gè)月份是分在不同的小組里? 【分析與解】經(jīng)過第一個(gè)月，將16個(gè)學(xué)生分成兩組，至少有8個(gè)學(xué)生分在同一組，下面只考慮這8個(gè)學(xué)生 經(jīng)過第二個(gè)月，將這8個(gè)學(xué)生分成兩組，至少有4個(gè)學(xué)生是分在同一組，下面只考慮這4個(gè)學(xué)生 經(jīng)過第三個(gè)月，將這4個(gè)學(xué)生分成兩組，至少有2個(gè)學(xué)生仍分在同一組，這說明只經(jīng)過3個(gè)月是無法滿足題目要求的 如果經(jīng)過四個(gè)月，將每個(gè)月都一直保持同組的學(xué)生一分為二，放人兩個(gè)組，那么第一個(gè)月保持同組的人數(shù)為16÷

16、;2=8人，第二個(gè)月保持同組的人數(shù)為8÷2=4人，第三個(gè)月保持同組人數(shù)為4÷2=2人，這說明，照此分法，不會(huì)有2個(gè)人一直保持在同一組內(nèi)，即滿足題目要求，故最少要經(jīng)過4個(gè)月12上體育課時(shí)，21名男、女學(xué)生排成3行7列的隊(duì)形做操老師是否總能從隊(duì)形中劃出一個(gè)長(zhǎng)方形，使得站在這個(gè)長(zhǎng)方形4個(gè)角上的學(xué)生或者都是男生，或者都是女生?如果能，請(qǐng)說明理由；如果不能，請(qǐng)舉出實(shí)例 【分析與解】 因?yàn)橹挥心猩蚺鷥煞N情況，所以第1行的7個(gè)位置中至少有4個(gè)位置同性別 為了確定起見，不妨設(shè)前4個(gè)位置同是男生，如果第二行的前4個(gè)位置有2名男生，那么4個(gè)角同是男生的情況已經(jīng)存在，所以我們假定第二行的前4

17、個(gè)位置中至少有3名女生，不妨假定前3個(gè)是女生 又第三行的前3個(gè)位置中至少有2個(gè)位置是同性別學(xué)生，當(dāng)是2名男生時(shí)與第一行構(gòu)成一個(gè)四角同性別的矩形，當(dāng)有2名女生時(shí)與第二行構(gòu)成四角同性別的矩形 所以，不論如何，總能從隊(duì)形中劃出一個(gè)長(zhǎng)方形，使得站在這個(gè)長(zhǎng)方形4個(gè)角上的學(xué)生同性別問題得證138個(gè)學(xué)生解8道題目 (1)若每道題至少被5人解出，請(qǐng)說明可以找到兩個(gè)學(xué)生，每道題至少被過兩個(gè)學(xué)生中的一個(gè)解出 (2)如果每道題只有4個(gè)學(xué)生解出，那么(1)的結(jié)論一般不成立試構(gòu)造一個(gè)例子說明這點(diǎn). 【分析與解】 (1)先設(shè)每道題被一人解出稱為一次，那么8道題目至少共解出58=40次，分到8個(gè)學(xué)生身上，至少有一個(gè)學(xué)生解出

18、了5次或5次以上題目，即這個(gè)學(xué)生至少解出5道題，稱這個(gè)學(xué)生為4，我們討論以下4種可能： 第一種可能：若4只解出5道題，則另3道題應(yīng)由其他7個(gè)人解出，而3道題至少共被解出35=15次，分到7個(gè)學(xué)生身上，至少有一名同學(xué)解出了3次或3次以上的題目(15=27+1，由抽屜原則便知)由于只有3道題，那么這3道題被一名學(xué)生全部解出，記這名同學(xué)為B 那么，每道題至少被A、B兩名同學(xué)中某人解出 第二種可能：若A解出6道題，則另2道題應(yīng)由另7人解出，而2道題至少共被解出2×5=10次，分到7個(gè)同學(xué)身上，至少有一名同學(xué)解出2次或2次以上的題目(10=17+3，由抽屜原則便知)與l第一種可能I同理，這兩道

19、題必被一名學(xué)生全部解出，記這名同學(xué)為C 那么，每道題目至少被A、C學(xué)生中一人解出 第三種可能：若A解出7道題目，則另一題必由另一人解出，記此人為D那么，每道題目至少被A、D兩名學(xué)生中一人解出 第四種可能：若A解出8道題目，則隨意找一名學(xué)生，記為E，那么，每道題目至少被A、E兩名學(xué)生中一人解出，所以問題(1)得證 (2)類似問題(1)中的想法，題目共被解出84=32次，可以使每名學(xué)生都解出4次，那么每人解出4道題 隨便找一名學(xué)生，必有4道未被他解出，這4道題共被7名同學(xué)解出44=16次，由于16=2×7+2，可以使每名同學(xué)解出題目不超過3道，這樣就無法找到兩名學(xué)生，使每道題目至少被其中

20、一人解出 具體構(gòu)造如下表，其中漢字代表題號(hào)，數(shù)字代表學(xué)生，打代表該位置對(duì)應(yīng)的題目被該位置對(duì)應(yīng)的學(xué)生解出14時(shí)鐘的表盤上按標(biāo)準(zhǔn)的方式標(biāo)著1，2，3，11，12這12個(gè)數(shù)，在其上任意做n個(gè)的扇形，每一個(gè)都恰好覆蓋4個(gè)數(shù)，每?jī)蓚€(gè)覆蓋的數(shù)不全相同如果從這任做的n個(gè)扇形中總能恰好取出3個(gè)覆蓋整個(gè)鐘面的全部12個(gè)數(shù)，求n的最小值 【分析與解】 如下圖，只要從某個(gè)數(shù)字對(duì)應(yīng)的位置開始，做出的扇形，一定能覆蓋4個(gè)數(shù) 從最不利的情況出發(fā)，n個(gè)扇形中最大程度的重疊，需做(12，1，2，3)，(1，2，3，4)，(2，3，4，5)，(3，4，5，6)，(4，5，6，7)，(5，6，7，8)，(6，7，8，9)，(7，8，9，10)，(8，9，