抽屜原理的應(yīng)用

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

關(guān)鍵詞： 抽屜原理 基本形式 應(yīng)用舉例

1.抽屜原理的基本形式

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

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

2.抽屜原理應(yīng)用舉例

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

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

我們以另外的，來自數(shù)論中的應(yīng)用來結(jié)束本段.首先我們回憶，如果兩個(gè)正整數(shù)m和n的最大公約數(shù)為1，我們就稱它們?yōu)榛?shù).

于是，12和35互數(shù)，而12和15則否，因?yàn)?是12和15的公因子.

3.問題的總結(jié)

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

參考文獻(xiàn)：

[1]Richard.Brualdi著.羅平等譯.組合數(shù)學(xué).北京：機(jī)械工業(yè)出版社，2005.2.

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