四年級(jí)秋季班第五講-簡(jiǎn)單抽屜原理、最不利原則

第五講簡(jiǎn)單抽屜原理、最不利原那么知識(shí)框架對(duì)抽屜原理兩個(gè)版本的認(rèn)識(shí)抽屜原理1：將n+1個(gè)物品任意放到n個(gè)抽屜中，那么至少有一個(gè)抽屜中的物品不少于2件。抽屜原理1：將n+1個(gè)物品任意放到n個(gè)抽屜中，那么至少有一個(gè)抽屜中的物品不少于2件。原理要點(diǎn)：物品數(shù)比抽屜數(shù)多1。只有物品數(shù)比抽屜數(shù)多時(shí)抽屜原理才會(huì)成立。物品是“任意放〞到抽屜中。其中“物品不少于2件〞的抽屜是一定存在的，但是不確定是哪一個(gè)。原理的結(jié)論是：“至少有一個(gè)抽屜中的物品數(shù)不少于2件〞，也可以這么說，“至少有2件物品在同一個(gè)抽屜中〞。原理講解：只要有一個(gè)抽屜中的物品數(shù)不少于2件，抽屜原理1就是成立的。當(dāng)我們可以往抽屜中任意放物品時(shí)，最不利的情形就是“平均分〞，這樣所有抽屜中的物品數(shù)都不會(huì)太多。n+1個(gè)物品平均地放入n個(gè)抽屜，每個(gè)抽屜放一個(gè)，由于物品數(shù)比抽屜數(shù)多，就會(huì)余出一個(gè)物品。最后，余出的這個(gè)物品放入某個(gè)抽屜，這個(gè)抽屜中就有了2個(gè)物品。此外，其它情形，只要有一個(gè)抽屜是空的，那么就一定會(huì)有另外的抽屜中有2個(gè)或2個(gè)以上的物品。例子：4只鴿子飛回三個(gè)鳥籠，有幾種方法？1號(hào)鳥籠2號(hào)鳥籠3號(hào)鳥籠方法一400方法二310方法三220方法四211每種方法中，都會(huì)有一個(gè)鳥籠中的鴿子數(shù)不少于2。在有些地方抽屜原理又叫做“鴿籠原理〞。抽屜原理2〔加強(qiáng)版的抽屜原理〕抽屜原理2〔加強(qiáng)版的抽屜原理〕將m件物品任意放入n個(gè)抽屜〔m>n〕，當(dāng)m是n的整數(shù)倍時(shí)，那么至少有一個(gè)抽屜中的物品件數(shù)是不少于m÷n件；當(dāng)m不是n的整數(shù)倍時(shí)，那么至少有一個(gè)抽屜中的物品件數(shù)是不少于[m÷n]+1件。注：假設(shè)m÷n=a…b，那么就說[m÷n]=a，也就是只要商，余數(shù)不要了。稱這個(gè)過程為取整。原理要點(diǎn)：物品數(shù)比抽屜數(shù)多，抽屜原理1的情形包含于這個(gè)原理中；解決的是抽屜的存在性；在解題時(shí)，遇到“有一個(gè)抽屜中的物品數(shù)不少于A件〞，其中A>2時(shí)，應(yīng)使用抽屜原理2。原理的結(jié)論也可以理解為：“總有不少于m÷n件〔或[m÷n]+1件〕物品在同一個(gè)抽屜中。〞相同的即為“抽屜〞。原理講解：最不利的情形就是“平均分〞，這樣每個(gè)抽屜中的物品數(shù)都不太多都是[m÷n]個(gè)。假設(shè)m÷n有余數(shù)，那么多出來的余數(shù)個(gè)物品也按照最不利的情形來分配，這樣就能保證抽屜中的物品盡量地少。也就是說這余數(shù)個(gè)物品也平均地往抽屜中放，這樣有的抽屜會(huì)再放入一個(gè)物品，而有的就分不到，那么至少會(huì)有一個(gè)抽屜中的物品數(shù)不少于[m÷n]+1個(gè)。這也解釋了物品數(shù)是不少于[m÷n]+1，而不是“不少于[m÷n]+余數(shù)〞。如何構(gòu)造抽屜袋中取球問題練習(xí)1在一個(gè)口袋中有紅色、黃色、藍(lán)色球假設(shè)干個(gè)，小聰明和其它六個(gè)小朋友一起做游戲，每人可以從口袋中任意取出2個(gè)球，那么不管怎么挑選，總有兩個(gè)小朋友取出的兩個(gè)球的顏色完全一樣。分析：〔方法1〕從問題出發(fā)?！翱傆袃蓚€(gè)小朋友取出的兩個(gè)球的顏色完全一樣〞，相同的是“取出的兩個(gè)球的顏色搭配〞，這就是“抽屜〞。取出的兩個(gè)球的顏色，可能的情況有如下六種：紅紅、黃黃、藍(lán)藍(lán)，紅藍(lán)、紅黃、藍(lán)黃。也就是說有6個(gè)抽屜。小聰明和其它6個(gè)小朋友一起做游戲，共7人，也就是有7個(gè)物品。物品數(shù)比抽屜數(shù)多1，根據(jù)抽屜原理1，總有2個(gè)小朋友取出的兩個(gè)球的顏色完全一樣。〔方法2〕從條件出發(fā)。每人從口袋中任意取出2個(gè)球，取出的顏色搭配可能有6種情形，取球的共有7個(gè)小朋友。小朋友數(shù)比顏色搭配數(shù)多1，那么7小朋友是“物品〞，6種顏色搭配是“抽屜〞。根據(jù)抽屜原理1，總有兩個(gè)小朋友取出的兩個(gè)球的顏色搭配相同。拓展口袋中放有足夠多的紅、白、藍(lán)三種顏色的球，現(xiàn)有31人輪流從袋子中取球，每人各取3個(gè)。證明：至少有4人取出球的顏色一樣。分析：類似練習(xí)1，取出球的顏色搭配是抽屜。搭配可能有：紅紅白、紅紅藍(lán)、藍(lán)藍(lán)紅、藍(lán)藍(lán)白、白白紅、白白藍(lán)、紅白藍(lán)，紅紅紅、白白白、藍(lán)藍(lán)藍(lán)，共10種。也就是說有10個(gè)抽屜。31個(gè)人看成是物品。，那么。根據(jù)抽屜原理2，至少有4人取出球的顏色是一樣的?？偨Y(jié)：總結(jié)：構(gòu)造抽屜的兩種方法：〔1〕從問題出發(fā)，相同的就是“抽屜〞；〔2〕從數(shù)量關(guān)系出發(fā)，多的是“物品〞，少的是“抽屜〞。數(shù)的整除性與抽屜原理余數(shù)的性質(zhì)：余數(shù)相同，差無余數(shù)。也就是說，兩個(gè)數(shù)除以同一個(gè)數(shù)得到的余數(shù)相同，那么這兩個(gè)數(shù)的差再去除以這同一個(gè)數(shù)時(shí)沒有余數(shù)。例：和的余數(shù)都是2，那么沒有余數(shù)。余數(shù)的和等于和的余數(shù)。也就是說，幾個(gè)數(shù)除以同一個(gè)數(shù)得到的余數(shù)相加所得的和再除以同一個(gè)數(shù)得到的余數(shù)，等于原本幾個(gè)數(shù)的和除以同一個(gè)數(shù)所得的余數(shù)。例：的余數(shù)是2，的余數(shù)是4，，的余數(shù)是1；的余數(shù)也是1。練習(xí)2在任意的4個(gè)自然數(shù)中，是否其中必有兩個(gè)數(shù)，它們的差能被3整除？分析：一個(gè)自然數(shù)除以3，其余數(shù)只能是0,1,2三種情形。將余數(shù)的這三種情形看做3個(gè)抽屜，一個(gè)自然數(shù)除以3的余數(shù)是幾，就將自然數(shù)放入那個(gè)“抽屜〞中。那么任意的4個(gè)自然數(shù)放入這3個(gè)抽屜中，根據(jù)抽屜原理，至少有一個(gè)抽屜中有不少于2個(gè)自然數(shù)。那么這個(gè)抽屜中的兩個(gè)自然數(shù)的差就能被3整除。拓展在任意的5個(gè)自然數(shù)中，是否必有其中三個(gè)數(shù)的和是3的倍數(shù)？分析：構(gòu)造抽屜的方法如練習(xí)2。那么可能出現(xiàn)兩種情形：〔1〕每個(gè)抽屜中都至少有一個(gè)數(shù)。這樣，每個(gè)抽屜中取出一個(gè)數(shù)，這三個(gè)數(shù)的余數(shù)分別是0,1,2.，那么余數(shù)的和為，除以3沒有余數(shù)，那么取出的這三個(gè)數(shù)的和除以3也沒有余數(shù)?！?〕有一個(gè)抽屜中有不少于3個(gè)數(shù)。從這樣的抽屜中取出3個(gè)數(shù)，這三個(gè)數(shù)的余數(shù)相同，那么余數(shù)的和是3×余數(shù)，除以3沒有余數(shù)，那么取出的這三個(gè)數(shù)的和除以3也沒有余數(shù)?？偨Y(jié)：總結(jié)：題目中出現(xiàn)“幾個(gè)數(shù)得和〔或差〕是某數(shù)的倍數(shù)〞時(shí)，就是數(shù)的整除性結(jié)合了抽屜原理，余數(shù)做抽屜。抽屜原理的應(yīng)用求抽屜中物品至多數(shù)練習(xí)317名同學(xué)參加一次考試，考試題是三道判斷題〔答案只有對(duì)錯(cuò)之分〕，每名同學(xué)都在答題紙上依次寫下三道題的答案。請(qǐng)問至少有幾名同學(xué)的答案是一樣的？分析：從問題出發(fā)找抽屜，相同的是答案，這就是抽屜。求抽屜數(shù)時(shí)可用乘法原理：每一道題都有2種答案，所以三道題的答案有種，即有8個(gè)抽屜。物品為17名同學(xué)。，由抽屜原理2，至少有名同學(xué)的答案是一樣的。練習(xí)4〔09年希望杯〕人的頭發(fā)平均有12萬根。假設(shè)最多不超過20萬根。13億人中至少有多少人的頭發(fā)根數(shù)相同？分析：從問題出發(fā)，抽屜就是頭發(fā)根數(shù)。頭發(fā)根數(shù)最多不超20萬，那么抽屜數(shù)為20萬。物品為13億人。，由抽屜原理2，至少有6500人的頭發(fā)根數(shù)相同。抽屜原理的逆應(yīng)用練習(xí)5〔2003年希望杯〕新年晚會(huì)上，老師讓每個(gè)同學(xué)從一個(gè)裝有許多玻璃球的口袋中摸兩個(gè)球，這些球給人的手感相同。只有紅、黃、白、藍(lán)、綠五色之分〔摸時(shí)看不到顏色〕，結(jié)果發(fā)現(xiàn)總有兩個(gè)人取的球相同，由此可知，參加取球的至少有多少人？分析：取兩個(gè)球，顏色搭配有15種可能。15個(gè)抽屜，此題中物品即為取球的人。物品數(shù)至少為個(gè)。拓展有三種圖書：科技書、文藝書、故事書，每位同學(xué)可任借兩本，問至少多少位同學(xué)借書，才能保證其中必有4人借的書類型相同？分析：抽屜就是借的兩本書的組合，共有6種。為保證必有4人借的書類型相同，物品數(shù)〔也就是此題中的人數(shù)〕至少為人?？偨Y(jié)：結(jié)論為總結(jié)：結(jié)論為“總有a個(gè)物品在一個(gè)抽屜里〞時(shí)〔a不少于2〕，物品數(shù)至少=〔a-1〕×抽屜數(shù)+1。這是因?yàn)閷個(gè)物品放入n個(gè)抽屜中時(shí)，當(dāng)總有a個(gè)物品在一個(gè)抽屜中時(shí)，最不利情形就是平均分，抽屜中的物品數(shù)最多為a，其它抽屜中均有〔a-1〕個(gè)物品。此時(shí)就是滿足結(jié)論的物品數(shù)最少的情形：物品數(shù)=〔a-1〕×抽屜數(shù)+1。練習(xí)6幼兒園小朋友分200塊餅干，無論怎么分都有人至少分到8塊餅干，這群小朋友至多有多少名？分析：200為物品數(shù)，小朋友為抽屜。結(jié)論為“無論怎么分都有人至少分到8塊餅干〞。根據(jù)抽屜原理2，把小朋友的人數(shù)設(shè)為n，那么，。要求的最大值。當(dāng)最小時(shí)，最大。取，，整數(shù)局部為28，所以這群小朋友至多有28名?？偨Y(jié)：當(dāng)結(jié)論為總結(jié)：當(dāng)結(jié)論為“總有a個(gè)物品在同一個(gè)抽屜中〞時(shí)〔a不少于2〕，抽屜數(shù)至多=〔物品總數(shù)-1〕÷〔a-1〕的整數(shù)局部。最不利原那么練習(xí)7口袋中有三種顏色的筷子各10根，問：至少取多少根才能保證三種顏色都能取到？至少取多少根才能保證有2雙顏色不同的筷子？至少取多少根才能保證有2雙顏色相同的筷子？分析：〔1〕最糟糕的情形就是兩種顏色的都取完了，還沒有取到第三種顏色的。這時(shí)只要再取一根就能湊足三種顏色，所以至少取根?！?〕最糟糕的情形就是其中一種顏色的筷子取出來一甩，其它兩種顏色筷子各取了1根，這時(shí)只要再取一根就能湊出兩雙顏色