六年級奧數(shù)-第九講.復雜抽屜原理.教師版

1、精選優(yōu)質文檔-傾情為你奉上第九講 復雜抽屜原理內容概述運用抽屜原理求解的較為復雜的組合計算與證明問題這里不僅“抽屜”與“蘋果”需要恰當?shù)卦O計與選取，而且有時還應構造出達到最佳狀態(tài)的例子典型問題1從1，2，3，1988，1989這些自然數(shù)中，最多可以取出多少個數(shù)，使得其中每兩個數(shù)的差不等于4？ 【分析與解】1，2，3，4，9，10，1l，12，17，18，19，20，25， 這些數(shù)中任何兩個數(shù)的差都不為4，這些數(shù)是每8個連續(xù)的數(shù)中選取前4個連續(xù)的數(shù) 有1989÷8=2485，所以最多可以選248×4+4=996個數(shù) 評注：對于這類問題，一種方法是先盡可能的多選擇，然后再找出這

2、些數(shù)的規(guī)律，再計算出最多可以選出多少個.2從1至1993這1993個自然數(shù)中最多能取出多少個數(shù)，使得其中任意的兩數(shù)都不連續(xù)且差不等于4？ 【分析與解】1，3，6，8，11，13，16，18，21， 這些數(shù)中任何兩個數(shù)不連續(xù)且差不等于4，這些數(shù)是每5個連續(xù)的數(shù)中選擇第1、3個數(shù) 1993÷5=3983.所以最多可以選398×2+2=798個數(shù) 評注：當然還可以是1，4，6，9，11，14，16，19，21， 這些數(shù)滿足條件，是每5個連續(xù)的數(shù)中選擇第1、4個數(shù)但是此時最多只能選出398×2+l=797個數(shù)3. 從1，2，3，4，5，6，7，8，9，10，11，12中最

3、多能選出幾個數(shù)，使得在選出的數(shù)中，每一個數(shù)都不是另一個數(shù)的2倍? 【分析與解】 方法一：直接從1開始選1，3，4，5，7，9，11，12，這樣可以選出8個數(shù)； 而從2開始選2，3，5，7，8，9，11，12，這樣也是可以選出8個數(shù) 3包含在組內，因此只用考慮這兩種情況即可 所以，在滿足題意情況下，最多可以選出8個數(shù) 方法二：我們知道選多少個奇數(shù)均滿足，有1，3，5，7，9，11均為奇數(shù)，并且有偶數(shù)中4的倍數(shù)，但不是8的倍數(shù)的也滿足，有4，12是這樣的數(shù)所以，在滿足題意情況下最多可以選出8個數(shù)4從1，3，5，7，97，99中最多可以選出多少個數(shù)，使得選出的數(shù)中，每一個數(shù)都不是另一個數(shù)的倍數(shù)? 【

4、分析與解】 方法一：因為均是奇數(shù)，所以如果存在倍數(shù)關系，那么也一定是3、5、7等奇數(shù)倍. 3×33：99，于是從35開始，199的奇數(shù)中沒有一個是3599的奇數(shù)倍(不包括1倍)，所以選出35，37，39，99這些奇數(shù)即可 共可選出33個數(shù)，使得選出的數(shù)中，每一個數(shù)都不是另一個數(shù)的倍數(shù) 方法二：利用3的若干次冪與質數(shù)的乘積對這50個奇數(shù)分組 (1，3，9，27，81)，(5，15，45)，(7，21，63)，(11，33)，(13，39)，(17，51)，(19，57)，(23，69)，(25，75)，(29，87)，(31，93)，(35)，(37)，(41)，(43)，(97)共3

5、3組 前11組，每組內任意兩個數(shù)都存在倍數(shù)關系，所以每組內最多只能選擇一個數(shù) 即最多可以選出33個數(shù)，使得選出的數(shù)中，每一個數(shù)都不是另一個數(shù)的倍數(shù) 評注：12n個自然數(shù)中，任意取出n+1個數(shù)，則其中必定有兩個數(shù)，它們一個是另一個的整數(shù)倍； 從2，3，2n+1中任取n+2個數(shù)，必有兩個數(shù)，它們一個是另一個的整數(shù)倍； 從1，2，33n中任取2n+1個數(shù)，則其中必有兩個數(shù)，它們中一個是另一個的整數(shù)倍，且至少是3倍；從1，2，3， mn中任取(m-1)n+1個數(shù)，則其中必有兩個數(shù)，它們中一個是另一個的整數(shù)倍，且至少是m倍(m、n為正整數(shù)).5證明：任給12個不同的兩位數(shù)，其中一定存在著這樣的兩個數(shù)，它

6、們的差是個位與十位數(shù)字相同的兩位數(shù) 【分析與解】 因為兩個不同的兩位數(shù)相減得到的差不可能為三位或三位以上的數(shù)如果這個差是1l的倍數(shù)，那么一定有這個差的個位與十位數(shù)字相同 兩個數(shù)的差除以1l的余數(shù)有0、1、2、3、10這11種情況將這11種情況視為11個抽屜 將12個數(shù)視為12個蘋果，那么必定有兩個蘋果在同一抽屜，也就是說有兩個數(shù)除以11的余數(shù)相同，那么它們的差一定是11的倍數(shù) 而兩個兩位數(shù)的差一定是一個兩位數(shù)，如果這個差是11的倍數(shù)，那么就有個數(shù)與十位數(shù)字相等問題得證 評注：抽屜原理一：將n+1個元素放到n個抽屜中去，則無論怎么放，必定有一個抽屜至少有兩個元素 抽屜原理二：將nr+1個元素放到

7、n個抽屜中去，則無論怎么放，必定有一個抽屜至少有r+1個元素抽屜原理三：將m個元素放到n個抽屜中去(mn)，則無論怎么放，必定有一個抽屜至少有個元素6從1，2，3，49，50這50個數(shù)中取出若干個數(shù)，使其中任意兩個數(shù)的和都不能被7整除，則最多能取出多少個數(shù)? 【分析與解】 利用除以7的余數(shù)分類： 余0：(7，14，21，28，35，42，49)； 余1：(1，8，15，22，29，36，43，50)； 余2：(2，9，16，23，30，37，44)； 余3：(3，10，17，24，31，38，45)； 余4：(4，11，18，25，32，39，46)； 余5：(5，12，19，26，33，40

8、，47)； 余6：(6，13，20，27，34，41，48) 第一組內的數(shù)最多只能取1個；如果取第二組，那么不能取第七組內任何一個數(shù)；取第三組，不能取第六組內任何一個數(shù)；取第四組，不能取第五組內任意一個數(shù)第二、三、四、五、六、七組分別有8、7、7、7、7、7個數(shù)，所以最多可以取1+8+7+7=23個數(shù)7從1，2，3，99，100這100個數(shù)中任意選出51個數(shù)證明： (1)在這51個數(shù)中，一定有兩個數(shù)互質； (2)在這51個數(shù)中，一定有兩個數(shù)的差等于50； (3)在這51個數(shù)中，一定存在9個數(shù)，它們的最大公約數(shù)大于1 【分析與解】 (1)我們將1100分成(1，2)，(3，4)，(5，6)，(7

9、，8)，(99，100)這50組，每組內的數(shù)相鄰而相鄰的兩個自然數(shù)互質 將這50組數(shù)作為50個抽屜，同一個抽屜內的兩個數(shù)互質 而現(xiàn)在51個數(shù)，放進50個抽屜，則必定有兩個數(shù)在同一抽屜，于是這兩個數(shù)互質問題得證 (2)我們將1100分成(1，51)，(2，52)，(3，53)，(40，90)，(50，100)這50組，每組內的數(shù)相差50將這50組數(shù)視為抽屜，則現(xiàn)在有51個數(shù)放進50個抽屜內，則必定有2個數(shù)在同一抽屜，那么這兩個數(shù)的差為50問題得證 (3)我們將1100按2的倍數(shù)、3的奇數(shù)倍、既不是2又不是3的倍數(shù)的情況分組，有(2，4，6，8，98，100)，(3，9，15，21，27，93，9

10、9)，(5，7，11，13，17，19，23，95，97)這三組第一、二、三組分別有50、17、33個元素最不利的情況下，51個數(shù)中有33個元素在第三組，那么剩下的18個數(shù)分到第一、二兩組內，那么至少有9個數(shù)在同一組所以這9個數(shù)的最大公約數(shù)為2或3或它們的倍數(shù)，顯然大于1問題得證8求證：可以找到一個各位數(shù)字都是4的自然數(shù)，它是1996的倍數(shù) 【分析與解】注意到1996=4×499； 對于l，1l，11l， 中必定有兩個數(shù)關于499同余 于是(mod 499)(m>n) 有-=，所以499 ，因為(499，)=l，所以499；于是有(499×4)（4），即1996 于是

11、，就找到這樣的全部都是由4組成的數(shù)字，是1996的倍數(shù) 評注：、可整除不合2，5因數(shù)的任何整數(shù)； 、整除不含因數(shù)5(因數(shù)2分別只能含1，2，2，3個)的任何整數(shù)； 整除不含因數(shù)2(因數(shù)5只能含1個)的任何整數(shù)9有49個小孩，每人胸前有一個號碼，號碼從1到49各不相同現(xiàn)在請你挑選若干個小孩，排成一個圓圈，使任何相鄰兩個小孩的號碼數(shù)的乘積小于100，那么你最多能挑選出多少個孩子? 【分析與解】 將1至49中相乘小于100的兩個數(shù)，按被乘數(shù)分成9組，如下： (1×2)、(1×3)、(1×4)、(1×49)； (2×3)、(2×4)、(2&#

12、215;5)、(2×49)； (8×9)、(8×10)、(8 ×11)、(8×12)； (9×10)、(9×11). 因為每個數(shù)只能與左右兩個數(shù)相乘，也就是每個數(shù)作為被乘數(shù)或乘數(shù)最多兩次，所以每一組中最多會有兩對數(shù)出現(xiàn)在圓圈中，最多可以取出18個數(shù)對，共18 ×2=36次，但是每個數(shù)都出現(xiàn)兩次，故出現(xiàn)了18個數(shù) 例如：(10×9)、(9×11)、(1×8)、(8×12)、(12×7)、(7×13)、(13×6)、(6×14)、(14&#

13、215;5)、(5×15)、(15×4)、(4 ×16)、(16 X 3)、(3×17)、(17×2)、(2×18)、(18 ×1)、(1×10)共出現(xiàn)l18號，共18個孩子 若隨意選取出19個孩子，那么共有19個號碼，由于每個號碼數(shù)要與旁邊兩數(shù)分別相乘，則會形成19個相乘的數(shù)對 那么在9組中取出19個數(shù)時，有19=9×2+1，由抽屜原則知，必有三個數(shù)對落入同一組中，這樣某個數(shù)字會在數(shù)對中出現(xiàn)三次(或三次以上)，由分析知，這是不允許的故最多挑出18個孩子10. 在邊長為1的正方形內隨意放進9個點，證明其中

14、必有3個點構成的三角形的面積不大于 【分析與解】 如下圖，把正方形分成四個形狀相同、大小相等的正方形9個點任意放人這四個正方形中 根據抽屜原理，多于2×4個點放入四個長方形中，至少有2+1個點(即3個點)落在某一個正方形之內現(xiàn)在，特別取出這個正方形來加以討論 把落在這正方形中的三點組成的三角形記為ABC，其面積不超過小正方形面積的，所以其面積不超過這樣就得到了需要證明的結論 評注：在邊長為1的等邊三角形中有個點，這個點中一定有距離不大于的兩點； 在邊長為l的等邊三角形內有個點，這個點中一定有距離小于的兩點 已知平行四邊形中，其面積為l，現(xiàn)有個點，則必定有三點組成的三角形，其面積不大于

15、； 已知三角形中，其面積為1，現(xiàn)有個點，則必定有三點組成的三角形，其面積不大于11某班有16名學生，每個月教師把學生分成兩個小組問最少要經過幾個月，才能使該班的任意兩個學生總有某個月份是分在不同的小組里? 【分析與解】經過第一個月，將16個學生分成兩組，至少有8個學生分在同一組，下面只考慮這8個學生 經過第二個月，將這8個學生分成兩組，至少有4個學生是分在同一組，下面只考慮這4個學生 經過第三個月，將這4個學生分成兩組，至少有2個學生仍分在同一組，這說明只經過3個月是無法滿足題目要求的 如果經過四個月，將每個月都一直保持同組的學生一分為二，放人兩個組，那么第一個月保持同組的人數(shù)為16÷

16、;2=8人，第二個月保持同組的人數(shù)為8÷2=4人，第三個月保持同組人數(shù)為4÷2=2人，這說明，照此分法，不會有2個人一直保持在同一組內，即滿足題目要求，故最少要經過4個月12上體育課時，21名男、女學生排成3行7列的隊形做操老師是否總能從隊形中劃出一個長方形，使得站在這個長方形4個角上的學生或者都是男生，或者都是女生?如果能，請說明理由；如果不能，請舉出實例 【分析與解】 因為只有男生或女生兩種情況，所以第1行的7個位置中至少有4個位置同性別 為了確定起見，不妨設前4個位置同是男生，如果第二行的前4個位置有2名男生，那么4個角同是男生的情況已經存在，所以我們假定第二行的前4

17、個位置中至少有3名女生，不妨假定前3個是女生 又第三行的前3個位置中至少有2個位置是同性別學生，當是2名男生時與第一行構成一個四角同性別的矩形，當有2名女生時與第二行構成四角同性別的矩形 所以，不論如何，總能從隊形中劃出一個長方形，使得站在這個長方形4個角上的學生同性別問題得證138個學生解8道題目 (1)若每道題至少被5人解出，請說明可以找到兩個學生，每道題至少被過兩個學生中的一個解出 (2)如果每道題只有4個學生解出，那么(1)的結論一般不成立試構造一個例子說明這點. 【分析與解】 (1)先設每道題被一人解出稱為一次，那么8道題目至少共解出58=40次，分到8個學生身上，至少有一個學生解出

18、了5次或5次以上題目，即這個學生至少解出5道題，稱這個學生為4，我們討論以下4種可能： 第一種可能：若4只解出5道題，則另3道題應由其他7個人解出，而3道題至少共被解出35=15次，分到7個學生身上，至少有一名同學解出了3次或3次以上的題目(15=27+1，由抽屜原則便知)由于只有3道題，那么這3道題被一名學生全部解出，記這名同學為B 那么，每道題至少被A、B兩名同學中某人解出 第二種可能：若A解出6道題，則另2道題應由另7人解出，而2道題至少共被解出2×5=10次，分到7個同學身上，至少有一名同學解出2次或2次以上的題目(10=17+3，由抽屜原則便知)與l第一種可能I同理，這兩道

19、題必被一名學生全部解出，記這名同學為C 那么，每道題目至少被A、C學生中一人解出 第三種可能：若A解出7道題目，則另一題必由另一人解出，記此人為D那么，每道題目至少被A、D兩名學生中一人解出 第四種可能：若A解出8道題目，則隨意找一名學生，記為E，那么，每道題目至少被A、E兩名學生中一人解出，所以問題(1)得證 (2)類似問題(1)中的想法，題目共被解出84=32次，可以使每名學生都解出4次，那么每人解出4道題 隨便找一名學生，必有4道未被他解出，這4道題共被7名同學解出44=16次，由于16=2×7+2，可以使每名同學解出題目不超過3道，這樣就無法找到兩名學生，使每道題目至少被其中

20、一人解出 具體構造如下表，其中漢字代表題號，數(shù)字代表學生，打代表該位置對應的題目被該位置對應的學生解出14時鐘的表盤上按標準的方式標著1，2，3，11，12這12個數(shù)，在其上任意做n個的扇形，每一個都恰好覆蓋4個數(shù)，每兩個覆蓋的數(shù)不全相同如果從這任做的n個扇形中總能恰好取出3個覆蓋整個鐘面的全部12個數(shù)，求n的最小值 【分析與解】 如下圖，只要從某個數(shù)字對應的位置開始，做出的扇形，一定能覆蓋4個數(shù) 從最不利的情況出發(fā)，n個扇形中最大程度的重疊，需做(12，1，2，3)，(1，2，3，4)，(2，3，4，5)，(3，4，5，6)，(4，5，6，7)，(5，6，7，8)，(6，7，8，9)，(7，8，9，10)，(8，9，