鸽巢原理

✍ dations ◷ 2025-12-01 08:49:52 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 帕罗西汀帕罗西汀(Paroxetine)是一种选择性5-羟色胺再吸收抑制剂(SSRI)型的抗抑郁药,其药物形态为盐酸帕罗西汀(Paroxetine hydrochloride),商品名为“赛乐特”(Seroxat)。在临床上常用于社交
  • 1,2-二甲基肼1,2-二甲基肼(英语:1,2-Dimethylhydrazine)又称为均二甲肼(英语:symmetrical dimethylhydrazine,缩写SDMH),是二甲基肼的其中一种,也是偏二甲肼的同分异构体。它是一种具有烷化剂作用
  • 巢是动物居住的地方,通常以地洞、树洞、泥土、岩石或建筑物之掩蔽为巢;或以有机物质如小树枝、草、叶和唾液构成,随人类物质利用产生的材料也在利用的范围之内,如绳线、塑胶、布
  • 清醒梦清醒梦(英语:lucid dream)是在意识清醒的时候所作的梦,又称作清明梦。清醒梦跟白日梦并不相同,清醒梦是做梦者于睡眠状态中保持意识清醒;白日梦则是做梦者于清醒状态中进行冥想或
  • GFPGFP可以指:
  • Taxaceae红豆杉科是松柏目下的一个科,其中包括7个属,约30种植物。红豆杉科物种多是分枝的小乔木和灌木。是常绿树种,叶螺旋状排列,呈线形至披针形,底面有淡绿色或白色的气孔带。雌雄异株,
  • 《华盛顿月刊》《华盛顿月刊》(Washington Monthly)是一份总部位于美国华盛顿特区的双月刊非营利杂志,主要刊登关于美国政治和美国政府的文章。该杂志由查尔斯·彼得斯成立于1969年,起先是月刊
  • 语言系属分类语言系属分类(英语:Language family)是指根据语言的演化关系,对语言进行分类的方法,具有相同祖先的语言被归为一类,类似生物分类法。分类依据为各语言语音、词汇、语法之间的对应
  • KODA KUMI LIVE TOUR 2015 〜WALK OF MY LIFE〜 supported by Mercedes-Benz《KODA KUMI LIVE TOUR 2015 〜WALK OF MY LIFE〜 supported by Mercedes-Benz》为日本歌手倖田来未于2015年于日本举办的巡回演唱会。
  • 龙门山镇龙门山镇,是中华人民共和国四川省成都市彭州市下辖的一个乡镇级行政单位。2019年12月,撤销小鱼洞镇,将其所属行政区域划归龙门山镇管辖,龙门山镇人民政府驻复兴路331号。龙门山