鸽巢原理

✍ dations ◷ 2025-11-24 07:03:12 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • Logit模型罗吉斯回归(英语:Logistic regression,又译作对数几率回归、罗吉斯回归)是一种对数几率模型(英语:Logit model,又译作逻辑模型、评定模型、分类评定模型)是离散选择法模型之一,属于多
  • 退伍军人管理局美国退伍军人事务部 (英语:United States Department of Veterans Affairs,缩写:VA),成立于1989年,是为美国退伍军人及家属提供服务的内阁部门。1930年7月21日,美国联邦政府成立退伍
  • 分子动力学分子动力学是一套分子模拟方法,该方法主要是依靠计算机来模拟分子、原子体系的运动,是一种多体模拟方法。通过对分子、原子在一定时间内运动状态的模拟,从而以动态观点考察系统
  • 沙门沙门(梵文:श्रमण śramaṇa;巴利语:शमण samaṇa),又译为桑门、丧门、娑门、沙门那、沙迦懑曩、室摩那弩、舍罗摩弩,意译为道士、道人、贫道等,意为“勤息”、“止息”等意,原
  • 宜章县宜章县位于中国湖南省南部,为郴州市辖县。地处南岭山脉中段,骑田岭南麓。县域总面积2,142.7平方公里,位居全省各县市的第42位;全县常住人口579,565人(2010普查),居全省第43位。2011
  • 各国萤石产量列表这是一个2006年的各国萤石产量列表,主要基于2008年7月 英国地质调查局 的数据。
  • 拉脱维亚城市列表在拉脱维亚有9个城市(拉脱维亚语:Republikas pilsētas)和67个城镇(拉脱维亚语:Novada pilsētas)。根据拉脱维亚法律,城镇是指为商业和文化中心的定居点,而且拥有发达的基础设施工
  • 普拉提亚战役普拉提亚战役(Battle of Plataea)是波斯第二次入侵希腊的战争中最后一场战役。时值公元前 479 年,发生于普拉提亚城(希腊维奥蒂亚地区的一个城市)附近,对阵双方分别是希腊城邦联合
  • 周祖衔周祖衔(?-1853年),字鹤侪,河南商城(现属安徽金寨县汤家汇镇)人,祖籍江西婺源,清朝官员。道光十八年(1838年)戊戌科进士。选翰林院庶吉士,散馆改知县。官至湖北武黄水利同知。咸丰二年十二
  • 马尔代夫国旗马尔代夫国旗启用于1965年7月25日。是一面绿地旗帜 (代表岛屿上的棕榈树),外围红框 (象征过去、现在与将来为国不惜牺牲的英雄)。中为一白新月,开口向右,象征伊斯兰信仰。1796—190