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

郭健紅 林彬

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

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

中圖分類號：O29 文獻標識碼：A 文章編號：1674-098X（2012）12（a）-000-02

1 抽屜原理

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

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

以上定理不難推廣為：

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

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

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

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

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

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

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

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

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

2 抽屜的構(gòu)造

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

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

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

抽屜。

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

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

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

證明：由柯西不等式有：

所以：

因此，當時，有

把區(qū)間分成個小區(qū)間，每個區(qū)間長度為。而因為每個能取k個整數(shù)，所以一共有個整數(shù)。

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

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

證畢。

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

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

很多實際問題或數(shù)學問題，通過轉(zhuǎn)化均可轉(zhuǎn)化為相關(guān)的幾何問題。而對于其中一類存在性問題，涉及到一個幾何圖形內(nèi)有若干點時，常常可以把圖形巧妙地分割成適當?shù)牟糠郑缓笥梅指钏玫男D形作抽屜。這種分割一般符合一個“分劃”的定義，即抽屜間的元素既互不重復，也無遺漏；但有時根據(jù)解題需要，分割也可使得抽屜之間含有公共元素。

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

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

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

設，是的兩個非空子集，且

由抽屜原理可知，中至少有兩點屬于同一子集，不妨設。

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

設的點除之外全屬于，那么只要上有異于的點屬于，設在上的投影點為，則為直角三角形。

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

圖1

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

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

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

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

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

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

證明：設平面上的9個整點為，，令

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

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

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

證畢。

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

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

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

證畢。

參考文獻

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

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

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

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

[5] 孫玉芹.鴿籠原理及其簡單應用[J].新鄉(xiāng)師范高等專科學校學報，2001（1）.

[6] 龐國萍.抽屜原理的抽屜構(gòu)造法[J].玉林師范高等專科學校學報，2000（3）.

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

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

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