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

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

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

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

4、游戲，共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)，紅紅紅、白白白

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

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

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

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

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

10、結(jié)論為“總有a個(gè)物品在一個(gè)抽屜里”時(shí)（a不少于2），物品數(shù)至少=（a-1）抽屜數(shù)+1。J這是因?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塊餅干，無(wú)論怎么分都有人至少分到 8塊餅干，這 群小朋友至多有多少名？分析：200為物品數(shù)，小朋友為抽屜。結(jié)論為“無(wú)論怎么分都有人至少分到 8塊 餅干”。根據(jù)抽屜原理2,把小朋友的人數(shù)設(shè)為n,那么200（8 1） n k，k 1。要求n的最大值。當(dāng)k最小時(shí)，n最大。取k

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