鸽巢原理

✍ dations ◷ 2025-12-05 18:54:36 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 原口动物原口动物(学名:拉丁语:Protostomia),又名前口动物或旧口动物,有完整的消化道。胚胎时期的原口会发展为成体的口,而肛门则是另外形成的。蜕皮动物(Ecdysozoa)和螺旋动物(Spiralia)都属于
  • 三立新闻三立新闻台(英语:SET News Channel),简称“三立新闻”,是台湾三立电视旗下的电视新闻频道,1998年3月3日开播,是台湾多家24小时即时播出的新闻频道之一。原名SET电视台,后改为SETN,200
  • 阿利效应阿利效应是一个在生物学中的现象,它反映了在一个种群中的种群规模、密度和平均个体适应度(通常被测量作人均人口增长率)具有相关联系的效应。虽然当时阿利效应这个概念还没有被
  • span class=chemf style=white-space:nowrap;Csub10/sub正癸烷是化学式为CH3(CH2)8CH3的烷烃,总共有136种异构体,若不计立体异构则为75个,全都是可燃液体。癸烷是汽油的组分之一。与其他烷烃类似,癸烷是非极性分子,不易溶于水之类的极
  • L03A·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码L03(免疫促进药)是解剖学治疗学及化学分类系统的一个药物分组,这是由世界卫生组织药物统计方法整合中心(The WHO Collabor
  • 马蹄马脚蹄,通常称为马蹄,是马的脚部长出来的蹄,正如人体长出脚甲一样,用以保护马的脚部。人工驯化的马匹,现多用作赛马用途。练马师为尽力保护马原生的马蹄,不让马儿因为长期奔跑而令
  • 圣玛格丽特教堂坐标:51°30′00″N 0°07′37″W / 51.50000°N 0.12694°W / 51.50000; -0.12694威斯敏斯特圣玛格丽特教堂(St. Margaret's Church, Westminster Abbey)是一座英国圣公会教堂
  • 大众传播大众传播(Mass communication)是一种信息传播方式,利用媒体(如声音、文字、影像等)将讯息以某种形式传递给人群。实作上的操作请见传播媒体。根据Gerhard Maletzke的定义,大众传播
  • 多四季论《多四季论:揭开大自然深层王国的奥秘》是湖北工程师董妙先的一部著作,曾被新华社、《光明日报》、《科技日报》等50多家报刊广泛报道。作者自称其理论是遵循如下“科学事实”
  • 邓旭邓旭,字元昭,江南寿州(今属安徽省)人。清初政治人物。邓旭于顺治四年(1647年)中式丁亥科三甲进士。选庶吉士,散馆授检讨,官至甘肃洮岷道。著有《林屋诗集》。