鸽巢原理

✍ dations ◷ 2025-08-05 19:02:12 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 统一帕金森病评定量表统一帕金森氏症评定量表 (英文全称为The unified Parkinson's disease rating scale,也被称为UPDRS评分量表或UPD评分量表)是用来纵向衡量帕金森氏症发展情形的估量表。 UPD评
  • 莪相莪相(Ossian)是传说中3世纪时爱尔兰英雄,吟游诗人;被指为1760年起苏格兰诗人詹姆斯·麦佛森 (James Macpherson) 发表一系列史诗的作者。当代评论家对于作品真实性的看法有分歧
  • 奥托·冯·居里克奥托·冯·居里克(Otto von Guericke,1602年11月20日-1686年5月11日)德国物理学家、政治家,曾于1646年至1676年间任马德堡市市长。他于1650年发明了活塞式真空泵,并利用这一发明于
  • 小满数据来源:喷气推进实验室线上历书系统小满,是二十四节气之一,每年5月20-22日之间,太阳到达黄经60°时开始。《月令七十二候集解》:“四月中,小满者,物至于此小得盈满。”这时北方夏
  • Bonaparte夏尔·吕西安·儒勒·劳伦·波拿巴,第二代卡尼诺和穆西格纳诺亲王(法语:Charles Lucien (Carlo) Jules Laurent Bonaparte, 2nd Prince of Canino and Musignano,1803年5月24日-1
  • 2018年亚洲运动会塔吉克斯坦代表团2018年亚洲运动会塔吉克斯坦代表团是塔吉克斯坦所派出的2018年亚洲运动会代表团。这是塔吉克斯坦第七次参加亚洲运动会。代表团开幕式旗手是摔跤运动员Rustam Iskandari。塔
  • 卢英 (江陵)卢英(1894年-1950年),字楚僧,湖北江陵人。卢英毕业于保定陆军军官学校第二期步科。毕业后,曾担任过湖北第一旅连长,学兵保定军校步兵科队长,四川军官教育团教官,陆军第一师工兵营营长
  • 埃登巴赫大街站埃登巴赫大街站(德语:U-Bahnhof Aidenbachstraße)是慕尼黑地铁3号线位于慕尼黑塔尔基兴-上森德灵-福斯滕里德-菲尔斯滕里德-索恩的一座车站。 维基共享资源中与埃登巴赫大街站
  • 西莫尼峰坐标:47°04′21″N 12°15′36″E / 47.0725°N 12.26°E / 47.0725; 12.26西莫尼峰(德语:Simonyspitzen),是奥地利的山峰,属于维内迪杰山脉的一部分,海拔高度3,473米,该山峰每年平
  • 红刺露兜树红刺露兜树(学名:)为露兜树科露兜树属下的一种常绿乔木。原产于非洲马达加斯加岛等地。因树型优美特殊,许多国家地区都有栽种,是有名的热带观赏树种,同时也是一种经常做为样本的树