Pigeonhole Principle

定义 Definition

鸽巢原理（抽屉原理）：如果把多于容器数量的对象放进这些容器里，那么至少有一个容器会包含两个或更多对象。常用于证明“必然会发生重复/碰撞/重合”。

发音 Pronunciation (IPA)

/ˈpɪdʒənˌhoʊl ˈprɪnsəpəl/

例句 Examples

If you put 11 socks into 10 drawers, at least one drawer has two socks.
如果把 11 只袜子放进 10 个抽屉里，至少有一个抽屉会有两只袜子。

In any group of 13 people, the pigeonhole principle implies that at least two share the same birth month.
在任意 13 个人的群体中，根据鸽巢原理，至少有两个人出生在同一个月份。

词源 Etymology

“pigeonhole”原指给鸽子用的小格子巢箱（一格一格的隔间），后来也指文件格/抽屉格。该原理借用这种“格子”的形象：当“鸽子”（对象）比“巢格”（容器）多时，必然出现“同格多鸽”的情况。该术语在英语数学语境中常见，也常被称为 Dirichlet principle（狄利克雷原理）（在某些数学文献中）。

相关词 Related Words

• Combinatorics
• Counting
• Proof
• Injection
• Surjection
• Bijection
• Invariant
• Dirichlet

文学与著作 Literary Works

• Proofs from THE BOOK（Aigner & Ziegler）中多次用鸽巢原理给出简洁证明。
• Concrete Mathematics（Graham, Knuth & Patashnik）在计数与离散数学论证中常提及该原理。
• Introduction to the Theory of Numbers（Hardy & Wright）在数论证明中使用鸽巢原理（常与狄利克雷近似等结论相关）。