淺談抽屜原理中抽屜的幾種構(gòu)造方法

郭健紅 林彬

摘 要：抽屜原理（鴿巢原理）是組合數(shù)學(xué)中一個(gè)重要的初等原理，在解決一某類存在性問題中具有廣泛應(yīng)用?？紤]到應(yīng)用抽屜原理證明時(shí)構(gòu)造抽屜的重要性，該文在簡(jiǎn)單地介紹抽屜原理（鴿巢原理）的基礎(chǔ)上，分別從等分區(qū)間，通過幾何圖形，利用余數(shù)，分組構(gòu)造等幾個(gè)方面對(duì)如何構(gòu)造抽屜，進(jìn)行了總結(jié)與概括，進(jìn)而應(yīng)用抽屜原理來解決某類存在性問題。

關(guān)鍵詞：組合數(shù)學(xué) 抽屜原理 存在性問題 構(gòu)造

中圖分類號(hào)：O29 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2012）12（a）-000-02

1 抽屜原理

抽屜原理又稱鴿巢原理，它是德國(guó)數(shù)學(xué)家狄利克雷首先明確的提出來并用以證明一些數(shù)論中的問題，因此，也稱為狄利克雷原則。它是組合數(shù)學(xué)中一個(gè)重要的原理。是一個(gè)及其初等而有應(yīng)用廣泛的數(shù)學(xué)原理。

定理1.1 抽屜原理（基本形式）：將n+1個(gè)物體放入到n個(gè)抽屜中，則至少有一個(gè)抽屜中的物品數(shù)不少于兩個(gè)。

以上定理不難推廣為：

定理1.2 第二抽屜原理（推廣形式）：把個(gè)物體放入標(biāo)號(hào)為的個(gè)抽屜中，則至少有一個(gè)標(biāo)號(hào)為i的抽屜中物品數(shù)不少于，。

根據(jù)以上定理結(jié)果，可得到以下結(jié)論。

推論1.1 將m個(gè)的元素按任一確定的方式分成個(gè)集合，則至少有一個(gè)集合中含有兩個(gè)或兩個(gè)以上的元素。

推論1.2 將個(gè)的元素按任一確定的方式分成n個(gè)集合，則至少有一個(gè)集合中元素個(gè)數(shù)不少于r個(gè)。

推論1.3 將m個(gè)的元素按任一確定的方式分成n個(gè)集合，則至少有一個(gè)集合中元素個(gè)數(shù)不少于個(gè)。其中為取整函數(shù)，下同。

推論1.4 將m個(gè)的元素按任一確定的方式分成n個(gè)集合，則至少有一個(gè)集合中元素個(gè)數(shù)不多于個(gè)。

以上結(jié)果均為有限形式的抽屜原理的有關(guān)結(jié)論，對(duì)于無限形式，有以下定理：

定理1.3 抽屜原理（無限形式）：無窮多個(gè)物體放到有限多只抽屜中，至少有一只抽屜放進(jìn)了無窮多個(gè)球。

以上諸定理及其推論在大部分組合數(shù)學(xué)教材中均有論及，限于篇幅有限，證明從略。

2 抽屜的構(gòu)造

抽屜原理的內(nèi)容簡(jiǎn)明樸素，易于接受，它在數(shù)學(xué)問題中有重要的作用。許多有關(guān)存在性的證明都可用它來解決。而在利用抽屜原理證明數(shù)學(xué)問題或者解決實(shí)際問題時(shí)，最關(guān)鍵是要確定哪些是“球”，哪些是“抽屜”。很多時(shí)候需要我們選取、制造“合適、恰當(dāng)”的抽屜?！昂线m”— 要求每個(gè)抽屜的“規(guī)格”是一樣的，因?yàn)槭前慈我夥绞椒胚M(jìn)元素的，每個(gè)抽屜放人元素的可能性是一樣的；“恰當(dāng)”— 抽屜的數(shù)目要少于元素的數(shù)目，且滿足所求的結(jié)論。以下通過實(shí)例，對(duì)如何構(gòu)造抽屜進(jìn)行簡(jiǎn)要分析說明。

2.1 等分區(qū)間構(gòu)造抽屜

所謂等分區(qū)間簡(jiǎn)單的說即是：如果在長(zhǎng)度為1的區(qū)間內(nèi)有多于n個(gè)的點(diǎn)，可考慮把區(qū)間n等分成n個(gè)子區(qū)間，這樣由抽屜原理可知，一定有兩點(diǎn)落在同一子區(qū)間，它們之間的距離不大于。這種構(gòu)造法常用于處理一些不等式的證明。對(duì)于給定了一定的長(zhǎng)度或區(qū)間并要證明不等式的問題，可以采用等分區(qū)間的構(gòu)造方法來構(gòu)造

抽屜。

例1 設(shè)x1，x2，…，xn全為實(shí)數(shù)，滿足，求證：對(duì)于任意的整數(shù)，存在不全為零的整數(shù)，使得，并且：

分析：由條件以及柯西不等式顯然有：

從而可以進(jìn)一步把區(qū)間等分成個(gè)小區(qū)間，構(gòu)造抽屜。

證明：由柯西不等式有：

所以：

因此，當(dāng)時(shí)，有

把區(qū)間分成個(gè)小區(qū)間，每個(gè)區(qū)間長(zhǎng)度為。而因?yàn)槊總€(gè)能取k個(gè)整數(shù)，所以一共有個(gè)整數(shù)。

根據(jù)抽屜原理，必存在某個(gè)小區(qū)間，其中至少有兩個(gè)整數(shù)，設(shè)它們分別為和，則有：

其中使得為整數(shù)，且。

證畢。

從上面例題不難發(fā)現(xiàn)，在等分區(qū)間的基礎(chǔ)上便很方便的構(gòu)造了抽屜，從而尋找到了證明不等式的一種非常特殊而又簡(jiǎn)易的方法，與通常的不等式的證明方法（構(gòu)造函數(shù)法，移位相減法）相比，等分區(qū)間構(gòu)造抽屜更簡(jiǎn)易，更容易被人接受。

2.2 通過幾何圖形構(gòu)造抽屜

很多實(shí)際問題或數(shù)學(xué)問題，通過轉(zhuǎn)化均可轉(zhuǎn)化為相關(guān)的幾何問題。而對(duì)于其中一類存在性問題，涉及到一個(gè)幾何圖形內(nèi)有若干點(diǎn)時(shí)，常?？梢园褕D形巧妙地分割成適當(dāng)?shù)牟糠?，然后用分割所得的小圖形作抽屜。這種分割一般符合一個(gè)“分劃”的定義，即抽屜間的元素既互不重復(fù)，也無遺漏；但有時(shí)根據(jù)解題需要，分割也可使得抽屜之間含有公共元素。

例2 設(shè)ABC為一等邊三角形，E是三邊上點(diǎn)的全體。對(duì)于每一個(gè)把E分成兩個(gè)不相交子集的劃分，問這兩個(gè)子集中是否至少有一個(gè)子集包含著一個(gè)直角三角形的三個(gè)頂點(diǎn)？

證明：如下圖，在邊BC、CA、AB上分別取三點(diǎn)P，Q，R，使

顯然△，，都是直角三角形。它們的銳角是30°及60°。

設(shè)，是的兩個(gè)非空子集，且

由抽屜原理可知，中至少有兩點(diǎn)屬于同一子集，不妨設(shè)。

如果邊上除之外還有屬于的點(diǎn)，那么結(jié)論已明。

設(shè)的點(diǎn)除之外全屬于，那么只要上有異于的點(diǎn)屬于，設(shè)在上的投影點(diǎn)為，則為直角三角形。

再設(shè)內(nèi)的每一點(diǎn)均不屬于，即除之外全屬于，特別，，于是，且為一直角三角形。從而命題得證。

圖1

上例通過分割圖形構(gòu)造抽屜。首先根據(jù)問題的要求把圖形進(jìn)行適當(dāng)?shù)姆指?，用這些分割成的圖形作為抽屜，再對(duì)已知點(diǎn)進(jìn)行分類，集中對(duì)某一個(gè)或幾個(gè)抽屜進(jìn)行討論，使問題得到解決。

2.3 利用余數(shù)構(gòu)造抽屜

在處理一類涉及自然數(shù)的存在性問題時(shí)，可以將自然數(shù)按照模n同余進(jìn)行分類，根據(jù)模n的值的不同，可以構(gòu)造n個(gè)抽屜（模n剩余類）。舉例來說，如果n=3，則可以將全體自然數(shù)N分為“余0類”、“余1類”、“余2類”3個(gè)抽屜。然再進(jìn)一步對(duì)問題進(jìn)行處理。

例3：求證對(duì)于平面上任意的不共線的9個(gè)整點(diǎn)，其中一定存在3個(gè)點(diǎn)，使得這三個(gè)點(diǎn)組成的三角形的重心也為整點(diǎn)。

分析：如果點(diǎn)，，滿足條件，即由此三點(diǎn)組成的三角形的重心

此處涉及到余數(shù)問題，所以可以按模3的剩余類進(jìn)行分類。

證明：設(shè)平面上的9個(gè)整點(diǎn)為，，令

則取值共有9種情況，即：

從而構(gòu)成了9個(gè)抽屜，每個(gè)點(diǎn)（也就是物品）根據(jù)的值放入相應(yīng)的抽屜中。

以下分兩種情況討論：（1）如果同一行或同一列的3個(gè)抽屜不空時(shí)，從每個(gè)抽屜中各選一個(gè)點(diǎn)，選出來的3個(gè)點(diǎn)即滿足要求。不妨以行為例，對(duì)于某一行抽屜中的3個(gè)類型的點(diǎn)，每個(gè)點(diǎn)的的分量除以3的余數(shù)是一樣的，而其的分量除以3的余數(shù)分別是0，1，2。所以不過是分量還是分量，3個(gè)余數(shù)之和都能被3整除，從而相應(yīng)的3個(gè)坐標(biāo)值之和能被3整除，即此3點(diǎn)組成的三角形的重心是整點(diǎn)。同理，從同一列的3個(gè)抽屜中各選一個(gè)點(diǎn)，選出來的3個(gè)點(diǎn)也滿足組成的三角形的重心是整點(diǎn)。（2）如果從不同行，不同列的3個(gè)抽屜中各選一個(gè)點(diǎn)時(shí)，選出的三個(gè)點(diǎn)組成的三角形的重心是整點(diǎn)。因?yàn)檫@是的3點(diǎn)的的分量除以3的余數(shù)分別是0，1，2，y的分量除以3的余數(shù)也為0，1，2，根據(jù)上面說明，顯然此三點(diǎn)組成的三角形的重心是整點(diǎn)。對(duì)于九個(gè)點(diǎn)，，如果某個(gè)抽屜中至少含有3個(gè)點(diǎn)，則此三個(gè)點(diǎn)組成的三角形的重心是整點(diǎn)。否則，每個(gè)抽屜中至多有兩個(gè)點(diǎn)。這樣此時(shí)至少某一行，或某一列，或不同行不同列的3個(gè)抽屜其中不空，那么，按照前面分析，從此3個(gè)抽屜中各選一點(diǎn)，則此三點(diǎn)組成的三角形的重心是整點(diǎn)。綜上，對(duì)于平面上任意的不共線的9個(gè)整點(diǎn)，一定可以選出其中3個(gè)點(diǎn)，使得這三個(gè)點(diǎn)組成的三角形的重心也為整點(diǎn)。

證畢。

另外，特別地，作為按照余數(shù)分組的特例，可以按照奇數(shù)與偶數(shù)（除以2余數(shù)分別為1和0）來進(jìn)行分組構(gòu)造抽屜。

2.4 利用分組構(gòu)造抽屜

利用這種構(gòu)造法解題，確定分組的“對(duì)象”很關(guān)鍵。確定了“對(duì)象”之后，其個(gè)數(shù)相對(duì)于“球”的個(gè)數(shù)而言，又往往顯得太多。只有把這些“對(duì)象”分成適當(dāng)數(shù)量的組（即抽屜）后，才能應(yīng)用抽屜原理。例4：求證：在1，4，7，10，13，…，100中任選出20個(gè)數(shù)，其中至少有不同的兩對(duì)數(shù)，其和都等于104。證明：給定的數(shù)共有34個(gè)，相鄰兩數(shù)之差為3，可以將這些數(shù)分成18個(gè)不相交的集合：{1}，{52}，{4，100}，{7，97}，{10，94}，…，{49，55}。并且將他們分成18個(gè)抽屜，從已知的34個(gè)數(shù)中任意取出20個(gè)數(shù)，即使將前兩個(gè)抽屜中的數(shù)1和52均取出，剩下的18個(gè)在其余的16個(gè)抽屜中取到，則至少有不同的兩個(gè)抽屜中的書全部取出，這兩個(gè)抽屜中數(shù)互不相同，每個(gè)抽屜中兩個(gè)數(shù)的和都是104。即可以在1，4，7，10，13，…，100中任選出20個(gè)數(shù)，使其中至少有不同的兩對(duì)數(shù)的和都等于104。

證畢。

參考文獻(xiàn)

[1] 柯召，魏萬迪.組合論[M].北京科學(xué)出版社，1981.

[2] 李宇交.組合數(shù)學(xué)[M].北京師范大學(xué)出版社，1988.

[3] 朱歡.抽屜原理在中學(xué)數(shù)學(xué)競(jìng)賽解題中的應(yīng)用[J].高等函授學(xué)報(bào)（自然科學(xué)版），2010（6）.

[4] 蘭社云，高喜梅.淺談抽屜原理及抽屜構(gòu)造[J].河南教育學(xué)院學(xué)報(bào)（自然科學(xué)版），2003（2）.

[5] 孫玉芹.鴿籠原理及其簡(jiǎn)單應(yīng)用[J].新鄉(xiāng)師范高等?？茖W(xué)校學(xué)報(bào)，2001（1）.

[6] 龐國(guó)萍.抽屜原理的抽屜構(gòu)造法[J].玉林師范高等?？茖W(xué)校學(xué)報(bào)，2000（3）.

[7] 楊忠.抽屜原理應(yīng)用若干例[J].中學(xué)生數(shù)學(xué)，2010（8）.

[8] 石立葉，于娜，劉文菡.抽屜原理及其應(yīng)用[J].今日科苑，2009（17）.

[9] 蔣洪.關(guān)于鴿巢原理和Ramsey定理的幾個(gè)結(jié)論[J].科教文匯（中旬刊），2008（11）.