淺談抽屜原理中抽屜的幾種構造方法

郭健紅 林彬

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

關鍵詞：組合數學 抽屜原理 存在性問題 構造

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

1 抽屜原理

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

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

以上定理不難推廣為：

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

根據以上定理結果，可得到以下結論。

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

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

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

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

以上結果均為有限形式的抽屜原理的有關結論，對于無限形式，有以下定理：

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

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

2 抽屜的構造

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

2.1 等分區間構造抽屜

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

抽屜。

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

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

從而可以進一步把區間等分成個小區間，構造抽屜。

證明：由柯西不等式有：

所以：

因此，當時，有

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

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

其中使得為整數，且。

證畢。

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

2.2 通過幾何圖形構造抽屜

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

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

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

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

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

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

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

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

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

圖1

上例通過分割圖形構造抽屜。首先根據問題的要求把圖形進行適當的分割，用這些分割成的圖形作為抽屜，再對已知點進行分類，集中對某一個或幾個抽屜進行討論，使問題得到解決。

2.3 利用余數構造抽屜

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

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

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

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

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

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

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

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

證畢。

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

2.4 利用分組構造抽屜

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

證畢。

參考文獻

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

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

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

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

[5] 孫玉芹.鴿籠原理及其簡單應用[J].新鄉師范高等?？茖W校學報，2001（1）.

[6] 龐國萍.抽屜原理的抽屜構造法[J].玉林師范高等?？茖W校學報，2000（3）.

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

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

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