鸽巢原理

✍ dations ◷ 2025-12-02 11:56:42 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 标准大气压标准大气压是压强的一种非国际单位制单位,单位符号atm。其具体数值有不同的定义。标准大气压一般定义为101.325kPa。国际民航组织、国际标准化组织等组织使用这一数值。在195
  • abbr class=abbr title=R33: 有累积毒性的危险品R33/abbr警示性质标准词(英语:Risk Phrases,简写:R-phrases)是于《欧联指导标准67/548/EEC 附录III: 有关危险物品与其储备的特殊风险性质》里定义。该列表被集中并再出版于指导标准2001/
  • 刘侠刘侠(1942年4月12日-2003年2月8日),已故中华民国作家,北投国小毕业。据其自述,因家乡在陕西省扶风县杏林镇(今属陕西省宝鸡市),也为了纪念自己一辈子与医院结下的“不解之缘”(因为杏
  • 潘诺尼亚平原潘诺尼亚平原(德语:Pannonische Tiefebene),又称喀尔巴阡盆地(匈牙利语:Kárpát-medence),是欧洲一大平原,分属匈牙利、奥地利、克罗地亚、捷克、斯洛伐克、塞尔维亚和罗马尼亚。周
  • 不见不散不见不散可以指:
  • 皮茨尔瓦尼亚县 (弗吉尼亚州)皮茨尔瓦尼亚县(Pittsylvania County, Virginia)是美国维吉尼亚州南部的一个县,南邻北卡罗莱纳州。面积2,533平方公里,是该州面积最大的县。根据美国2000年人口普查,共有人口61,
  • 伊莎贝尔·哈克伊莎贝尔·哈克(土耳其语:Isabelle Haak,1999年7月11日-),瑞典女子排球运动员,司职接应二传手。现时效力于土超豪门球队瓦基弗银行女排俱乐部。哈克在2014年开始成为瑞典国家女子排
  • 蒙茅斯 (消歧义)蒙茅斯可以指:
  • 况叔祺况叔祺,字吉夫,生卒年不详,江西高安县人,明朝政治人物,同进士出身。况一经之子。嘉靖二十九年(1550年)庚戌科殿试金榜第三甲赐同进士出身第49名,初授刑部主事,历官贵州副使致仕,翰林院
  • 布吉站布吉站是深圳地铁3号线及5号线的换乘站,位于中国广东省深圳市龙岗区布吉街道与龙岗大道近规划中布吉综合客运枢纽东广场,同时亦连接广深铁路和京九铁路的深圳东站。3号线部分