鸽巢原理

✍ dations ◷ 2025-04-26 11:57:54 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 尼德兰人的血脉《尼德兰人的血脉》(荷兰语:Wien Neêrlands Bloed)又译《荷兰人血统》,是荷兰1815年至1932年间的国歌。1815年,比利时与荷兰合并为荷兰王国,并开始探讨征集新国歌。早在荷兰共和
  • 德布罗意-玻姆理论一般认为,德布罗意-玻姆理论是一种量子力学诠释。亦称因果性诠释(Causal Interpretation)、存在性诠释(Ontological Interpretation)、玻姆诠释、玻姆力学(Bohmian Mechanics),有时
  • 贺龙体育文化中心贺龙体育文化中心(新世纪文化中心)位于湖南省长沙市城南的天心区内,由芙蓉中路、劳动西路、白沙路与城南西路合围的大片区域,总面积约为70公顷。该中心于2000年12月28日开工,2003
  • 前件前件(antecedent),亦称前提,是假言命题的前半部分。例子:这是假言命题的标准逻辑公式。在这种情况下,前件是P。X是人是这个命题的前件。这里的人类已经在月亮上行走是前件。
  • 共生虫属共生虫属(学名:)是一类微小的水生动物,于1995年由莱因哈特·克里斯滕森(英语:Reinhardt Kristensen)与彼得·方奇(英语:Peter Funch)发现,。是环口动物门(Cycliophora,又名微轮动物门)、真
  • 2018年美国网球公开赛2018年美国网球公开赛(2018 US Open)是第138届美国网球公开赛,赛事于8月27日至9月9日在美国网球协会比利·简·金网球中心举行。拉斐尔·纳达尔和斯洛恩·斯蒂芬斯分别是该赛事
  • Not Alone《Not Alone》是韩国Pop Dance组合SS501成员朴政珉的个人首张单曲,亦是SS501中首位单飞后发行的首张单曲。音源于2011年1月20日通过各音乐网站公开。整张单曲由明星制作人“
  • 荷式松饼荷式松饼、荷兰松饼、或荷兰华夫饼(荷兰语:Stroopwafels, pronunciation 帮助·信息,翻译成英文则为Syrup waffles)是由两片薄且脆的松饼,夹着含有红糖的麦芽糖浆。最早出现在荷
  • 毛毛雨 (消歧义)毛毛雨可以指:
  • 古典 (鸡尾酒)扭过的橘子或马拉斯奇诺樱桃古典是一杯用捣棒混合方糖和苦酒, 并且加入威士忌或者在不常见做法中加入白兰地, 之后用扭过的橘子或马拉斯奇诺樱桃点缀的鸡尾酒。传统上是用岩