鸽巢原理

✍ dations ◷ 2025-11-26 10:30:13 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 电火花电火花加工(英语:electrical discharge machining,EDM),是一种借由放电产生火花,使工件成为所需形状的一种制造工艺。介电质液体分隔两电极并施以电压,产生周期性快速变化的电流放
  • 弗雷德里克·巴特莱特弗雷德里克·巴特莱特爵士(英语:Sir Frederic Charles Bartlett,1886年10月20日-1969年9月30日),英国心理学家,剑桥大学实验心理学教授(从1931年到1951年退休)。1944 年,他和肯尼思·
  • 新左营车站台铁:岛式月台三座(第一月台仅使用一侧)高铁:岛式月台三座 捷运红线:台湾高铁左营站、台湾铁路管理局新左营站、高雄捷运左营(高铁)站,是不同铁路客运系统业者对自身所营运,但在同一
  • 火卫一火卫一,又称为“福波斯”(英语:Phobos;希腊语:Φόβος;系统名称:Mars I),是火星的两颗自然卫星中,距离火星较近且较大的一颗,平均半径为11.1km,是另一颗卫星火卫二的1.8倍。火卫一的
  • 拉腊马里亚诺·何塞·德·拉腊因(Mariano José de Larra)(1809年3月24日-1837年2月13日)是西班牙浪漫主义作家,最出名的是杂文。他最后自杀身亡。马里亚诺·何塞·德·拉腊因的作品往
  • 光明会光明会(拉丁语:Illuminati)是1776年5月1日启蒙运动时成立于巴伐利亚的一个秘密组织。该组织经常被各种阴谋论指控参与控制全世界的事务,透过掌握货币发行权、策划历史事件(如法国
  • Kdenetworkkdenetwork 是一个网络相关应用程序的软件包。 Akonadi · Decibel · Flake · KConfig XT · KJS · KDOM · KHTML · KIO · Kiosk · KIPI · KParts · Kros
  • 陈燕燕陈燕燕可以指:
  • 阿纳斯塔西娅·克尼亚泽娃阿纳斯塔西娅·帕夫洛夫娜·克尼亚泽娃(俄语:Анастасия Павловна Князева,2011年7月1日-),俄罗斯女童星。2011年生于莫斯科。从两岁半开始就喜欢镜头和被
  • 蒂黑马县蒂黑马县(英语:Tehama County)是美国加利福尼亚州的一个县,县治雷德布拉夫。根据美国人口调查局2000年统计,共有人口56,039,其中白人占84.79%、印第安人占2.1%。‡该聚居地有部分