鸽巢原理

✍ dations ◷ 2025-04-26 13:00:19 #组合数学,数学定理

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

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

另一种为:

集合论的表述如下:

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

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

另一个例子:

另一个例子:

更不直观一点的例子:

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

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

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

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

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

相关

  • 重肌无力症重症肌无力(英语:Myasthenia Gravis,简写MG),是慢性的神经肌肉疾病(英语:Neuromuscular disease),会造成不同程度的肌肉无力(英语:Muscle weakness)。最常影响眼部、脸部(英语:Facial musc
  • 术数饮食 - 服饰 - 建筑 - 文物 - 节日 - 教育 科学 - 五术(医学 - 术数) - 武术术数指在中华文化中五术的命、卜、相此三术。“盖数术家陈其数,而阴阳家明其义耳’。战国时便出现
  • 仲醇仲醇,或称二级醇(secondary alcohol),2-醇,是指羟基直接连接在一个仲碳原子上的醇。它也可以说是含有基团“–CHOH”的醇。异丙醇、异丁醇都是仲醇。可以在催化剂存在的条件下被
  • 西斯汀教堂西斯汀小堂(拉丁语:Sacellum Sixtinum;意大利语:Cappella Sistina ;也称为西斯汀礼拜堂)是一座位于梵蒂冈宗座宫殿内的天主教小堂,紧邻圣伯多禄大殿,以米开朗基罗所绘《创世纪》穹顶
  • 性沉溺性成瘾(英语:Sexual addiction),也称性瘾、嗜性、性上瘾或做爱上瘾症,是一种尽管得到了负反馈,依然想要进行性活动(自慰或非直接性交)(特别是性交)的强迫行为。支持为性成瘾症建立一个
  • 民事诉讼程序美国民事诉讼程序(Civil procedure in the United States)包括管辖美国联邦法院程序、50个美国各州法院系统及美国地区法院(英语:United States territorial court)等之的民事程
  • 用餐者困境在博弈论中,用餐者困境是一个多参与者的囚徒困境。设想的情景是有若干人出去吃饭,在点菜之前他们达成了一致:所有人平摊买单的钱。现在每个人要么点贵的菜肴,要么点便宜的菜肴。
  • 冲激不变法冲激不变法是利用连续时间滤波器来设计离散时间无限冲激响应(IIR)滤波器的一种方法,这种方法中对连续时间系统的冲激响应进行采样以产生离散时间系统的冲激响应。离散时间系统
  • 2018年冬季奥林匹克运动会伊朗代表团2018年冬季奥林匹克运动会伊朗代表团是伊朗所派出的2018年冬季奥林匹克运动会代表团。这是伊朗第11次参加冬奥。代表团包含四名运动员。伊朗在高山滑雪项目上获得一个男子席
  • 激光夜视照明器激光夜视照明,属于主动红外夜视照明。红外波长为人类肉眼看不见的波长,但是在近红外波段,CCD等电子设备可以侦侧得到,主动红外夜视就是利用这个原理。而红外激光,由于光模式分布