鸽巢原理

✍ dations ◷ 2025-11-11 14:06:03 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 急性急性(Acute)在医学中指发作迅速持续时间可能也较短的病症。有时侯,急性与慢性用来区分不同的病,比如急性白血病和慢性白血病;有时候,急性用来强调发病突然,如急性心肌梗塞。医学征
  • 分权权力分立(Separation of powers)是一个政治学说,其主张政府的行政、立法与司法职权范围要分明,以免滥用权力。此学说起源可追溯至古希腊,而其后被英国与法国的哲学家进一步发展。
  • 核酸双螺旋在分子生物学中,双螺旋是指由核酸(如DNA和RNA)的双链分子所形成的结构。核酸复合物的双螺旋结构是它的二级结构的结果,并且是确定其三级结构的基本组成部分。这个术语因詹姆斯·
  • 1445年约前1445年,古埃及法老图特摩斯三世打败了米坦尼国王,夺占米坦尼王国位于幼发拉底河西岸的土地。
  • 弧长曲线的弧长也称曲线的长度,是曲线的特征之一。不是所有的曲线都能定义长度,能够定义长度的曲线称为可求长曲线。最早研究的曲线弧长是圆弧的长度。为了计算圆周的长度,数学家发
  • 逆时针方向以逆时针方向运行指依从时针移动的相反方向(如图),即可视为由左上方向下,然后转向右,再回到上。也就是说逆时针方向就是顺时针方向的相反,也是镜射变换后的结果,故逆时针方向的反方
  • 氯化铋氯化铋化学式BiCl3,常温下是易潮解的白色晶体。与离子晶体三氟化铋不同,在气相或晶体中,氯化铋分子构型都为三角锥形,可从价层电子对互斥理论(VSEPR)解释。是常用的提供Bi3+离子的
  • 波雅尔波雅尔(保加利亚语:боляр / болярин;乌克兰语:буй / боярин;俄语:боя́рин,罗马化:boyarin,IPA:.mw-parser-output .IPA{font-family:"Charis SIL","Doulo
  • 我的妹妹是“大阪大妈”《我的妹妹是“大阪大妈”》(日语:僕の妹は「大阪おかん」),是日本BS朝日于2012年12月21日开始放送的日本深夜动画,共12集。动画原作是中经出版发行的介绍日本各地风俗的“规则系
  • 韦利斯克区坐标:61°04′N 42°06′E / 61.067°N 42.100°E / 61.067; 42.100韦利斯克区(俄语:Вельский район),是俄罗斯的一个区,位于该国西北部,由阿尔汉格尔斯克州负责管辖,