鴿籠原理（pigeonhole principle）

鴿籠原理是數學裡最顯而易見的想法，只是穿上了正裝：如果你把較多的鴿子放進較少的籠子，至少有一個籠子必定關著兩隻鴿子。房間裡有 13 個人，必有兩人生日同月，因為只有 12 個月。它聽起來微不足道，卻威力驚人，原因恰恰在於它保證了碰撞卻不告訴你在哪裡——你不必找出那個擠的籠子，你只知道它存在。

直白地說：若你把 n 件物品放進 m 個盒子且 n > m，則某個盒子必定裝著至少兩件物品。稍強的版本說某個盒子裝著至少 n/m 的上取整那麼多件。這個原理證明的是存在，而非位置：它告訴你會發生重複，卻從不告訴你是哪一個。要使用它，你得擺好正確的鴿子與正確的籠子——藝術在於選定誰扮演什麼角色，好讓「一個籠子裡有兩隻鴿子」意味著某件有用的事。

這正是幫浦引理的祕密引擎。一台有 n 個狀態的 DFA，餵入長度為 n 或更長的輸入，沿途至少造訪 n+1 個狀態（含起始）。把造訪過的位置當作鴿子、把 n 個狀態當作籠子：必有某個狀態重複。那個重複的狀態在執行中造成一個迴圈，而任何驅使機器繞過該迴圈的子串都可以被重複（幫浦）任意多次而仍被接受——這正是幫浦引理。同樣的計數也顯示：在任何夠長的輸入上，一台有限記憶的機器最終必定會重新進入它先前見過的某個格局。