鴿巢原理

在‘數學歸納法（三）’發佈後，好友Koopa留下了一個非常有意思的回應，大家可參考其原文。

Koopa帶出了一個非常重要的概念，這就是歸納法可證明由經驗總結出來的公式，但並不能解釋公式背後的原理。其實，這正正是歸納系統的本質問題。事實上，數學家並不會滿於能證明經驗式，這祗是探索的開始，而絶不是終結！

Koopa的回應鼓勵了我再多寫一些入門數學和邏輯原理，今天，我便說一說‘鴿巢原理’（pigeonhole principle）。

很多人第一次認識‘鴿巢原理’，都會認為它是‘阿媽係女人’的廢話。對不起，數學並無空間容納廢話。我請大家先拿一點耐性出來了解一下就個看似‘阿媽係女人’的原理，然後，我便會利用它推導出一些絶不常識的東西。

‘鴿巢’這個譯法有點誤導。Pigeonhole在英文裏，可理解為一組一組的信箱，我在大學時，電腦打印機是極度昂貴的資源，整個電腦中心就祗有一兩部打印機，這些都是鎖在獨立的房間內，我們打印後便由操作員把printout派到我們的‘信箱’，這些‘信箱’便叫pigeonhole.

想像一下，若有50個pigeonhole，而有51份printout，這說明了甚麼呢？這便是至少有一個pigeonhole有兩份或以上的printout。明白了沒有！當然，可以51份printout都在同一個pigeonhole內，但這也符合我的說法。若有問題，請小心再看一看我的說法。

這便是‘pigeonhole principle’了！夠不夠‘阿媽係女人’呢？但是，若我說：‘在香港必然有兩人有相同數目的頭髮’，你又怎樣看呢？理由很簡單，人平均的頭髮數目約在150,000左右，我們可很‘安全地’假設一個人的頭髮數目不會多於1,000,000，但香港約有七百萬人！

同樣，若有四百人參加一個社交活動，就必然會找到兩人在同一天生日。因為一年最多祗得366天。

若你還是覺得這些都是‘阿媽係女人’，那麼我便再說一個電腦學上的例子。我曾在這裏討論過數據壓縮，對於無損失壓縮（loseless compression）而言，不論算法有多精妙，若可降低某些數據的檔案大小，就必然會增加某些數據的檔案大小！為甚麼？請想一想罷！若有人說，他的算法必會降低檔案大小，這就必然是個‘錯誤’。

事實上，pigeonhole principle並不限於‘有限’數目的命題，而是還可以用於有關‘無限’的命題。

邏輯永遠都是看似簡單，但認真研究，就一點也不是常識！但更重要的，就是不懂邏輯也可以活得開心快樂。祗要這些從未受邏輯訓練的人，不亂說甚麼合邏輯，甚麼不合邏輯便天下太平了！