抽屜原理的應用

摘 要： 抽屜原理是初等的組合原理，它能夠用來解決各種有趣的問題，常常會得出一些驚奇的結論.

關鍵詞： 抽屜原理 基本形式 應用舉例

1.抽屜原理的基本形式

定理：如果將n+1個物體放進n個抽屜，那么至少有一個抽屜中包含兩個或更多的物體.

證明：如果這n個盒子中的每一個至多包含有一個物體，那么物體的總數最多是n，既然我們有n+1個物體，于是某個盒子中就必然包含至少兩個物體.

2.抽屜原理應用舉例

例3：從整數1，2，…，200中，我們選擇101個整數.證明：在所選的這些整數之間存在兩個這樣的整數，其中的一個可被另一個整除.

注意，例3在這種意義下是最好的可能：從1，2，…，200中可以選擇這樣的100個數，其中沒有一個能被另一個整除，比如，101，102，…，199，200就是這樣的整數.

我們以另外的，來自數論中的應用來結束本段.首先我們回憶，如果兩個正整數m和n的最大公約數為1，我們就稱它們為互數.

于是，12和35互數，而12和15則否，因為3是12和15的公因子.

3.問題的總結

通過上述三個例題，我們看到，利用抽屜原理能夠解決看起來很復雜的問題，而得出解決問題的關鍵是為后面巧妙地構造抽屜.

參考文獻：

[1]Richard.Brualdi著.羅平等譯.組合數學.北京：機械工業出版社，2005.2.

[2][匈]B.Andra’sfai著.郭照人譯.圖論導引[M].北京：高等教育出版社，1985.8.