四年級秋季班第五講-簡單抽屜原理、最不利原則

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