鸽巢原理

✍ dations ◷ 2025-11-29 12:06:41 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 王 水王水(1942年4月12日-),空间物理学家。生于江苏南京。1961年毕业于南京大学气象系。1993年当选为中国科学院院士。中国科学技术大学教授,中国地球物理学会理事长。曾任中国科技大
  • 谢希谢希(英语:Salitis),古埃及第十五王朝首任国王。为西克索斯人首领,西克索斯人是青铜器时代巴勒斯坦入侵者,他们逐渐侵袭埃及,强占王位。占领下埃及与中埃及,将上埃及由其诸侯来统治
  • 硫酰基尿素类硫酰基尿素类(英语:Sulfonylurea)衍生物是用于2型糖尿病的抗糖尿病药。主要作用是促进胰脏β细胞分泌胰岛素。硫酰基尿素类是由法国科学家Marcel Janbon和他的同事们发现的,当他
  • 卡斯特勒阿尔弗雷德·卡斯特勒(法语:Alfred Kastler,1902年5月3日法国盖布维莱尔 - 1984年1月7日),法国物理学家,1966年获诺贝尔物理学奖。1901年:伦琴 / 1902年:洛伦兹、塞曼 / 1903年:贝
  • 圣安德烈亚斯断层圣安德列斯断层(英语:San Andreas Fault,又译圣安地列斯断层、圣安德烈亚斯断层、圣安德鲁斯断层),是北美洲一处频繁活动的断层。此断层约1300千米长,位于太平洋板块和北美洲板块
  • 阿拉姆语阿拉姆语(帝国亚拉姆语:ܐܪܡܝܐ‎;汉译为亚拉姆语、亞蘭語、阿拉姆語、阿拉米语、阿拉美语或阿辣米语,下称阿拉姆语)是闪米特语族(闪族)的一种语言,与希伯来语和阿拉伯语相近。阿
  • 扎邦猪齿鱼扎邦猪齿鱼(学名:),又名石老、四齿仔、西齿、扎邦寒鲷、札汶猪齿鱼,为辐鳍鱼纲鲈形目隆头鱼亚目隆头鱼科的其中一种,分布于菲律宾、印尼、澳洲西北部海域,体长可达45公分,栖息沙底质
  • 西斯 (星球大战)西斯(Sith)是《星球大战》系列中的黑暗自由战士。它亦可以指两种不同但相联系的群体,一般为人所知的是第一种,即一群与绝地同样使用光剑作武器及共同具有黑暗原力信仰的原力使用
  • 东北大米东北大米是一种粳稻,主要种植于中国黑龙江省、吉林省与辽宁省的广大平原地区,种植在富含矿物质的黑土地中,阳光雨露均足,又有来自松花江、嫩江与东辽河等水系的灌溉用水。东北大
  • 陶崇园事件陶崇园事件是发生于2018年3月的事件。因为长期受到导师压迫,武汉理工大学研究生三年级学生陶崇园(1992年3月28日-2018年3月26日)于2018年3月26日清晨跳楼自杀。微博ID为“陶崇