鴿籠原理

如果你把 13 隻鴿子放進 12 個鴿籠，至少有一個籠子必定裝了兩隻以上——籠子根本不夠。這個聽起來理所當然的敘述就是鴿籠原理，儘管簡單，它能證明出人意料的存在性事實。它不告訴你「哪一個」籠子擠了，只說必定有一個擠；它是用來證明某物必定存在的工具，而非找出它的工具。

基本形式：若把 n 個東西放進 m 個容器、而 n 大於 m，則至少有一個容器裝了至少兩個。一般化的形式更精細：若把 n 個東西放進 m 個容器，某個容器裝了至少 n/m 的天花板（向上取整）個。經典而乾淨的例子是：任意 13 個人中，至少有兩人生日在同一個月，因為只有 12 個月、而 13 大於 12。其中的藝術在於選對「鴿子」與「籠子」分別是什麼，好讓原理派上用場。

鴿籠原理純粹是「存在」工具——它在不構造的情況下保證了一次碰撞或重複，所以給人一種白白得來的感覺。它支撐著許多計數與機率論證：它立刻證明任意 367 人中至少有兩人同一天生日（只有 366 個可能日期），也是「鍵比槽多的完美雜湊必定碰撞」背後的嚴謹骨幹。誠實的限制：它告訴你某種巧合無法避免，卻從不告訴你如何找到它、或一個「接近的」巧合有多可能（那個較柔和的問題是生日問題）。