抽屜原理有時(shí)也被稱為鴿巢原理(“如果有五個(gè)鴿子籠,養(yǎng)鴿人養(yǎng)了6只鴿子,那么當(dāng)鴿子飛回籠中后,至少有一個(gè)籠子中裝有2只鴿子”)。它是德國數(shù)學(xué)家狄利克雷首先明確的提出來并用以證明一些數(shù)論中的問題,因此,也稱為狄利克雷原理。它是組合數(shù)學(xué)中一個(gè)重要的原理。
假設(shè)有3個(gè)蘋果放入2個(gè)抽屜中,則必然有一個(gè)抽屜中有2個(gè)蘋果,她的一般模型可以表述為:
第一抽屜原理:把(mn+1)個(gè)物體放入n個(gè)抽屜中,其中必有一個(gè)抽屜中至少有(m+1)個(gè)物體。
若把3個(gè)蘋果放入4個(gè)抽屜中,則必然有一個(gè)抽屜空著,她的一般模型可以表述為:
第二抽屜原理:把(mn-1)個(gè)物體放入n個(gè)抽屜中,其中必有一個(gè)抽屜中至多有(m—1)個(gè)物體。
制造抽屜是運(yùn)用原則的一大關(guān)鍵
例1、一副撲克牌有四種花色,每種花色各有13張,現(xiàn)在從中任意抽牌。問最少抽幾張牌,才能保證有4張牌是同一種花色的?
A.12 B.13
C.15 D.16
【解析】根據(jù)抽屜原理,當(dāng)每次取出4張牌時(shí),則至少可以保障每種花色一樣一張,按此類推,當(dāng)取出12張牌時(shí),則至少可以保障每種花色一樣三張,所以當(dāng)抽取第13張牌時(shí),無論是什么花色,都可以至少保障有4張牌是同一種花色,選B。
例2、從1、2、3、4……、12這12個(gè)自然數(shù)中,至少任選幾個(gè),就可以保證其中一定包括兩個(gè)數(shù),他們的差是7?
A.7 B.10 C.9 D.8
【解析】在這12個(gè)自然數(shù)中,差是7的自然樹有以下5對:{12,5}{11,4}{10,3}{9,2}{8,1}。另外,還有2個(gè)不能配對的數(shù)是{6}{7}。可構(gòu)造抽屜原理,共構(gòu)造了7個(gè)抽屜。只要有兩個(gè)數(shù)是取自同一個(gè)抽屜,那么它們的差就等于7。這7個(gè)抽屜可以表示為{12,5}{11,4}{10,3}{9,2}{8,1}{6}{7},顯然從7個(gè)抽屜中取8個(gè)數(shù),則一定可以使有兩個(gè)數(shù)字來源于同一個(gè)抽屜,也即作差為7,所以選擇D。
例3、有紅、黃、藍(lán)、白珠子各10粒,裝在一只袋子里,為了保證摸出的珠子有兩粒顏色相同,應(yīng)至少摸出幾粒?()
A. 3 B. 4 C. 5 D. 6
【解析】這是一道典型的抽屜原理,只不過比上面舉的例子復(fù)雜一些,仔細(xì)分析其實(shí)并不難。解這種題時(shí),要從最壞的情況考慮,所謂的最不利原則,假定摸出的前4粒都不同色,則再摸出的1粒(第5粒)一定可以保證可以和前面中的一粒同色。因此選C。
傳統(tǒng)的解抽屜原理的方法是找兩個(gè)關(guān)鍵詞,“保證”和“最少”。
保證:5粒可以保證始終有兩粒同色,如少于5粒(比如4粒),我們?nèi)〖t、黃、藍(lán)、白各一個(gè),就不能“保證”,所以“保證”指的是要一定沒有意外。
最?。翰荒苋〈笥?的,如為6,那么5也能“保證”,就為5。
例4、從一副完整的撲克牌中至少抽出( )張牌。才能保證至少 6 張牌的花色相同。
A. 21 B. 22
C. 23 D. 24
解析:2+5*4+1=23
2012年山東公務(wù)員考試復(fù)習(xí)用書可參考《2012年山東公務(wù)員考試一本通》。