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

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

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

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

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

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

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

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

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

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

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