抽屜原理及其在數(shù)學(xué)與生活中的應(yīng)用

戴蔣千易

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

關(guān)鍵詞：抽屜原理；圖論

中圖分類號：G633.6 文獻(xiàn)標(biāo)識碼：B 文章編號：1672-1578（2017）09-0172-01

抽屜原理是德國數(shù)學(xué)家狄利克雷發(fā)現(xiàn)的，其形式簡單易懂，卻包含了深奧的道理，在應(yīng)用中，對一些命題的證明時，往往起到令人驚奇的效果。它從構(gòu)造法角度證明了存在性的問題。

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

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

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

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

在數(shù)學(xué)問題中有一類與"存在性"有關(guān)的問題，如367個人中至少有兩個人是同一天過生日等這類問題在生活中非常常見，它所依據(jù)的理論 ，就是"抽屜原理"。"抽屜原理"的理論本身并不復(fù)雜，但"抽屜原理"的應(yīng)用是千變?nèi)f化的。

以下是抽屜原理在數(shù)學(xué)中的幾個典型應(yīng)用。

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

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

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

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

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

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

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

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

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

例4.三維空間中9個坐標(biāo)為整數(shù)的點，試證在兩兩相連的線段內(nèi)，至少存在一個坐標(biāo)為整數(shù)的內(nèi)點。

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

那么，在這9個坐標(biāo)為整數(shù)的點中，任意取出一點，與這個點的三個坐標(biāo)中，存在的差值正好是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點與這個點相連的線段內(nèi)必有一個坐標(biāo)為整數(shù)的內(nèi)點。

若剩下的8個點都屬于這7種情況之一，那么，運(yùn)用鴿巢原理，則至少存在兩個點屬于這7種情況中的同一個情況，那么，這兩點中必存在一個坐標(biāo)為整數(shù)的內(nèi)點。

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

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

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

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

參考文獻(xiàn)：

[1] 巧用抽屜原理 馮躍峰 中國科學(xué)技術(shù)大學(xué)出版社 2005

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