淺談抽屜原理的構造及應用

摘要抽屜原理是組合數學中研究存在性問題的一個基本原理之一，也是非常規解題方法的重要類型之一。本文著重研討抽屜原理的幾種常用的構造方法，及其應用抽屜原理解答數學問題。

中圖分類號:O29文獻標識碼:A

1 利用分割圖形的方法構造抽屜

本方法主要用于解決點在幾何圖形中的位置分布和性質問題，通常我們把一個幾何圖形分割成幾部分，然后把每一部分當做一個“抽屜”，每個抽屜里放入相應的元素。通常情況下，我們分割圖形構造抽屜的最好方法是等分這個幾何圖形，例如等分圓，正方形等。

例1將13個點任意的放在一個邊長為2米的正方形內。求證:必存在這樣的4個點，以它們為頂點的四邊形的面積不超過1平方米。

分析與證明 將原正方形四等分為面積為1平方米的四個小正方形如圖(1)所示。由13 = 3€?4+1，依據抽屜原理，則必存在4個點落在面積為1平方米的小正方形內(或邊上)，因此以這4個點為頂點的四邊形的面積總不超過小正方形的面積，即以這樣的4個點為頂點的四邊形的面積不超過1平方米。

圖(1) 圖(2)

注:這里是將正方形等分為4個小的正方形來構造抽屜的，也可將此正方形等分為4個小的矩形來構造抽屜，如圖(2)。

2 利用劃分數組的方法來構造抽屜

利用此方法解題的關鍵是要明確分組的“對象”，然后將這些對象分成適當的數組，再應用抽屜原理，問題便得以解決。

例2任意給定7個不同的整數，求證:其中必有兩數之和或差是10的倍數。

證明設這7個不同的整數分別為，t1，t2，…t7，它們分別除以10后，得到的余數是從0到9中的數。

(1)若這7個余數中有兩個數相同:設ti =10p+k， tj =10q+k(p、q為整數)，則ti - tj=10(p-q)，即ti - tj是10的倍數，即存在兩數之差是10的倍數。

(2)若這7個余數中任何兩個都不同，由抽屜原理知，至少有一數被10除余數為6、7、8、9之一。

將余數為6的數與余數為4的數劃為一組，余數為7的數與余數為3的數劃為一組，余數為8的數與余數為2的數劃為一組，余數為9的數與余數為1的數劃為一組。于是便有，這7個不同的余數，除0，5外，其余的必有一組數它們做和是10的倍數。

3 利用物體所處的狀態構造抽屜

通常是根據各個物體所存在的狀態，將它們的狀態看作抽屜原理中的“抽屜”和“元素”，從而來解決問題的。

例3設有這樣的六點，任意兩點間都用紅色或藍色線段連接，且任意三點均不共線，證明:一定可以找到這樣的三點，以它們為頂點的三角形三邊涂有相同的顏色。

分析假設已知六點為A1、A2、A3、A4、A5、A6，由于任三點不共線，所以任意的三點能夠構成一個三角形。

證明任取一點為與其余五點相連得線段:A1A2，A1A3，A1A4，A1A5，A1A6，由于這五條線段涂有紅色或藍色，由抽屜原理知，這五條線段中至少有三條涂有同一種顏色。(設顏色表示抽屜，線段表示元素)，我們不妨假設A1A2，A1A3，A1A4三邊均為紅色，接下來探討△A2A3A4三邊的顏色，以便找到三邊相同顏色的三角形。

(1)若△A2A3A4中至少有一條紅色邊，則△A1A2A3就是三邊均為紅色的三角形;(2)若△A2A3A4中無紅色邊，則△A2A3A4就是三邊均為藍色的三角形。

綜上所述，總可以找到這樣的三點，由它們構成的三角形三邊顏色相同。

4 利用間接轉換的方法來構造抽屜

即通過間接轉換的方式，把原問題轉換為一類容易解決的新問題，繼而通過對新問題的求解，間接的來解決原問題。

例4 從一個班中任意選定6個人，試證其中必存在這樣的3個人，他們互相認識或都不認識。

證明將這6個人分別用A，B，C，D，E，F表示，不妨先以A為中心進行分析。設兩個人相互認識用紅色線段連接，否則用藍色線段連接，由此我們得到一個2色6階完全圖。于是原問題可以間接轉化為:“證明:一個2色6階圖中必定存在一個單色三角形，即三角形的三邊顏色相同。”因為點A與其它5點的連線只能是紅色或藍色，由抽屜原理知，其中至少有3條同色，不妨設AB，AC，AD皆為紅色。如果BC，BD，CD中有某1條(比如CD)是紅色的，則的三邊都是紅色;如果BC，BD，CD都是藍色，則的三邊都是藍色。綜上所述，一個2色6階圖中必定存在一個單色三角形，由此新問題得以解決，隨之原問題也得以解決。

注: 3和4的方法都可以用于解決以上類型的問題。

5 按同余類制造抽屜

例5 證明任意五個整數中，必有三個整數的和是3的倍數。

證明任一整數被3除余數只可能是0，1，2。若給定的五個整數被3除所得的余數中0，1，2都出現，那么余數分別為0，1，2的三個數的和一定能被3整除，如果余(下轉第105頁)(上接第69頁)數中至多只出現0，1，2中的兩個，那么由抽屜原理，其中必有一個余數至少出現三次。而這余數相同的三個數的和一定能被3整除。

注:對于如何解決有關整除的存在性問題，通常情況下，我們對模n進行同余分類，繼而造n個抽屜。即以n為模，可將整數集分為“余0類”、“余1類”，…，“余n-1類”共n只抽屜。然后應用抽屜原理，原問題便得以解決。

抽屜原理的應用非常廣泛，本文從抽屜原理出發，介紹了抽屜原理幾種常見的構造方法，在解決同一道抽屜原理的題時，并不是只有一種構造抽屜原理的方法，只有更多的接觸不同形式的問題并加以解決才能學好抽屜原理。

參考文獻

[1]吳順唐.離散數學[M].上海:華東師范大學出版社，1997.

[2]劉否南.華夏文集[M].太原:高校聯合出版社，1995.

[3]王向東，周士藩等.高等代數常用方法[M].1989.11.

[4]曹汝成.組合數學[M].華東理工大學出版社，2000.

[5]嚴士健.抽屜原則及其它的一些應用[J].數學通報，1959.

[6]盧開澄，盧華明.組合數學(第三版)[M].北京:清華大學出版社，2002.

[7]陳景林.抽屜原理及其應用[J].唐山師專學報，1999.9.

[8]潘可為.抽屜原理及其應用[J].湖州師專學報，1993.5.

[9]龐曉麗.用“抽屜”原理解決邏輯問題[J].保定師專學報，2001.5.

[10]蘭杜云，高喜梅.淺談抽屜原理及抽屜構造[J].河南教育學院學報(自然科學版)，2003.6.

[11]屈婉玲.組合數學[J].北京:北京大學出版社，1989.11.