四年級秋季班第五講-簡單抽屜原理、最不利原則教學內(nèi)容

1、四年級秋季班第五講-簡單抽屜原理、最不利原則精品文檔第五講簡單抽屜原理、最不利原則知識框架認識一一抽屜原理解決的是存在杵問題操作一一構(gòu)造抽屜的方法Z從問題出發(fā)，相同的即為抽屜: 從數(shù)量關系出發(fā)；少的就是抽屜演練一一抽屜原理的逆向應用最不利原則最糟的情形就能保i止完成11標一、對抽屜原理兩個版本的認識抽屜原理1:將n+1個物品任意放到n個抽屜中，那么至少有一個抽屜中的物品不少于2件。n），（1）當m是n的整數(shù)倍時，那么至少有一個抽屜中的物品件數(shù) 是不少于m n件；（2）當m不是n的整數(shù)倍時，那么至少有一個抽屜中的物品件 數(shù)是不少于m n+1件。注：若mn =ab,那么就說mn=a ,也就是只要商

2、，余數(shù)不 要了。稱這個過程為取整。原理要點：（1）物品數(shù)比抽屜數(shù)多，抽屜原理1的情形包含于這個原理中；（2）解決的是抽屜的存在性；（3） 在解題時，遇到“有一個抽屜中的物品數(shù)不少于A件”，其 中A2時，應使用抽屜原理2。（4） 原理的結(jié)論也可以理解為：“總有不少于m n件（或m n +1件）物品在同一個抽屜中?！毕嗤募礊椤俺閷稀?。 原理講解：最不利的情形就是“平均分”，這樣每個抽屜中的物品數(shù)都不太 多都是m n個。若mn有余數(shù)，那么多出來的余數(shù)個物品也按照 最不利的情形來分配，這樣就能保證抽屜中的物品盡量地少。也就是說這余數(shù)個物品也平均地往抽屜中放，這樣有的抽屜會再放入一 個物品，而有的就分

3、不到，那么至少會有一個抽屜中的物品數(shù)不少 于m n+1個。這也解釋了物品數(shù)是不少于m n+1 ,而不是“不少 于m n+余數(shù)”。二、如何構(gòu)造抽屜1. 袋中取球問題練習1在一個口袋中有紅色、黃色、藍色球若干個，小聰明和其它 六個小朋友一起做游戲，每人可以從口袋中任意取出 2個球，那么 不管怎么挑選，總有兩個小朋友取出的兩個球的顏色完全一樣。 分析：（方法1）從問題出發(fā)?！翱傆袃蓚€小朋友取出的兩個球的顏色完全一 樣”，相同的是“取出的兩個球的顏色搭配”，這就是“抽屜”。取出的兩個球的顏 色，可能的情況有如下六種：紅紅、黃黃、藍藍，紅藍、紅黃、藍黃。也就是 說有6個抽屜。小聰明和其它6個小朋友一起做

4、游戲，共7人，也就是有7個 物品。物品數(shù)比抽屜數(shù)多1,根據(jù)抽屜原理1,總有2個小朋友取出的兩個球的 顏色完全一樣。（方法2）從條件出發(fā)。每人從口袋中任意取出2個球，取出的顏色搭配可能 有6種情形，取球的共有7個小朋友。小朋友數(shù)比顏色搭配數(shù)多1,那么7小 朋友是“物品”，6種顏色搭配是“抽屜”。根據(jù)抽屜原理1,總有兩個小朋友取出 的兩個球的顏色搭配相同。拓展口袋中放有足夠多的紅、白、藍三種顏色的球，現(xiàn)有31人輪流從袋子中取球，每人各取3個。證明：至少有4人取出球的顏色一樣。分析：類似練習1,取出球的顏色搭配是抽屜。搭配可能有：紅紅白、紅紅藍、藍藍紅、藍藍白、白白紅、白白藍、紅白藍，紅紅紅、白白白

5、、藍藍藍，共10種。也就是說有10個抽屜。31個人看成是物品。31 10 3 1 ,那么31 1013 14。根據(jù)抽屜原理2,至少有4人取出球的顏色是一樣的。總結(jié)：構(gòu)造抽屜的兩種方法：（1）從問題出發(fā)，相同的就是“抽屜”；（2）從數(shù)量關系出發(fā)，多的是“物品”，少的是“抽屜”。2. 數(shù)的整除性與抽屜原理余數(shù)的性質(zhì):（1）余數(shù)相同，差無余數(shù)。也就是說，兩個數(shù)除以同一個數(shù)得到的余數(shù)相同，那么這兩個數(shù)的差再去除以這同一個數(shù)時沒有余數(shù)。例：12 5和32 5的余數(shù)都是2,那么（32 12）5沒有余數(shù)。（2）余數(shù)的和等于和的余數(shù)。也就是說，幾個數(shù)除以同一個數(shù)得到的余數(shù)相加所得的和再除以同一個數(shù)得到的余數(shù)，

6、等于原本幾個數(shù)的和除以同一個數(shù)所得的余數(shù)。例：12 5的余數(shù)是2，14 5的余數(shù)是4，2 4 6，6 5的余數(shù)是1 ；（12 14） 5的余數(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。那么

7、可能出現(xiàn)兩種情形：（1）每個抽屜中都 至少有一個數(shù)。這樣，每個抽屜中取出一個數(shù)，這三個數(shù)的余數(shù)分別是0,1,2.，那么余數(shù)的和為0 123 ,除以3沒有余數(shù)，那么取出的這三個數(shù)的和除以3也沒有余數(shù)。（2）有一個抽屜中有不少于3個數(shù)。從這樣的抽屜中取出3個 數(shù)，這三個數(shù)的余數(shù)相同，那么余數(shù)的和是 3余數(shù)，除以3沒有余數(shù)，那么取 出的這三個數(shù)的和除以3也沒有余數(shù)。總結(jié)：題目中出現(xiàn)“幾個數(shù)得和（或差）是某數(shù)的倍數(shù)”時，就是數(shù)的整除性結(jié)合了抽屜原理，余數(shù)做抽屜。三、抽屜原理的應用1、 求抽屜中物品至多數(shù)練習3 17名同學參加一次考試，考試題是三道判斷題（答案只有對錯之分），每名同學都在答題紙上依次寫下

8、三道題的答案。請問至少有幾名同學的答案是 一樣的？分析：從問題出發(fā)找抽屜，相同的是答案，這就是抽屜。求抽屜數(shù)時可用乘法原理：每一道題都有2種答案，所以三道題的答案有2 2 2 8種，即有8個抽屜。物品為17名同學。17 821 ,由抽屜原理2,至少有2 1 3名同學的答案是一樣的。練習4 （09年希望杯）人的頭發(fā)平均有12萬根。假設最多不超過20萬根。13 億人中至少有多少人的頭發(fā)根數(shù)相同？分析：從問題出發(fā)，抽屜就是頭發(fā)根數(shù)。頭發(fā)根數(shù)最多不超20萬，那么抽屜數(shù)為20萬。物品為13億人。1300000000 200000 6500 ,由抽屜原理2,至少 有6500人的頭發(fā)根數(shù)相同。2、抽屜原理的

9、逆應用練習5（2003年希望杯）新年晚會上，老師讓每個同學從一個裝有許多玻璃球 的口袋中摸兩個球，這些球給人的手感相同。只有紅、黃、白、藍、綠五色之 分（摸時看不到顏色），結(jié)果發(fā)現(xiàn)總有兩個人取的球相同，由此可知，參加取 球的至少有多少人？分析：取兩個球，顏色搭配有15種可能。15個抽屜，本題中物品即為取球的人。物品數(shù)至少為15 1 16個。拓展有三種圖書：科技書、文藝書、故事書，每位同學可任借兩本，問至少多少位同學借書，才能保證其中必有 4人借的書類型相同？分析：抽屜就是借的兩本書的組合，共有 6種。為保證必有4人借的書類型相 同，物品數(shù)（也就是本題中的人數(shù)）至少為 3 6 1 19人?？偨Y(jié)：

10、結(jié)論為“總有a個物品在一個抽屜里”時（a不少于2），物品數(shù)至少=（a-1）抽屜數(shù)+1。J這是因為將m個物品放入n個抽屜中時，當總有a個物品在一個抽屜中時，最一丿不利情形就是平均分，抽屜中的物品數(shù)最多為a,其它抽屜中均有（a-1 ）個物品。此時就是滿足結(jié)論的物品數(shù)最少的情形：物品數(shù)=（a-1）抽屜數(shù)+1。練習6幼兒園小朋友分200塊餅干，無論怎么分都有人至少分到 8塊餅干，這 群小朋友至多有多少名？分析：200為物品數(shù)，小朋友為抽屜。結(jié)論為“無論怎么分都有人至少分到 8塊 餅干”。根據(jù)抽屜原理2,把小朋友的人數(shù)設為n,那么200（8 1） n k，k 1。要求n的最大值。當k最小時，n最大。取k

11、 1，n 199 7 ,整數(shù)部分 為28,所以這群小朋友至多有28名。（ 總結(jié)：當結(jié)論為“總有a個物品在同一個抽屜中”時（a不少于2）,抽屜數(shù)至多=（物品總數(shù)-1）（a-1）的整數(shù)部分。四、最不利原則練習7 口袋中有三種顏色的筷子各10根，問：（1）至少取多少根才能保證三種顏色都能取到？（2）至少取多少根才能保證有2雙顏色不同的筷子？（3）至少取多少根才能保證有2雙顏色相同的筷子？分析：（1最糟糕的情形就是兩種顏色的都取完了，還沒有取到第三種顏色 的。這時只要再取一根就能湊足三種顏色，所以至少取 10 10 1 21根。（2）最糟糕的情形就是其中一種顏色的筷子取出來一甩，其它兩種顏色筷子各取了 1根，這時只要再取一根就能湊出兩雙顏色不同的，所