鸽巢原理

✍ dations ◷ 2025-11-29 18:40:59 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 与格与格(拉丁语:casus dativus ,英语:dative case,缩写: .mw-parser-output .smallcaps-all{font-variant:small-caps;text-transform:lowercase}.mw-parser-output .smallcaps-all *
  • 同量素同量素是质量数相同,但质子数不同的原子核。同量素必然是不同的元素。例:Cu (原子序29) 和 Zn (原子序30) 具有质量数同为65的同量素。 理论上,两个以上的同量素不会都是稳定的
  • 马来统治者最高元首后东姑阿兹纱阿蜜娜(英语:Tunku Azizah Aminah Maimunah)副最高元首苏丹纳兹林沙(马来语:Sultan Nazrin Muizuddin Shah ibni Sultan Azlan Muhibbuddin Shah)副首相(不设
  • 真空泵真空泵是制造真空的一种机械,它可以把一个密闭的或半密闭的空间中空气排出或者吸收,达到局部空间的相对真空。常见的真空泵有往复式真空泵、水环泵、分子泵、旋片式真空泵、活
  • 影子内阁政治主题女王陛下最忠诚的影子内阁(英语:Her Majesty's Most Loyal Opposition),由在野党高级党员组成,他们会批评执政党对应官员,提出本党政策,迫使执政党为施政辩护。自2010年5月
  • 程志程志(Cheng Zhi)是美国电视连续剧《24》的一个角色。在剧中,他是中华人民共和国驻洛杉矶总领事馆保安主管以及一名特工。程志于第四季担任中华人民共和国驻洛杉矶领事馆保安主
  • 鳐科见内文。鳐科(学名)是鳐形目的典型科,本科鱼身体扁平,胸鳍宽大,腹鳍有一个明显的缺刻,几乎将腹鳍分为两叶,两个背鳍非常小,紧靠尾部,尾细小,通常无尾鳍,如有也没有鳍条支持。鳐科鱼生活
  • 国家地理林业信息研究所国家地理林业信息研究所(法语:Institut national de l’information géographique et forestière)是法国的一个公共管理机构,负责管理法国以及其海外属地的地理资讯。在2012年
  • 土光敏夫土光敏夫(日语:土光 敏夫/どこう としお ;1896年9月15日-1988年8月4日),日本昭和时代企业家,工商界人士。石川岛播磨重工业社长、东芝社长、日本经济团体联合会第4代会长。
  • 周易参同契《周易参同契》又名《参同契》,是一本讲炼丹术著作,被称为“万古丹经王”。作者是东汉的魏伯阳。《周易参同契》的书名中“参”音cān(ㄘㄢ),指参同“大易”、“黄老”、“炉火