鸽巢原理

✍ dations ◷ 2025-12-08 04:13:34 #组合数学,数学定理

鸽巢原理,又名狄利克雷抽屉原理、鸽笼原理。

其中一种简单的表述法为:

另一种为:

集合论的表述如下:

拉姆齐定理是此原理的推广。

虽然鸽巢原理看起来很容易理解,但有时使用鸽巢原理会得到一些有趣的结论:

另一个例子:

另一个例子:

更不直观一点的例子:

鸽巢原理经常在计算机领域得到真正的应用。比如:哈希表的重复问题(冲突)是不可避免的,因为Keys的数目总是比Indices的数目多,不管是多么高明的算法都不可能解决这个问题。这个原理,还证明任何无损压缩算法,在把一些输入变小的同时,作为代价一定有其他的输入增大,否则对于长度为L的输入集合,该压缩算法总能将其映射到一个更小的长度小于L的输出集合,而这与鸽巢理论相悖。

一种表达是这样的:如果要把n个对象分配到m个容器中,必有至少一个容器容纳至少 n m + 1 {\displaystyle \left\lceil {\frac {n}{m}}+1\right\rceil } 1, 2, ..., 皆是正整数,现有

个对象要分配在个箱子中,那么以下叙述至少一者成立:

这个原理一样可以使用反证法证明,即假设上述所有叙述为假并得出矛盾,方法与前述简单情况类似。

借由康托的无穷基数可将鸽巢原理推广到无穷集中:如果集合A的势大于集合B的势,那么不存在由A到B的单射。

相关

  • 雪是降水形式的一种,是从云中降落的结晶状固体冰,常以雪花的形式存在。雪是由小的冰颗粒物构成,是一种颗粒材料(英语:granular material),它的结构开放,因此显得柔软。因为气温和湿
  • EINECS欧盟编号(EC Number)是一套在欧盟通用的化学品编号,由形如NNN-NNN-R的七位数字组成。欧盟编号列表由三部分演化而来:随着欧洲化学品管理局的运作,新的欧盟编号已经开始发放。关于
  • 符箓符箓是符和箓的合称,也称符咒、符令、符文、符书、符术、符篆、符图、符纸、甲马、灵符。按《说文解字》:符者信也。按《云笈七签》:箓者指戒箓情性。符指书写于纸、帛上的笔画
  • 东风-31东风-31(DF-31,北约代号:CSS-10),是中华人民共和国研制的一种公路机动型三级固体推进剂洲际弹道导弹;包括东风-31、东风-31A(甲)、东风-31AG(甲改)增强型三种型号。东风-31基本型
  • 联鸟龙联鸟龙属(学名:Ornithodesmus)是一属小型的虚骨龙类恐龙,生存于1亿3000万年前的英格兰。联鸟龙的化石是一根像鸟类的荐骨(编号BMNH R187),最初被认为是属于翼龙目的。后来有很多翼
  • 巨大血小板综合症巨大血小板症候群(英语:giant platelet syndrome),又称为伯纳德-苏里尔症候群(Bernard–Soulier syndrome),是一种罕见的血小板异常性疾病,为常染色体隐性遗传。发病率仅百万分之一,大
  • 氟甲烷0.557 g/cm3(25°C气体,饱和蒸气压)氟甲烷,也称为甲基氟、氟利昂41、HFC-41,其化学式为CH3F,在常温常压下是无毒、可液化的可燃气体,是甲烷的一氟取代物。氟甲烷用在半导体及电子
  • 流浪动物之家基金会财团法人流浪动物之家基金会是台湾的动物保护组织,1996年由汪丽玲成立。协会在新北市贡寮区设有保育场收容流浪狗。创办人汪丽玲女士为第二届中国小姐冠军。她最初在1987年与
  • 德川茂承德川茂承(1844年3月1日-1906年8月20日),日本幕末大名、纪州藩第14代及最后一代藩主,是第8代藩主德川重伦的弟弟松平赖谦的曾孙。德川茂承在天保十五年(1844年)生于江户屋敷(日语:江戸
  • 胡戈·埃德曼胡戈·埃德曼(德语:Hugo Wilhelm Traugott Erdmann,1862年5月8日-1910年6月25日)是一位德国化学家,他和他的博士导师雅各布·福尔哈德(Jacob Volhard)共同发现了Volhard–Erdmann环