鸽巢原理

✍ dations ◷ 2025-12-03 01:49:58 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 斯瓦希里语斯瓦希里语(kiswahili),属于班图语族,是非洲语言使用人数最多的语言之一(5500万多人),和阿拉伯语及豪萨语并列非洲三大语言。斯瓦希里语是坦桑尼亚、肯尼亚、乌干达的官方语言,刚果
  • 训名训名,又称学名。有一些家庭的儿童,入学受教育时或会由父亲、老师或其他长辈,取一个“训名”,供老师称呼,有别于小名、表字。如《红楼梦》:“这薛公子学名薛蟠,表字文起。”《宋史》
  • N06AA·B·C·D·G·H·QI·J·L·M·N·P·R·S·VATC代码N06(精神兴奋药)是解剖学治疗学及化学分类系统的一个药物分组,这是由世界卫生组织药物统计方法整合中心(The WHO Collabor
  • Nasub5/subPsub3/subOsub10/sub三聚磷酸钠,化学式Na5P3O10。三聚磷酸钠是一种白色粉末,易溶于水,水溶液呈碱性,1%水溶液pH为9.7。有两种晶形,α型(高温型)和β型(低温型),两者化学性质相同,均可得到相同的水溶液和结晶
  • 国军退除役官兵辅导委员会国军退除役官兵辅导委员会(简称退辅会、辅导会)为中华民国专门处理退伍军人五大事项(就业、就学、就医、就养与服务照顾等)的机关。退辅会在台湾各地的所属机关有15所荣民医院(包
  • 北京烤鸭北京烤鸭,中国名菜,又名北京填鸭,是具有世界声誉的北京著名菜式,用料为优质肉食鸭北京鸭,果木炭火烤制,色泽红润,肉质肥而不腻。北京烤鸭分为“挂炉烤鸭”与“焖炉烤鸭”两大流派,而
  • 髋关节在脊椎动物解剖学中,髋关节(英语:hip,拉丁语:coxa)既可指代一个解剖学区域,亦可指代一个关节。髋关节区位于臀部外前侧,髂嵴(英语:iliac crest)内侧,覆盖了股骨大转子(英语:greater trocha
  • 托尔贝恩·贝里曼托尔贝恩·贝里曼(Torbern Bergman,1735年3月20日-1784年7月8日),瑞典化学家,矿物学家。1735年,出生于瑞典Katharinberg。17岁,进入乌普萨拉大学学习。后成为教授。1764年,成为瑞典皇
  • 弗朗齐谢克·贡戈尔弗郎齐歇克·贡戈尔(Franciszek Gągor,1951年9月8日-2010年4月10日),波兰上将,原波兰军队总参谋长,出生于新松奇附近的Koniuszowa。他于1970年代服役于第二坦克团,之后成为联合国行
  • 金阁寺 (小说)《金阁寺》为日本作家三岛由纪夫的小说作品,发表于1956年。全书以日本京都的金阁寺为背景。金阁寺本名为鹿苑寺,1394年由幕府将军足利义满建造,因为其金碧煇煌的外观,湖中倒映出