抽屜原理年與排列組合

抽屜原理與排列組合.抽屜原理把4只蘋果放到3個(gè)抽屜里去，共有3種放法，不論如何放，必有一個(gè)抽屜里至少放進(jìn)兩個(gè)蘋果。同樣，把5只蘋果放到4個(gè)抽屜里去，必有一個(gè)抽屜里至少放進(jìn)兩個(gè)蘋果?！M(jìn)一步，我們能夠得出這樣的結(jié)論：把n＋1只蘋果放到n個(gè)抽屜里去，那么必定有一個(gè)抽屜里至少放進(jìn)兩個(gè)蘋果。這個(gè)結(jié)論，通常被稱為抽屜原理。利用抽屜原理，可以說(shuō)明（證明）許多有趣的現(xiàn)象或結(jié)論。不過(guò)，抽屜原理不是拿來(lái)就能用的，關(guān)鍵是要應(yīng)用所學(xué)的數(shù)學(xué)知識(shí)去尋找“抽屜”，制造“抽屜”，弄清應(yīng)當(dāng)把什么看作“抽屜”，把什么看作“蘋果”。【例1】一個(gè)小組共有13名同學(xué)，其中至少有2名同學(xué)同一個(gè)月過(guò)生日。為什么？【分析】每年里共有12個(gè)月，任何一個(gè)人的生日，一定在其中的某一個(gè)月。如果把這12個(gè)月看成12個(gè)“抽屜”，把13名同學(xué)的生日看【例3】有規(guī)格尺寸相同的5種顏色的襪子各15只混裝在箱內(nèi)，試問(wèn)不論如何取，從箱中至少取出多少只就能保證有3雙襪子（襪子無(wú)左、右之分）？【分析】試想一下，從箱中取出6只、9只襪子，能配成3雙襪子嗎？回答是否定的。按5種顏色制作5個(gè)抽屜，根據(jù)抽屜原理1，只要取出6只襪子就總有一只抽屜里裝2只，這2只就可配成一雙。拿走這一雙，尚剩4只，如果再補(bǔ)進(jìn)2只又成6只，再根據(jù)抽屜原理1，又可配成一雙拿走。如果再補(bǔ)進(jìn)2只，又可取得第3雙。所以，至少要取6＋2＋2=10只襪子，就一定會(huì)配成3雙?！纠?】一個(gè)布袋中有35個(gè)同樣大小的木球，其中白、黃、紅三種顏色球各有10個(gè)，另外還有3個(gè)藍(lán)色球、2個(gè)綠色球，試問(wèn)一次至少取出多少個(gè)球，才能保證取出的球中至少有4個(gè)是同一顏色的球？【分析】從最“不利”的取出情況入手。最不利的情況是首先取出的5個(gè)球中，有3個(gè)是藍(lán)色球、2個(gè)綠色球。接下來(lái)，把白、黃、紅三色看作三個(gè)抽屜，由于這三種顏色球相等均超過(guò)4個(gè)，所以，根據(jù)抽屜原理2，只要取出的球數(shù)多于（4-1）×3=9個(gè)，即至少應(yīng)取出10個(gè)球，就可以保證取出的球至少有4個(gè)是同一抽屜（同一顏色）里的球。故總共至少應(yīng)取出10＋5=15個(gè)球。思考：把題中要求改為4個(gè)不同色，或者是兩兩同色，情形又如何？(答案分別為31和33）當(dāng)我們遇到“判別具有某種事物的性質(zhì)有沒(méi)有，至少有幾個(gè)”這樣的問(wèn)題時(shí)，想到它——抽屜原理，這是你的一條“決勝”之路。提示語(yǔ)抽屜原理還可以反過(guò)來(lái)理解：假如把n＋1個(gè)蘋果放到n個(gè)抽屜里，放2個(gè)或2個(gè)以上蘋果的抽屜一個(gè)也沒(méi)有（與“必有一個(gè)抽屜放2個(gè)或2個(gè)以上的蘋果”相反），那么，每個(gè)抽屜最多只放1個(gè)蘋果，n個(gè)抽屜最多有n個(gè)蘋果，與“n+1個(gè)蘋果”的條件矛盾。運(yùn)用抽屜原理的關(guān)鍵是“制造抽屜”。通常，可采用把n個(gè)“蘋果”進(jìn)行合理分類的方法來(lái)制造抽屜。比如，若干個(gè)同學(xué)可按出生的月份不同分為12類，自然數(shù)可按被3除所得余數(shù)分為3類排列組合問(wèn)題例1：某人到食堂去買飯，主食有三種，副食有五種，他主食和副食各買一種，共有多少種不同的買法？分析：某人買飯要分兩步完成，即先買一種主食，再買一種副食。其中，買主食有3種不同的方法，買副食有5種不同的方法。故可以由乘法原理解決：解：由乘法原理，主食和副食各買一種共有3×5=15種不同的方法。例2：書(shū)架上有6本不同的外語(yǔ)書(shū)，4本不同語(yǔ)文書(shū)，從中任取外語(yǔ)、語(yǔ)文書(shū)各一本，有多少本不同的取法？分析：要做的事情是從外語(yǔ)、語(yǔ)文書(shū)中各取一本。完成它要分兩步：即先取一本外語(yǔ)書(shū)（有6種取法），再取一本語(yǔ)文書(shū)（有4種取法）。所以，用乘法原理解決。解：從架上各取一本共有6×4＝24種不同的取法。例3：由數(shù)字0、1、2、3組成的三位數(shù)，問(wèn)：（1）、可組成多少個(gè)不相等的三位數(shù)？（2）、可組成多少個(gè)沒(méi)有重復(fù)數(shù)字的三位數(shù)？分析：在確定由0、1、2、3組成的三位數(shù)的過(guò)程中，應(yīng)該一位一位地去確定。所以，每個(gè)問(wèn)題都可以看成是分三個(gè)步驟來(lái)完成。（1）：要求組成不相等的三位數(shù)。所以，數(shù)字可以重復(fù)使用，百位上，不能取0，故有3種不同的取法；十位上，可以在四個(gè)數(shù)字中任取一個(gè)，有4種不同的取法；個(gè)位上，也有4種不同的取法，由乘法原理，共可組成3×4×4＝48個(gè)不相等的三位數(shù)。（2）：要求組成的三位數(shù)中沒(méi)有重復(fù)數(shù)字，百位上，不能取0，有3種不同的取法；十位上，由于百位上已在1、2、3中取走一個(gè)，故只剩下0和其它兩個(gè)數(shù)字，故有3種取法；個(gè)位上，由于百位和十位已各取走一個(gè)數(shù)字，故只能在剩下的兩個(gè)數(shù)字中取，有2種取法，由乘法原理，共有3×3×2＝18個(gè)沒(méi)有重復(fù)數(shù)字的三位數(shù)。例4：現(xiàn)有一角的人民幣4張，貳角的人民幣2張，壹元的人民幣3張，如果從中至少取一張，至多取9張，那么，共可以配成多少種不同的錢數(shù)？分析：要從三種面值的人民幣中任取幾張，構(gòu)成一個(gè)錢數(shù)，需一步一步地來(lái)做。如先取一解的，再取貳角的，最后取壹元的。但注意到，取2張一角的人民幣和取1張貳角的人民幣，得到的錢數(shù)是相同的。這就會(huì)產(chǎn)生重復(fù)，如何解決這一問(wèn)題呢？我們可以把壹角的人民幣4張和貳角的人民幣2張統(tǒng)一起來(lái)考慮。即從中取出幾張組成一種面值，看共可以組成多少種。分析得知，共可以組成從壹角到捌角間的任何一種面值，共8種情況。整個(gè)問(wèn)題就變成了從8張壹角的人民幣和3張壹元的人民幣中分別取錢。這樣，第一步，從8張壹角的人民幣中取，共9種取法，即0、1、2、3、4、5、6、7、8；第二步，從3張壹元的人民幣中取共4種取法，即0、1、2、3.由乘法原理，共有9×4＝36種情形，但注意到，要求”至少取一張”而現(xiàn)在包含了一張都不取的這一種情形，應(yīng)減掉。所以有35種不同的情形。例5：學(xué)校組織讀書(shū)活動(dòng)，要求每個(gè)同學(xué)讀一本書(shū)。小明到圖書(shū)館借書(shū)時(shí)，圖書(shū)館有不同的外語(yǔ)書(shū)150本，不同的科技書(shū)200本，不同的小說(shuō)100本。那么，小明借一本書(shū)可以有多少種不同的選法？分析：在這個(gè)問(wèn)題中，小明選一本書(shū)有三類方法。即要么選外語(yǔ)書(shū)，要么選科技書(shū)，要么選小說(shuō)。所以，是就用加法原理的問(wèn)題。解：小明借一本書(shū)共有：150+200+100=450（種）不同的選法。例6：一個(gè)口袋內(nèi)裝有3個(gè)小球，另一個(gè)口袋內(nèi)裝有8個(gè)小球，所有這些小球顏色各不相同。問(wèn)：（1）、從兩個(gè)口袋內(nèi)任取一個(gè)小球，有多少種不同的取法？（2）、從兩個(gè)口袋內(nèi)各取一個(gè)小球，有多少種不同的取法？分析：（1）、從兩個(gè)口袋中只需取一個(gè)小球，則這個(gè)小球要么從第一個(gè)口袋中取，要么從第二個(gè)口袋中取，共有兩大類方法。所以是加法原理的問(wèn)題。（2）、要從兩個(gè)口袋中各取一個(gè)小球，則可看成先從第一個(gè)口袋中取一個(gè)，再?gòu)牡诙€(gè)口袋中取一個(gè)，分兩步完成，是乘法原理的問(wèn)題。解（1）：3＋8＝11（種）（2）：3×8＝24（種）例7：有兩個(gè)相同的正方體，每個(gè)正方體的六個(gè)面上分別標(biāo)有數(shù)字1、2、3、4、5、6。將兩個(gè)正方體放到桌面上，向上的一面數(shù)字之和為偶數(shù)的有多少種情形？分析：要使兩個(gè)數(shù)字之和為偶數(shù)，只要這兩個(gè)數(shù)字的奇偶性相同，即這兩個(gè)數(shù)字同為奇數(shù)，要么同為偶數(shù)，所以，要分兩大類來(lái)考慮。第一類：兩個(gè)數(shù)字同