你或許已熟知這樣一個(gè)原理：

當(dāng)有n個(gè)籠子和n+1只鴿子，那么至少有一個(gè)籠子里有2只鴿子。

這就是“鴿巢原理”，又名"抽屜原理"或"鴿籠原理"等等。

這個(gè)原理聽(tīng)上去簡(jiǎn)直像廢話(huà)，這是小學(xué)生都能懂的道理。但它既然能在數(shù)學(xué)里留下名字，它當(dāng)然是很有用的一個(gè)原理，絕不是只能簡(jiǎn)單處理把鴿子放進(jìn)籠子這樣的情況。那么以下，我列舉一些可以用鴿巢原理證明的有趣命題和結(jié)論。

先來(lái)一個(gè)比較簡(jiǎn)單的，生活化的例子。有若干人，在一個(gè)房間里聚會(huì)。聚會(huì)開(kāi)始時(shí)互相握手認(rèn)識(shí)。那么有這樣一個(gè)結(jié)論：

在任何時(shí)刻，總存在兩個(gè)人，與這兩人握過(guò)手的人數(shù)，是相等的。

證明如下：

假設(shè)有一共有n個(gè)人，那么每個(gè)人可以握手的人數(shù)就是從0到n-1，一共有n種可能。一共有n個(gè)人，那么看上去似乎鴿巢原理用不上了呢？別急，這里面還有一個(gè)情況。如果有一個(gè)人，與其握過(guò)手的人數(shù)是n-1，那么就不應(yīng)該有另一個(gè)人，與其握過(guò)手的人數(shù)是0了。同理，如果某個(gè)人一次也沒(méi)有跟其他人握手，那么就不會(huì)有另一個(gè)人，與n-1個(gè)人握手。所以“0”與“n-1”，這兩個(gè)數(shù)字不能共存。因此所有人的可能握手人數(shù)，其范圍要么是從1到n-1，要么是從0到n-2，一共n-1種可能。

而總?cè)藬?shù)有n個(gè)人，所以必然存在2個(gè)人，他們的握手人數(shù)相等，證明完成。這個(gè)問(wèn)題也經(jīng)常用錦標(biāo)賽來(lái)描述，結(jié)論就是，在一場(chǎng)錦標(biāo)賽里，任何時(shí)刻總有兩個(gè)人或兩支隊(duì)伍，他們比賽過(guò)的場(chǎng)次數(shù)是一樣的。這是第一個(gè)例子。

再來(lái)一個(gè)比較偏數(shù)學(xué)的例子，考慮這樣一個(gè)數(shù)列：

7, 77, 777, 7777，77777，777777, ...

即由若干個(gè)7連寫(xiě)的數(shù)字構(gòu)成的數(shù)列。請(qǐng)證明：這些數(shù)字中，至少有一個(gè)能被2027整除。

當(dāng)然，你可以一個(gè)一個(gè)去試，直到找到這樣一個(gè)能被2027整除的數(shù)字。但是這樣很麻煩，即使用電腦編程求解，你也不知道程序需要跑多久。另外，2027是一個(gè)質(zhì)數(shù)，所以你不用考慮與質(zhì)因數(shù)分解相關(guān)的方法。

這里有一個(gè)使用鴿巢原理，且非常簡(jiǎn)潔的證明方法。而且，可以證明更強(qiáng)的結(jié)論：這個(gè)序列里不但肯定有可以被2027整除的數(shù)字，而且這個(gè)數(shù)字出現(xiàn)在前2027項(xiàng)以?xún)?nèi)。以下是證明。

首先，用反證法。假設(shè)這個(gè)數(shù)列的前2027項(xiàng)里，所有數(shù)字都不能被2027整除。那么這些數(shù)字除以2027，都會(huì)有余數(shù)，余數(shù)的取值范圍是從1到2026，一共2026種。根據(jù)鴿巢原理，這個(gè)數(shù)列里的前2027中，必然有兩個(gè)數(shù)字，它們除以2027后，所得余數(shù)相等，那么現(xiàn)在有意思了。

我們把這兩個(gè)數(shù)字取出來(lái)，把大的那個(gè)去減去小的那個(gè)，考察相減后的數(shù)字。因?yàn)樵葍蓚€(gè)數(shù)字除以2027后余數(shù)相等，所以它們相減后，它們的差必然可以被2027整除，這一點(diǎn)是比較容易確認(rèn)的。那么再看一下這個(gè)差值數(shù)字的形式。因?yàn)樵葍蓚€(gè)數(shù)字都是7連寫(xiě)構(gòu)成的數(shù)字，那么它們相減后必然所得數(shù)字必然是若干個(gè)7在開(kāi)頭，后面有若干個(gè)0的形式：

7...70....0

這個(gè)數(shù)字可以改寫(xiě)為 7...7 × 的形式。

10^n是肯定不能被2027整除的，則那若干個(gè)“7”連寫(xiě)構(gòu)成的整數(shù)必然能被2027整除。而那若干個(gè)“7”連寫(xiě)，本身就是數(shù)列的前2027項(xiàng)中的某一項(xiàng)，那么這個(gè)情況就與我們證明開(kāi)始時(shí)的假設(shè)矛盾了！從而我們?cè)谧C明開(kāi)始時(shí)的假設(shè)不成立，這說(shuō)明，這個(gè)數(shù)列的前2027項(xiàng)中必有一項(xiàng)可以被2027整除。

而這個(gè)證明也告訴我們，一般來(lái)說(shuō)“鴿巢原理”給出的結(jié)論都是存在性的，而不是構(gòu)造性的。這也是數(shù)學(xué)奇妙的地方之一，它可以告訴你一個(gè)東西肯定存在，但不知道在哪里。

再看一個(gè)比較生活化的例子。請(qǐng)證明：在任何一年，最少有4個(gè)月份，最多有5個(gè)月份，包含5個(gè)星期天。

你不信的話(huà)，可以馬上看一下日歷，數(shù)數(shù)有哪幾個(gè)月有5個(gè)星期天。那么可以告訴你，有5個(gè)星期天的月份總是4個(gè)或5個(gè)，不過(guò)多也不會(huì)少。這個(gè)結(jié)論，可以簡(jiǎn)單得用鴿巢原理證明，大概也是唯一的方法。

因?yàn)橐荒?65或366天，也就是52個(gè)星期多1天或2天。那么一年里至少有52個(gè)星期天，最多53個(gè)星期天（如果這一年元旦恰好是星期天等）。我們要把這些星期天，分布到12個(gè)月里。因?yàn)槊總€(gè)月至少28天，至多31天，也就是每個(gè)月至少有4個(gè)星期天，最多5個(gè)星期天。

那么，現(xiàn)在就可以反證法了。如果只有3個(gè)月份有5個(gè)星期天，那么其他9個(gè)月份都是4個(gè)星期天，總共是3×5+9×4=51個(gè)星期天，就與這一天年至少有52個(gè)星期天矛盾了。而如果有6個(gè)月份有5個(gè)星期天，那么其他6個(gè)月份是4個(gè)星期天，總的星期天數(shù)量是6×5+6×4=54，這就與一天中最多53個(gè)星期天矛盾了。所以，一年中最少有4個(gè)月，最多有5個(gè)月份，包含5個(gè)星期天，證明完成！

而用鴿巢原理還能得出一些令人吃驚的有趣結(jié)論。比如，有這樣一個(gè)結(jié)論：全體北京人中間，至少有兩個(gè)人的頭發(fā)數(shù)量相同，排除光頭。這很好理解，因?yàn)槿说钠骄^發(fā)數(shù)量是10萬(wàn)，不會(huì)超過(guò)15萬(wàn)，北京人口遠(yuǎn)超這個(gè)數(shù)量，所以北京肯定有2個(gè)人有相同的頭發(fā)數(shù)量。而且北京人口實(shí)際超過(guò)2千多萬(wàn)，所以這個(gè)結(jié)論可以加強(qiáng)為：北京肯定有100個(gè)人，他們有相同數(shù)量的頭發(fā)。

“鴿巢原理”可以告訴我們的一個(gè)最驚人的結(jié)論是這樣一個(gè)（大概率成立的）命題：在最近1000年以?xún)?nèi)，存在這樣一個(gè)歷史上的人，這個(gè)人是你的父母親的共同祖先！也就是，你的父母都是這個(gè)人的后代。

你可能會(huì)說(shuō)，這怎么可能，我變成近親結(jié)婚的后代了嗎？你先別急，1000年以?xún)?nèi)，從生物學(xué)上講已經(jīng)完全不是近親了。但是，這個(gè)結(jié)論是成立的嗎？那么我們來(lái)論證一下這個(gè)結(jié)論，它可以用鴿巢原理非確定性的證明，但是大概率是成立的。

首先，如果我們從自己的父母向上追溯人口的話(huà)，你會(huì)發(fā)現(xiàn)每向上一代，你的祖先人數(shù)就會(huì)翻倍。你的父母有兩個(gè)人；你的祖父祖母、外公外婆是4個(gè)人。你向上追溯n代，那么你就會(huì)有2^n個(gè)祖先。

那么我們假設(shè)每25年，有一代人的更迭。那么1000年的話(huà)，大約是40代。如果你的祖先40代，都是不同的人，那么總的人數(shù)就是2+4+8+....+2^40=人，大約是，也就是22萬(wàn)億人，這個(gè)數(shù)字太嚇人了！根據(jù)歷史記載，最近1000年，地球上存在過(guò)的人口數(shù)量，遠(yuǎn)小于22萬(wàn)億人。所以，這就說(shuō)明，你的祖先這40代人，不可能都是不同的人！很可能，有某人是你父母的共同祖先。

但為什么說(shuō)這不是一個(gè)100%嚴(yán)謹(jǐn)?shù)淖C明呢？因?yàn)檫€存在這樣一種可能：你父親這一支向上的祖先，發(fā)生過(guò)很多的合并，也就是你父親的祖先里，有很多人有共同的祖先。同樣，你母親這一支的祖先中，也有很多人有共同的祖先。這樣你父母親的祖先這兩支人口，就不需要那么多人了，有可能，你父母的祖先在1000年內(nèi)完全是兩個(gè)沒(méi)有交集的群體。但這也說(shuō)明，如果以上結(jié)論對(duì)你不成立，那么這個(gè)結(jié)論就會(huì)對(duì)你的父母更大概率的成立。

這就是鴿巢原理告訴我們的一個(gè)反直覺(jué)結(jié)論。它讓我想起了一些延伸的結(jié)論。既然以上結(jié)論適合你的父母，其實(shí)它也適合任何兩個(gè)人。

比如，中國(guó)人有句俗語(yǔ)，對(duì)同姓氏的人，我們常說(shuō)“五百年前是一家”。根據(jù)以上推導(dǎo)，這句話(huà)還真不是一句客套話(huà)，而是可以從數(shù)學(xué)上證明的。同姓氏的兩個(gè)人，非常有可能在500年內(nèi)，有一個(gè)共同祖先，尤其是那些不常見(jiàn)的姓氏。

那么有關(guān)鴿巢原理，就聊到這里。鴿巢原理雖然內(nèi)容簡(jiǎn)單，但是它確實(shí)能幫我們證明一些意想不到的結(jié)論。最后，出兩道有意思的，與鴿巢原理相關(guān)的思考題，供大家消遣娛樂(lè)：

史密斯夫婦，邀請(qǐng)4對(duì)夫婦到家里來(lái)玩。這4對(duì)夫婦中，有些人是史密斯先生的朋友，有些是史密斯太太的朋友，有些互相之間認(rèn)識(shí)，有些不認(rèn)識(shí)。當(dāng)這4對(duì)夫婦到達(dá)史密斯夫婦的家中后，所有之前互相認(rèn)識(shí)的人都握手了一下。史密斯先生發(fā)現(xiàn)了一個(gè)有意思的情況，他說(shuō)：如果把我排除在外，剩下的人中，每個(gè)人握手的次數(shù)都是不同的。這里，有兩個(gè)隱含條件是：自己不會(huì)跟自己握手，夫妻之間也當(dāng)然不需要握手。現(xiàn)在的問(wèn)題是：史密斯太太握了幾次手？

這個(gè)問(wèn)題聽(tīng)上去是不是有點(diǎn)不可思議，因?yàn)橐阎獥l件如此至少，怎么突然就問(wèn)史密斯太太握了幾次手？但是，根據(jù)鴿巢原理，確實(shí)可以唯一的確定史密斯太太的握手次數(shù)。請(qǐng)你來(lái)做一次偵探，推理出這個(gè)數(shù)字。

參考文檔：

http://www.microlinkcolleges.net/elib/files/undergraduate/Mathematics/A%20Walk%20Through%20Combinatorics%20An%20Introduction%20to%20Enumeration%20and%20Graph%20Theory.pdf