抽屜原理
一、 知識(shí)要點(diǎn)
抽屜原理又稱鴿巢原理,它是組合數(shù)學(xué)的一個(gè)基本原理,最先是由德國(guó)數(shù)學(xué)家狹利克雷明確地提出來(lái)的,因此,也稱為狹利克雷原理.
把3個(gè)蘋果放進(jìn)2個(gè)抽屜里,一定有一個(gè)抽屜里放了2個(gè)或2個(gè)以上的蘋果.這個(gè)人所皆知的常識(shí)就是抽屜原理在日常生活中的體現(xiàn).用它可以解決一些相當(dāng)復(fù)雜甚至無(wú)從下手的問(wèn)題.
原理1：把n+1個(gè)元素分成n類,不管怎么分,則一定有一類中有2個(gè)或2個(gè)以上的元素.
原理2：把m個(gè)元素任意放入n（n＜m＝個(gè)集合,則一定有一個(gè)集合呈至少要有k個(gè)元素.
其中 k＝ （當(dāng)n能整除m時(shí)）
〔 〕＋1 （當(dāng)n不能整除m時(shí)）
（〔 〕表示不大于 的最大整數(shù),即 的整數(shù)部分）
原理3：把無(wú)窮多個(gè)元素放入有限個(gè)集合里,則一定有一個(gè)集合里含有無(wú)窮多個(gè)元素.
二、 應(yīng)用抽屜原理解題的步驟
第一步：分析題意.分清什么是“東西”,什么是“抽屜”,也就是什么作“東西”,什么可作“抽屜”.
第二步：制造抽屜.這個(gè)是關(guān)鍵的一步,這一步就是如何設(shè)計(jì)抽屜.根據(jù)題目條件和結(jié)論,結(jié)合有關(guān)的數(shù)學(xué)知識(shí),抓住最基本的數(shù)量關(guān)系,設(shè)計(jì)和確定解決問(wèn)題所需的抽屜及其個(gè)數(shù),為使用抽屜鋪平道路.
第三步：運(yùn)用抽屜原理.觀察題設(shè)條件,結(jié)合第二步,恰當(dāng)應(yīng)用各個(gè)原則或綜合運(yùn)用幾個(gè)原則,以求問(wèn)題之解決.
例1、 教室里有5名學(xué)生正在做作業(yè),今天只有數(shù)學(xué)、英語(yǔ)、語(yǔ)文、地理四科作業(yè)
求證：這5名學(xué)生中,至少有兩個(gè)人在做同一科作業(yè).
證明：將5名學(xué)生看作5個(gè)蘋果
將數(shù)學(xué)、英語(yǔ)、語(yǔ)文、地理作業(yè)各看成一個(gè)抽屜,共4個(gè)抽屜
由抽屜原理1,一定存在一個(gè)抽屜,在這個(gè)抽屜里至少有2個(gè)蘋果.
即至少有兩名學(xué)生在做同一科的作業(yè).
例2、 木箱里裝有紅色球3個(gè)、黃色球5個(gè)、藍(lán)色球7個(gè),若蒙眼去摸,為保證取出的球中有兩個(gè)球的顏色相同,則最少要取出多少個(gè)球?
把3種顏色看作3個(gè)抽屜
若要符合題意,則小球的數(shù)目必須大于3
大于3的最小數(shù)字是4
故至少取出4個(gè)小球才能符合要求
答：最少要取出4個(gè)球.
例3、 班上有50名學(xué)生,將書分給大家,至少要拿多少本,才能保證至少有一個(gè)學(xué)生能得到兩本或兩本以上的書.
把50名學(xué)生看作50個(gè)抽屜,把書看成蘋果
根據(jù)原理1,書的數(shù)目要比學(xué)生的人數(shù)多
即書至少需要50+1=51本
答：最少需要51本.
例4、 在一條長(zhǎng)100米的小路一旁植樹101棵,不管怎樣種,總有兩棵樹的距離不超過(guò)1米.
把這條小路分成每段1米長(zhǎng),共100段
每段看作是一個(gè)抽屜,共100個(gè)抽屜,把101棵樹看作是101個(gè)蘋果
于是101個(gè)蘋果放入100個(gè)抽屜中,至少有一個(gè)抽屜中有兩個(gè)蘋果
即至少有一段有兩棵或兩棵以上的樹
例5、 11名學(xué)生到老師家借書,老師是書房中有A、B、C、D四類書,每名學(xué)生最多可借兩本不同類的書,最少借一本
試證明：必有兩個(gè)學(xué)生所借的書的類型相同
證明：若學(xué)生只借一本書,則不同的類型有A、B、C、D四種
若學(xué)生借兩本不同類型的書,則不同的類型有AB、AC、AD、BC、BD、CD六種
共有10種類型
把這10種類型看作10個(gè)“抽屜”
把11個(gè)學(xué)生看作11個(gè)“蘋果”
如果誰(shuí)借哪種類型的書,就進(jìn)入哪個(gè)抽屜
由抽屜原理,至少有兩個(gè)學(xué)生,他們所借的書的類型相同
例6、 有50名運(yùn)動(dòng)員進(jìn)行某個(gè)項(xiàng)目的單循環(huán)賽,如果沒有平局,也沒有全勝
試證明：一定有兩個(gè)運(yùn)動(dòng)員積分相同
證明：設(shè)每勝一局得一分
由于沒有平局,也沒有全勝,則得分情況只有1、2、3……49,只有49種可能
以這49種可能得分的情況為49個(gè)抽屜
現(xiàn)有50名運(yùn)動(dòng)員得分
則一定有兩名運(yùn)動(dòng)員得分相同
例7、 體育用品倉(cāng)庫(kù)里有許多足球、排球和籃球,某班50名同學(xué)來(lái)倉(cāng)庫(kù)拿球,規(guī)定每個(gè)人至少拿1個(gè)球,至多拿2個(gè)球,問(wèn)至少有幾名同學(xué)所拿的球種類是一致的?
解題關(guān)鍵：利用抽屜原理2.
根據(jù)規(guī)定,多有同學(xué)拿球的配組方式共有以下9種：
｛足｝｛排｝｛藍(lán)｝｛足足｝｛排排｝｛藍(lán)藍(lán)｝｛足排｝｛足藍(lán)｝｛排藍(lán)｝
以這9種配組方式制造9個(gè)抽屜
將這50個(gè)同學(xué)看作蘋果
＝5.5……5
由抽屜原理2k＝〔 〕＋1可得,至少有6人,他們所拿的球類是完全