鸽巢原理

✍ dations ◷ 2025-06-08 21:21:49 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • ssRNA(-)核糖核酸病毒(英语:RNA virus),又称RNA病毒,其遗传物质为RNA,这些核糖核酸通常是单链RNA(ssRNA),但是也可能是双链RNA(dsRNA)。由RNA病毒感染造成的著名人类疾病包括艾滋病(AIDS)、埃博
  • 接合生殖水绵是水绵属(学名:Spirogyra)绿藻门物种的总称,又名石衣、水衣、水苔、石发、陟厘、侧梨、水青苔,是一种普遍生活在淡水里的真核多细胞藻类,因体内含有1-16条带状、螺旋形的叶绿体
  • Cu(IOsub3/sub)sub2/sub碘酸铜是铜的碘酸盐,目前仅已知二价的化合物。向硝酸铜溶液中加入碘酸,得到一水合物晶体:碘酸铜一水合物(Cu(IO3)2·H2O)在240°C发生脱水,生成无水物。无水物继续加热至470°C,不
  • span style=color: white;公务员法庭/span本文是 欧洲联盟的政治与政府 系列条目之一欧洲联盟的公务员法庭(英语:Civil Service Tribunal)为欧洲联盟法院中的专门法庭之一,创设于2005年12月2日。根据尼斯条约的规定,就某
  • 七姊妹学院七姊妹学院(英语:Seven Sisters)是形容美国东北部地区7所文理学院间松散关系的一个称呼,因这些学院曾经都是女子学院而得名。7所学院均成立于19世纪,至今仍有5所学院延续这种教育
  • 李冲 (唐朝)李冲(7世纪?-688年),唐朝宗室,唐太宗的孙子,越王李贞的长子,封琅玡王。李冲好学,勇而有才,累迁博州刺史。688年,黄国公李譔伪造唐睿宗李旦给李冲下的诏书,皇帝已经被武太后软禁,要宗室一
  • 汽化膨胀比液化或低温(英语:cryogenic)物质的膨胀比是指在一定量物质在其液体时体积,和其在室温、一大气压力下,气体时体积的比。若封闭容器中装有液化物质,而有相当多的液体蒸发,所产生的压
  • 克普坐标:58°19′36″N 25°18′23″E / 58.32667°N 25.30639°E / 58.32667; 25.30639克普(爱沙尼亚语:Kõpu),是爱沙尼亚的城镇,位于该国南部,由维尔扬迪县负责管辖,是克普乡的首府,
  • 扯根菜科扯根菜属 扯根菜科只有1属2种,分布在北美洲东部和东亚,中国有1种—扯根菜( Pursh. ),分布在除西北以外的所有地区。本科植物为多年生直立草本,叶互生,有锯齿;有地下茎;花没有花瓣;果实
  • 吕叔湘吕叔湘(1904年12月24日-1998年4月9日),谱名锺湘,学名湘,字叔湘,以字行,男,江苏丹阳人,中国语言学家,近代汉语学的拓荒者和奠基人。其堂兄为画家吕凤子,又与佛学家吕澂同族。吕叔湘生于在