鸽巢原理

✍ dations ◷ 2025-11-30 14:21:28 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 宋家树宋家树(1932年3月21日-),中国金属物理学家。原籍安徽舒城。生于湖南长沙。1954年毕业于东北人民大学物理系,1958年该校研究生毕业。中国工程物理研究院科技委委员。1993年当选为
  • 8088Intel 8088 是一个 Intel 以 8086 为基础的 微处理器,拥有 16 比特 寄存器 和 8 比特外部 数据总线。这是原本 IBM PC 上所使用的处理器。8088 使用 8 比特的设计,所针对的是
  • 富兰克林·马赛厄斯富兰克林·汤普森·马赛厄斯(英语:Franklin Thompson Matthias,1908年3月13日-1993年12月3日)是一位美国的土木工程师(英语:civil engineer),在二战期间主持建造了曼哈顿计划的核心设
  • 深圳市体育设施列表深圳是中国的体育强市之一,体育设施非常完善,田径场、游泳馆、自行车赛场、手球馆、舞蹈馆、曲棍球场、水上运动场等非常齐全。
  • 刘伯温传说刘基像,顾见龙绘道家系列条目刘基(1311年7月1日-1375年5月27日),字伯温,浙江省青田县(今文成县)人,祖籍陕西保安(志丹),南宋抗金将领刘光世的后人。元末明初军事家、政治家及诗人,通经史
  • WB电视网WB电视网(英语:The WB Television Network)是美国的一家电视台。于1995年1月11日开始播出。由华纳兄弟公司经营。2006年1月24日,CBS集团与华纳兄弟公司宣布将在秋季开播新的电
  • 三亿日元抢劫案三亿日元抢劫案是1968年12月10日发生在日本东京都府中市的一次现金抢劫案,至今犯人尚未捕获。此案已经过了追诉期。犯人作案手法巧妙成为日本历史上最神秘的案件之一,被人们视
  • 丽莎·蓝道尔丽莎·蓝道尔(英语:Lisa Randall,1962年6月18日-),美国理论物理学家,粒子物理学和宇宙学的权威专家,女性主义者,美国国家科学院与美国文理科学院院士与美国物理协会会员,为哈佛大学理
  • 奥登纳图斯奥登纳图斯(英语:Odaenathus),(?-267年)。罗马帝国殖民地巴尔米拉的邦君。曾于公元260年效忠于罗马帝国统治者瓦莱里安。并且由于在同年击败波斯人以及罗马帝国僭位者而受封为“东方
  • 费尔弗里德 (霍亨索伦)费尔弗里德·马克西米利安·皮乌斯·迈恩拉德·玛利亚·胡贝特·米夏埃尔·尤斯蒂努斯(Ferfried Maximilian Pius Meinrad Maria Hubert Michael Justinus,1943年4月14日-),出生