抽屜原理及其在數學與生活中的應用

戴蔣千易

摘要：本文首先講述了抽屜原理的概念和幾種形式和推廣，然后列舉了其在數學及格分支中的應用以及在生活中的應用，使我們意識到，利用抽屜原理確實可以幫我們解決一些實際問題。

關鍵詞：抽屜原理；圖論

中圖分類號：G633.6 文獻標識碼：B 文章編號：1672-1578（2017）09-0172-01

抽屜原理是德國數學家狄利克雷發現的，其形式簡單易懂，卻包含了深奧的道理，在應用中，對一些命題的證明時，往往起到令人驚奇的效果。它從構造法角度證明了存在性的問題。

陳景林在他的《組合數學與圖論》中講了抽屜原理的三種形式：

形式一、也是最簡單的形式，就是將n+1個以上的物品放到n個抽屜中，則至少有一個抽屜里放兩個以上的物品。

形式二、把多于m×n個物品放到n個抽屜中，無論怎樣放，一定能找到一個抽屜，它里面至少有（m+1）個物品。

形式三、把無窮個物品放到有限個抽屜中，無論怎樣放，一定能找到一個抽屜，它里面至少有無窮個物品。

在數學問題中有一類與"存在性"有關的問題，如367個人中至少有兩個人是同一天過生日等這類問題在生活中非常常見，它所依據的理論 ，就是"抽屜原理"。"抽屜原理"的理論本身并不復雜，但"抽屜原理"的應用是千變萬化的。

以下是抽屜原理在數學中的幾個典型應用。

例1：證明任取8個自然數，必有兩個數的差是7的倍數。

證明：任一個整數被7除后的余數只有可能是0到6這7個自然數中一個。把這7個自然數看成是7個抽屜，則8個整數中必有兩個整數被7除后的余數落在同一個抽屜里面，即必有至少兩個整數除以7的余數相等。則這兩個數的差必然是7的倍數。

例2.木箱里裝有紅色球3個、黃色球5個、藍色球7個，若蒙眼去摸，為保證取出的球中有兩個球的顏色相同，則最少要取出多少個球？

解：把3種顏色看作3個抽屜，若要符合題意，則小球的數目必須大于3，故至少取出4個小球才能符合要求。

例3.任意5個整數中，有其中3個整數的和為3的倍數。

證：將整數分為形如3k、3k+1及3k+2這3類形式，則我們可以將這3類整數看作是3個抽屜，將這5個整數看作元素放入這3個抽屜中。

由抽屜原理可知，至少存在2個整數在同一抽屜中，即它們都是形如（3k+m）的整數，m=0，1或2。

如果有3個以上的數在同一個抽屜中，則取其中的任意三個數，它們的和是形如3（3k+m）的整數，即三者的和為3的倍數。

如果有2個整數在同一個抽屜中，則由抽屜原理知，在余下的3個數中有2個數在同一個抽屜中，余下的1個數在另一個抽屜中.在3個抽屜中各取一個數，這3個數的形式分別為3k1，3k2+1，3k3+2，則三者的和為3（k1+k2+k3）+3，即為3的倍數。

例4.三維空間中9個坐標為整數的點，試證在兩兩相連的線段內，至少存在一個坐標為整數的內點。

解：三維空間中，任意兩坐標為整數的點，若這兩點相連的線段內不存在坐標為整數的內點，則對于x，y，z這三個坐標軸，這兩點至少在一個坐標上的差值正好是1.

那么，在這9個坐標為整數的點中，任意取出一點，與這個點的三個坐標中，存在的差值正好是1的共有7類，即與x軸差值正好是1，與y軸差值正好是1，與z軸差值正好是1，與x，y軸差值都是1，與x，z軸差值都是1，與y，z軸差值都是1，與x，y，z軸差值都是1。

對于剩下的8個點，若存在一點a不滿足這7種情況，那么a點與這個點相連的線段內必有一個坐標為整數的內點。

若剩下的8個點都屬于這7種情況之一，那么，運用鴿巢原理，則至少存在兩個點屬于這7種情況中的同一個情況，那么，這兩點中必存在一個坐標為整數的內點。

例5.任意6個人中，要么有三個人互相認識，要么有三個人互不認識。

證：先選定一人，叫A先生，則他要么至少跟其他5人中3人以上認識，要么跟3人以上不認識。不妨設第一種情況。那么再看這三人之間，如果他們有兩人認識，則與A先生3人之間互相認識，如果兩兩不認識，則也滿足本題結論。

例6.有11名學生到老師家借書，假設老師的書房中有A、B、C、D四類書，每名學生最多可借兩本不同類的書，最少借一本。試證明：必有兩個學生所借的書的類型相同。

證：若學生只借一本書，則不同的類型有A、B、C、D四種，若學生借兩本不同類型的書，則不同的類型有AB、AC、AD、BC、BD、CD六種。共有10種類型，把這10種類型看作10個"抽屜"，把11個學生看作11個"蘋果"。如果誰借哪種類型的書，就進入哪個抽屜，由抽屜原理，至少有兩個學生，他們所借的書的類型相同。

參考文獻：

[1] 巧用抽屜原理 馮躍峰 中國科學技術大學出版社 2005

[2] 抽屜原理及其他 常庚哲 上海教育出版社 1986年endprint