鸽巢原理

✍ dations ◷ 2025-12-10 03:17:22 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 日本漫画日本漫画(日语: 漫画/マンガ Manga ?)指日本于18世纪以后从12世纪戏画(戯画/ぎが Giga ?)延伸发展出的视觉艺术,相当于英文的“Cartoon”,可参见“卡通”。当代日本漫画为故事连
  • Smartbooksmartbook是一种介于智能手机与上网本之间的移动设备。这个概念在2009年六月由高通公司发表。smartbook 通常使用 5-10 吋的屏幕,使用触屏或实体QWERTY键盘。它长期保持引导,
  • 拜科努尔发射场坐标:45°57′58″N 63°18′28″E / 45.96611°N 63.30778°E / 45.96611; 63.30778name = 'Aero', description = '航空太空科技(航空航天科技)', content = {{ type = 'text
  • 雩桂片本文属于客家系列的一部分雩桂客语,或称客家语于桂片,是汉语族客家语的一个支系,主要分布在中国江西省西南部及湖南省东部地区。对于客家语的划分一般有两个版本,而此片在这两个
  • 红血球浓厚液红血球浓厚液(英语:Packed red blood cells),意即输血中所分离出来的红血球,通常不是用于贫血症状就是当血红蛋白低于 70 g/L(7 g/dL)时使用。一单位的红血球浓厚液可以将血红蛋白
  • 爱屋吉屋郭晓东、陈慧恬、谢承伟、 萧丽玲、蔡昕乐、温绍平、 《爱屋吉屋》(英语:),马来西亚八度空间时装剧,制作单位为新传媒制作(马来西亚)有限公司,由郭晓东、陈慧恬、谢承伟、萧丽玲、蔡
  • 蒋介卿蒋介卿(1875年1月3日-1936年12月27日),名锡侯,字介卿,又字瑞生,号萧绪,别号前安,谱名周康,以字行。浙江奉化人,蒋介石异母兄。出身弟子员,曾任法官、县长、海关监督、浙江省政府委员等。
  • 黄君璧黄君璧(1898年11月12日-1991年10月29日),原名允瑄,本名韫之,号君璧、君翁,晚号米寿老人,广东南海禄舟人,当代国画大师。与张大千、溥心畬以“渡海三家”齐名。1898年(光绪二十四年)9月2
  • 朴志晟志晟(韩语:지성;英语:Jisung,2002年2月5日-),本名朴志晟(韩语:박지성;英语:Park Jisung),出生于韩国首尔特别市江北区,为SM娱乐旗下NCT的成员。2016年8月,以子团NCT Dream出道,是SM旗下最小年
  • LIM结构域LIM结构域(英语:LIM domain)是一种蛋白质结构域,由两个疏水氨基酸残基连接两个锌指结构组成,其命名来自于最早发现这一结构域的三种蛋白(Lin11, Isl-1 & Mec-3)的首字母。LIM结构