鸽巢原理

✍ dations ◷ 2025-12-07 19:59:00 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 860110 数学 120 信息科学与系统科学 130 力学 140 物理学 150 化学 160 天文学 170 地球科学 180 生物学210 农学 220 林学 230 畜牧、兽医科学 240 水产学310 
  • 牟比士症候群牟比士症候群(Möbius syndrome,或拼做Moebius)是一个很罕见的遗传性神经失调疾病,明显的特征是颜面神经麻痹以及没办法控制眼球的移动。大部分刚出生患有牟比士症候群的人都伴
  • 吴骞吴骞(1733年-1813年),字槎客,又字葵里,号兔床,海宁新昌里人。雍正十一年(1733年)生,乾隆时贡生,陈鳣年轻时曾随其讲训诂之学。笃嗜典籍,家有“拜经楼”,藏书五万卷,“皆节衣缩食,竭平生之精
  • 格奥尔格·冯·霍茨布林克出版集团霍尔茨布林克出版集团(德语:Verlagsgruppe Georg von Holtzbrinck),于1948年成立,总部设于斯图加特,是德国著名的出版集团,拥有麦克米伦出版公司100%股权,是德国时代周报(英语:Die Zei
  • 南康区南康区是中华人民共和国江西省的一个市辖区,现是隶属于赣州市。南康区地处于江西省南部,距离赣州市中心城区约半小时车程,因“地接岭南,人安物阜”而得名。原南康市总面积1800平
  • 小儿多系统发炎症候群小儿多系统发炎症候群(Pediatric Multisystem Inflammatory Syndrome) 是2020年定义的新病症,主发在五岁以下儿童,主要症状为全身性发炎 、发烧和器官衰竭,其他可能症状包括结膜
  • 伊丹康直伊丹康直 (1522-1596.8.14),日本战国时代武将。幼名千代松,初名伊丹雅胜。1529年居城被攻破,父亲战死,千代松尚年幼,随外祖父出逃至骏河被今川义元收留。义元战死后,伊丹康直被提拔
  • 山口二矢山口二矢(1943年2月22日-1960年11月2日),日本学生运动家及政治人士,右翼团体大日本爱国党成员。因刺杀左派领导人浅沼稻次郎而闻名。1960年,日本社会党党首浅沼稻次郎竞选首相,极受
  • 太阳辐射压力太阳辐射压力是太阳辐射抵达物体时,施加在该物体的压力,这是天文学上的现象。在太空动力学,太阳辐射压力是非常有趣的,它也是轨道摄动的一个来源。这种扰动的力量可以简单的表示
  • 卡里古拉 (游戏)《卡里古拉》(日版名:Caligula -カリギュラ-,英文版名:The Caligula Effect)是Aquria(日语:アクリア)为PlayStation Vita平台所开发的一款电子角色扮演游戏,于2016年6月由FuRyu(日语:フ