歡迎來到鴿籠原理（Pigeonhole Principle）的世界！
在你的 H3 數學旅程中，你會遇到許多複雜的證明。有些證明需要數頁的代數運算，但有些則依賴一個簡單得驚人的概念，稱為鴿籠原理 (Pigeonhole Principle, PHP)。這個原理是你課程大綱中「數學證明與推理原則」部分的一項強大工具。它讓我們能夠證明某種情況必定存在，即使我們不知道它確切在哪裡！
如果這個名字聽起來有點好笑，別擔心。看完這些筆記，你就會明白為什麼這個「顯而易見」的概念，竟然是解決離散數學中最棘手問題的秘密武器。
1. 基本概念：鴿子與籠子
想像你有 10 隻鴿子，但只有 9 個籠子供牠們棲息。如果每隻鴿子都飛進籠子裡，我們可以肯定地說些什麼呢？
即使我們盡可能將牠們分散，也必定至少有一個籠子裡裝了超過一隻鴿子。畢竟，我們不可能給每隻鴿子一個獨立的房間！
數學定義：
如果將 \( n + 1 \) 隻鴿子放入 \( n \) 個籠子，那麼至少有一個籠子裡包含 2 隻或以上的鴿子。
簡單的類比：
想想你的襪子抽屜。如果你有 3 隻散襪子，顏色只有黑色或藍色（2 種顏色），那麼這 3 隻襪子中必定至少有 2 隻顏色相同。恭喜你，你剛剛運用了鴿籠原理！
重點複習：
- 鴿子 (Pigeons) = 你正在計算的物件。
- 籠子 (Holes) = 你用來放置這些物件的類別或容器。
- 規則 (The Rule) = 如果鴿子數量 > 籠子數量，則至少有一個籠子會有 > 1 隻鴿子。
2. 廣義鴿籠原理
有時候，我們的鴿子數量遠多於籠子。例如，如果有 21 隻鴿子和 10 個籠子，情況會如何？
如果我們盡可能均勻地分配，每個籠子會分到 2 隻鴿子，還剩餘 1 隻。這多出來的 1 隻鴿子必須塞進某個已經有 2 隻的籠子，這意味著至少有一個籠子會擁有 3 隻鴿子。
公式：
如果將 \( N \) 個物件放入 \( k \) 個盒子，那麼至少有一個盒子包含至少 \( \lceil N/k \rceil \) 個物件。
註：符號 \( \lceil x \rceil \) 是頂函數 (ceiling function)。它的意思是「向上取整至最接近的整數」。例如，\( \lceil 2.1 \rceil = 3 \)。
逐步範例：
假設房間裡有 50 個人。那麼必定有多少人是在同一個星期幾出生的呢？
1. 找出鴿子：\( N = 50 \)（人數）。
2. 找出籠子：\( k = 7 \)（一星期的天數）。
3. 計算：\( 50 / 7 \approx 7.14 \)。
4. 向上取整：\( \lceil 7.14 \rceil = 8 \)。
結論：至少有 8 個人是在同一個星期幾出生的。
3. 如何處理 PHP 問題
不知道該如何下手？別擔心！大多數 PHP 問題都遵循相似的模式。當你看到題目要求你「證明存在...」或「顯示至少有...」時，請按照以下步驟進行：
步驟 1：找出「鴿子」
你正在分配的是什麼東西？通常是數量較多的那一群（數字、人數、點位）。
步驟 2：找出「籠子」
類別是什麼？這通常是最困難的部分。你可能需要根據餘數、數字範圍或幾何區域來建立「盒子」。
步驟 3：應用原理
說明因為鴿子數量大於籠子數量（或是籠子數量的倍數），結論必定成立。
關鍵要點：鴿籠原理是一種非構造性證明 (non-constructive proof)。它告訴我們某種情況必定存在，但它不會告訴你具體是哪一個籠子裡有額外的鴿子！
4. 常見應用與範例
範例 1：生日
在一群 13 個人中，必定至少有兩個人是在同一個月份出生的。
（鴿子 = 13 人，籠子 = 12 個月份。由於 13 > 12，結論成立。）
範例 2：數論（餘數）
證明如果你選取 6 個整數，其中至少有兩個整數除以 5 時的餘數相同。
（鴿子 = 6 個整數，籠子 = 除以 5 的可能餘數，即 {0, 1, 2, 3, 4}。由於有 6 個數字但只有 5 種可能的餘數，必然有兩個數字共用同一個餘數。）
你知道嗎？
這個原理也被稱為狄利克雷抽屜原理 (Dirichlet's Box Principle)，以德國數學家彼得·古斯塔夫·勒熱內·狄利克雷命名，他在 1834 年將其形式化。
5. 常見錯誤
1. 混淆鴿子與籠子：一定要確保你的「鴿子」是那些被分配的物品，而「籠子」是容器。如果你搞反了，數學邏輯就不成立了！
2. 忘記向上取整：在廣義版本中，一定要記得使用頂函數。即使除法結果是 \( 2.01 \)，答案也必須是 3。
3. 以為能找到具體的那個籠子：PHP 只證明了存在性。如果你說「第三個籠子裡必定有兩隻鴿子」，通常是過度推論了。你只能說「至少有一個籠子裡有兩隻鴿子」。
總結檢查清單
- 基本 PHP： \( n+1 \) 個物件放入 \( n \) 個盒子 \( \rightarrow \) 至少有一個盒子有 \( \ge 2 \) 個物件。
- 廣義 PHP： \( N \) 個物件放入 \( k \) 個盒子 \( \rightarrow \) 至少有一個盒子有 \( \ge \lceil N/k \rceil \) 個物件。
- 先決條件：在寫證明之前，請務必清楚定義你的鴿子和籠子。
- 目標：運用此原理來證明組合數學和數論問題中的存在性。
持續練習吧！起初，找出「籠子」可能像在解謎，但只要累積一點經驗，你就會開始發現到處都是鴿籠！