鸽巢原理

✍ dations ◷ 2025-11-25 23:55:35 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 化学生物学化学生物学(英语:Chemical Biology)是哈佛大学的斯图亚特·L·施莱伯等人所提倡,利用分子生物学的手法,搭配有机化学的方式,探讨细胞内核酸或是蛋白质等生物体内分子的功能或是反
  • Johns Hopkins University Press约翰斯·霍普金斯大学出版社(英语:Johns Hopkins University Press,也由以约翰霍普金斯大学出版社或JHUP的简称)是约翰斯·霍普金斯大学的出版部门。它始建于1878年,拥有在美国连
  • 解离常数在化学、生物化学及药理学中,解离常数(英语:dissociation constant, K d {\d
  • 塞林格杰罗姆·大卫·“J·D”·塞林格(英语:Jerome David Salinger,J. D. Salinger/ˈsælᵻndʒər/,1919年1月1日-2010年1月27日)是一位美国作家,以著作《麦田里的守望者》而闻名。塞
  • 台铁E200-E400型电力机车E200、E300、E400型电力机车,是台湾铁路管理局的六轴电力机车,目前仍是台铁局主线电力机车主力车型之一。台湾铁路管理局为因应十大建设的纵贯线铁路电气化,从美国GE运输公司(简
  • 赵可教赵可教(1531年-1590年),字心轩,四川省成都府温江县人,治《诗经》三房,年六十二岁中式万历二十年壬辰科第三甲第七十七名进士。癸巳正月初四日生,曾祖赵万里、祖赵本俊、父赵斌。中式
  • 绕口令绕口令(又称“拗口令”、“急口令”),是一种语言游戏,是将声调、韵母或声母容易混淆的文字编成句子,念起来有些拗口,而说快了容易发生错误。绕口令也是训练口才的一种方法,对有口吃
  • 弗雷德里克·亚瑟·伯里曼弗雷德里克·亚瑟·伯里曼(英语:Frederick Arthur Bridgman,1847年11月10日-1928年1月13日),美国东方主义画家,以绘有许多北非景色的画作而知名。赴法国求学时曾于布列塔尼钻研画作
  • 安东贞美安东贞美(1853年10月20日-1932年8月29日),饭田藩(今长野县)出身。曾任日本陆军士官学校校长,1915年以陆军大将身份,前往台湾担任台湾总督,为台湾日治时期第6任总督,成立“台湾劝业共进
  • 春香传 (1935年电影)《春香传》是一部1935年电影,亦是朝鲜半岛的首部有声电影。该片由朝鲜半岛早期电影人李弼雨和其弟弟李明雨合作完成,改编自朝鲜民间传说《春香传》。李明雨担任导演,李弼雨兼任