第二章(Chapter 2)鴿巢原理(The Pigeonhole Principle)

第二章(Chapter2)鴿巢原理(ThePigeonholePrinciple)2.1問題的引入鴿巢原理又稱抽屜原理(theDirichletdrawerprinciple)或鞋盒原理(shoeboxprinciple)原理闡釋：有許多鴿子飛進(jìn)不足夠多的鴿子巢內(nèi)，那么至少要有一個鴿巢被兩個或多個鴿子占據(jù)。2.1問題的引入實例：⒈366個人中必然有至少兩人生日相同。⒉抽屜里散放著10雙手套，從中任意抽取11只，其中至少有兩只使成雙的。⒊某次會議有n位代表參加，每位代表認(rèn)識其他代表中某些人，則至少有兩個人認(rèn)識的人數(shù)是一樣的。⒋任給5個不同的整數(shù)，其中至少有3個數(shù)的和被3整除。這些例子中都包含著鴿巢原理的一般意義。2.2鴿巢原理的簡單形式：定理2.1

如果n+1個物體被放進(jìn)n個盒子，那么至少有一個盒子包含兩個或更多個物體。證明：如果這n個盒子中的每一個都至多含有一個物體，那么物體的總數(shù)最多是n。既然我們有n+1個物體，于是某個盒子就必然包含至少兩個物體。[注]：①鴿巢原理僅能被用于證明一個排列或某種現(xiàn)象的存在性，不能對任何構(gòu)造排列或?qū)ふ椰F(xiàn)象的例證給出任何指示。

②一些與鴿巢原理相關(guān)的其他原理：如果n個物體放入n個盒子并且沒有一個盒子是空的，那么每個盒子恰好包含一個物體；如果n個物體放入n個盒子并且沒有盒子被放入多于一個物體，，那么每個盒子中恰好有一個物體；③上述三個原理的抽象表述形式：令X和Y是兩個有限集，并令f：X→Y是一個從X到Y(jié)的函數(shù)，如果X的元素多于Y的元素，那么f就不是一一對應(yīng)的。如果X和Y含有相同個數(shù)的元素，并且f是映上(onto)的,那么f就是一一對應(yīng)的。如果X和Y含有相同個數(shù)的元素，并且f是一對一的，那么f就是映上的。④若把將物體放入盒子改為用n中顏色中的一種顏色對每一個物體涂色，則鴿巢原理可斷言：如果n+1個物體用n中顏色涂色，那么必然有兩個物體被涂成相同顏色。下面介紹鴿巢原理簡單形式的應(yīng)用：例題2.2.1：從1到2n的正整數(shù)中任取n+1個，則這n+1個數(shù)中至少有一對數(shù)，其中一個數(shù)是另一個數(shù)的倍數(shù)。解證明：設(shè)所取n+1個數(shù)分別為：對序列中的每一個數(shù)去掉一切2的因子，直至剩下一個奇數(shù)為止。例如，68=2×34=22×17，去掉2的因子22，留下奇數(shù)17，結(jié)果得到由奇數(shù)組成的序列：……(R)1到2n中只有n個奇數(shù)，故序列(R)中至少有兩個是相同的。設(shè)為：，對應(yīng)地有：，，若＞，則是的倍數(shù)。例題2.2.2：設(shè)是正整數(shù)序列，則至少存在整數(shù)和，＜，使得和：是的倍數(shù).（即，在序列中存在連續(xù)個，這些之和能被整除）。解例題2.2.3：設(shè)是3個任意整數(shù)；是的任一排列，則至少有一個是偶數(shù)。

解：例題2.2.4（中國余氏定理）令和為二互素的正整數(shù)，并令和為兩整數(shù)，且0≤≤以及0≤≤。于是，存在一個整數(shù)，使得除以的余數(shù)為，并且除以的余數(shù)為；即可以寫成的同時又可以寫成的形式，這里和是兩個整數(shù)。

解：2.3鴿巢原理的推廣形式（也稱加強(qiáng)形式）定理2.2令為正整數(shù)。如果將個物體放入盒子內(nèi)，那么，或者第一個盒子至少含有個物體，或者第二個盒子至少含有個物體，……,或者第個盒子至少含有個物體。

證明：[注]：⑴鴿巢原理的簡單形式是由其加強(qiáng)形式通過令而得到的。⑵鴿巢原理的加強(qiáng)形式可用著色的術(shù)語表述為：如果個物體中的每一個物體被指定用種顏色中的一種著色，那么存在一個這樣的，使得第種顏色的物體至少有個。⑶鴿巢原理加強(qiáng)形式的直接表述：只鴿子，個鴿巢，則至少有一個鴿巢里有不少于只鴿子。（其中，表示的取整，即不超過的最大整數(shù)）⑷在初等數(shù)學(xué)中，鴿巢原理加強(qiáng)形式常用于都等于同一個整數(shù)的特殊情況。此時，該原理可敘述為：

1）如果個物體放入個盒子中，那么至少有一個盒子含有個或更多個物體。

2）如果個非負(fù)整數(shù)的平均數(shù)大于，即：＞，那么至少有一個整數(shù)大于或等于。

3）如果個非負(fù)整數(shù)的平均數(shù)小于，即：＜，那么其中

至少有一個整數(shù)小于。4）如果個非負(fù)整數(shù)的平均數(shù)至少等于，那么這個整數(shù)中至少有一個滿足≥。下面介紹鴿巢原理加強(qiáng)形式的應(yīng)用：例題2.3.1：一籃子水果裝有蘋果、香蕉和橘子。為了保證籃子里或者至少8個蘋果或者至少6個香蕉或者至少9個橘子，則放入籃子中的水果的最小件數(shù)是多少？解：例題2.3.2：設(shè)A是個正整數(shù)的集合，≥1，證明：存在非空子集BA，使得B的元素之和被除盡。解：例題2.3.3：(Erdos/Szekeres定理)——具體見Acombinatorialproblemingeometry,CompositioMathematica,2(1935),463-470試證：每個由個不相等實數(shù)構(gòu)成的序列或者含有長度為的遞增子序列，或者含有長度為的遞減子序列。解：例題2.3.