别名

鸽笼原理，狄利克雷抽屉原理

表述

• 表述1：若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子。
• 表述2：若有n个笼子和kn+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少k+1只鸽子。
• 集合论表述：若A是n+1元集，B是n元集，则不存在从A到B的单射。

应用

• 哈希表的重复问题是不可避免的。因为Keys的数目总是比Indices的数目多。
• 任何无损压缩算法，在把一个文件变小的同时，一定有其他文件增大来辅助，否则某些信息必然会丢失。