先讲一个我常用来暖场的数学小测试随便找13个人我敢保证其中至少有两个人出生在同一个月份。你听到这句话的第一反应可能是大概率吧但我要说的是这件事不是概率高而是逻辑上100%确定。背后的道理就是今天要聊的主角——鸽巢原理也叫抽屉原理。它朴素到一句话就能说完把n1只鸽子放进n个鸽巢总有一个巢里至少有两只鸽子。听起来像废话却是组合数学中最锋利的一把刀是无数竞赛题和算法题的底层逻辑。这篇内容适合所有想搞懂鸽巢原理的读者不管你是刚开始接触竞赛的中学生还是工作多年想补补数学基础的程序员甚至只是想陪孩子做趣味数学的家长都能从这里找到用得上的东西。我会从原理本身讲起一路拆到经典应用、竞赛实战、进阶形式最后聊一聊我自己踩过的误区和总结出的破题习惯。整个读下来你会发现这个废话级别的定理其实是一座巨大的冰山。1. 鸽巢原理的直觉与本质——为什么“简单到不像定理”我第一次接触鸽巢原理时心里只有四个字这不废话吗但恰恰是这种废话级别的命题在数学里有着极其严密的逻辑地位。它不是一个经验总结而是一条可以严格证明的定理。搞懂它为什么成立你才算真正握住了这把刀。1.1 从生活常识到一个严格的数学命题给完全没接触过的人讲鸽巢原理我一般用这句话如果m个物体要放进n个抽屉并且m n那么至少有一个抽屉里要放不少于两个物体。举个最直白的例子一年有12个月现在来了13个人每个人都有一个出生月份。一个月最多装下多少个人每个人出生月份只有12种可能那第13个人无论出生在哪个月都会和前面某个人重复。这就是13个人必有两人同月出生的由来。同样道理367个人里必有两个人同一天生日——因为一年最多366天算上闰年的2月29日。这是保证发生而不是大概率发生。很多人会混淆这两个概念后面我会专门展开讲。你可能会说这道理不是显而易见的吗没错它是显而易见的。但数学里有一条不成文的规矩越是显而易见的命题一旦被严格化、推广化就越能爆发出可怕的力量。鸽巢原理就是典型代表。它表面说的是鸽子比巢多就会挤本质却是关于有限集合到有限集合的映射必然产生碰撞的深刻结论。1.2 反证法鸽巢原理为什么一定成立要证明鸽巢原理最漂亮的方式是反证法。假设结论不成立也就是说每个巢里最多只有1只鸽子。那么n个巢最多能装下1 1 ... 1 n只鸽子。可是我们手上有n1只鸽子n n1矛盾。所以假设错误必然存在某个巢里至少有2只鸽子。你看整个过程干净利落。很多人问我为什么数学里总爱用反证法因为对于证明一定存在这类命题直接找往往无从下手但假设它不存在再推出矛盾往往简单得多。鸽巢原理就是一个绝佳的入门例子你不需要知道具体是哪只鸽子挤在哪只巢里只要知道必然存在就够了。从逻辑上说鸽巢原理本质依赖于自然数的性質如果有n个抽屉每个抽屉容量上限是k−1比如最多放k−1只那么所有抽屉加起来最多只能装n(k−1)个物体。只要你手上的物体总数比这个上限多就必然有抽屉被迫达到k个。这个推广形式就是鸽巢原理的广义版本也是很多题目真正的考点。1.3 平均数的视角广义表述与向上取整鸽巢原理还有一个更常用的表述我习惯叫它平均值视角把m个物体放进n个抽屉那么至少有一个抽屉里至少有⌈m/n⌉个物体。这里的⌈m/n⌉是向上取整也就是不小于m/n的最小整数。比如11个苹果放进4个抽屉11/4 2.75向上取整是3所以至少有一个抽屉里至少有3个苹果。为什么必须是向上取整因为如果每个抽屉都少于⌈m/n⌉个也就是每个抽屉最多⌈m/n⌉−1个那么总数最多是n(⌈m/n⌉−1)。你可以算一下这个数一定小于m于是矛盾。这个视角特别有用因为它把至少存在一个变成了一个可以计算的量。比如你参加一个测试总共答了50道题分5个板块平均每个板块10道题那么显然至少有一个板块有10道题——这几乎是废话但同样的逻辑用于更复杂的对象时就不废话了。后面我会展示很多看似高不可攀的数学题其实就是用这个平均值视角直接压出来的。2. 从人群到棋盘鸽巢原理的经典应用现场原理看完了接下来进入正题它怎么用我挑几个最经典的场景它们分别代表了用天然分类做抽屉用颜色做抽屉用余数做抽屉这三种最常见的构造思路。2.1 生日同月13个人与12个抽屉第一个例子已经说过13个人必有两人同月出生。这里的物体是人抽屉是月份。用平均值视角来说⌈13/12⌉ 2所以至少两人生日在同一个月。接着往深走一步。如果题目改成40个人的班级里一定有两个人同一天生日吗很多人的第一反应是应该有吧但正确答案是不一定。因为40 366从鸽巢原理的角度物体数小于抽屉数原理根本不适用。当然现实中一个40人班级里两人生日相同的概率很高这属于概率论的生日悖论范畴而不是确定性结论。这个差别极其关键。鸽巢原理给的是最坏情况下的保证它不负责回答有多大可能性。我在给学生讲的时候一定会强调这一点原理保证不了的事你再觉得理所当然也不能用。否则做题时很容易把一个概率直觉当成必然结论最后推导出错误答案。还有一个反直觉的例子常被拿来当面试题地球上至少有两个人头发根数相同。推理方式假设一个人最多有15万根头发把头发根数分成0到15万共150001类而全球有几十亿人远远大于150001。所以根据鸽巢原理至少有两人的头发根数完全相同。这个结论听起来离谱但逻辑上无懈可击。它展示的正是用天然类别做抽屉的力量。2.2 棋盘骨牌颜色也能当抽屉第二个经典场景来自一道流传很广的趣味题一个8×8的国际象棋棋盘有64个格子黑白各32个。如果去掉左上角和右下角这两个格子剩下62格能否用31块1×2的多米诺骨牌正好铺满直觉上62格用31块骨牌每块盖两个格子似乎能铺满。但答案是不能。为什么每块多米诺骨牌不管怎么放都会覆盖一个黑格和一个白格。所以如果31块骨牌真的能铺满62格那就必须恰好覆盖31个黑格和31个白格。可是原来的棋盘黑白各32个去掉的两个对角格是什么颜色都是黑色。于是剩下的是30个黑格和32个白格黑白数量不一致。无论你怎么摆都不可能在黑白不等的情况下完成覆盖。这个例子最妙的地方在于它把颜色变成了抽屉把骨牌覆盖变成了一场计数游戏。你根本不需要去尝试任何具体的摆放方案仅仅靠鸽巢原理的思想就永久性地否定了这个方案的存在性。从这个例子可以提炼出一个重要经验构造抽屉的依据不一定是物理上的格子任何能把物体分成互斥类别的标准都可以当抽屉用。颜色、奇偶、正负、同余、配对方式全是现成的抽屉素材。2.3 整除问题余数是最常用的抽屉之一再来看一个在数论里反复出现的应用任取n1个整数必有其中两个数之差能被n整除。证明同样直白任何一个整数被n除余数只能取0, 1, 2, ..., n−1一共n种情况。现在有n1个整数把它们按余数分类相当于把n1个物体放进n个抽屉。鸽巢原理说必有两个数落在同一个余数类里也就是它们的余数相同。两个余数相同的数相减自然能被n整除。取一个具体的数字验证任取6个整数其中必有两个数之差是5的倍数。因为被5除的余数只有0到4五种6个数却要分到5个抽屉里。这个结论在算法竞赛里应用极广。比如判断一个数组中是否存在两个数的差是某个数的倍数或者统计同余类的数量底层都是这个思想。我甚至可以说只要你见到差和整除两个词同时出现第一反应就应该是余数抽屉。2.4 抽屉从哪来三种典型的构造思路把上面这些经典例子放在一起你会发现构造抽屉的思路并不是天马行空而是有规律可循的。我总结成三种常见来源天然分类月份、星期、生日、血型、头发根数——题目本身已经提供了分类标准你只需要数一数物体数是否大于类别数。人为划分棋盘分色、正三角形分区域、区间等分——题目没有现成抽屉需要你主动把对象划分成若干个互斥且覆盖全体的小区域。数学结构余数类、奇偶性、整除后的奇数部分——利用数本身的数学属性来制造抽屉往往能解决最困难的一类题。为了方便对照我整理了一张经典例子表场景物体鸽子抽屉鸽巢结论13人生日同月13个人12个月必有两人同月出生367人生日同日367个人366天必有两人同一天生日棋盘去对角骨牌覆盖需求黑格/白格黑白数不等无法铺满n1个整数之差n1个整数n个余数类必有两数之差被n整除这三类源头几乎覆盖了90%的鸽巢原理题目。剩下10%的难题往往是在如何巧妙划分上做文章这也是下一部分要聊的竞赛实战。3. 竞赛题里鸽子藏在哪里抽屉构造的实战拆解如果说前两部分是热身这一部分就是真正的实战。竞赛题不会傻到告诉你这里有n1只鸽子、n个巢它会把鸽子藏进数字、图形和关系里。破题的关键就是你得把它们找出来。3.1 1到2n中任取n1个数必有一个整除另一个这道题我每次讲都觉得很惊艳。题目是这样从1到2n这2n个正整数中任意取出n1个数证明其中必有一个数整除另一个数。看起来无从下手。1到2n里的数五花八门整除关系更是一团乱麻。但实际上这道题只需要一步巧妙的抽屉构造。把每个正整数都写成奇数 × 2的幂的形式。什么意思比如24 3 × 2³8 1 × 2³10 5 × 2¹奇数部分分别是3、1、5。注意任何一个正整数的奇数部分都是唯一的。现在看从1到2n之间的数它们的奇数部分只能取1, 3, 5, ..., 2n−1一共只有n种。可我们选了n1个数于是根据鸽巢原理必然有两个数的奇数部分相同。假设这两个数是 a r × 2^i 和 b r × 2^j其中r是同一个奇数不妨设i j。那么显然a整除b。整个过程没有暴力计算只是把一个看似复杂的整除关系转化成了相同奇数部分的碰撞。这一步转化就是整个题目的灵魂。我当年第一次看到这个解法时真的有一种被点亮的感觉——原来抽屉可以藏在数的质因数分解剥掉2之后这个层面。这个题目也揭示了一个重要方法大多数时候你不需要直接构造两个有整除关系的数你只需要构造一个让它们共享某种结构的抽屉剩下的交给你选择的数学结构自己完成。3.2 正三角形里的5个点几何问题分区域几何里也一样能藏鸽子。这道题是入门级的经典在一个边长为1的正三角形内任取5个点证明至少有两个点之间的距离不超过1/2。第一眼看上去像是度量几何的问题好像和鸽巢原理没什么关系。但做法非常巧妙把这个边长为1的正三角形按照三条中位线切成4个边长都是1/2的小正三角形。这样原来的大三角形就被分成了4个互不重叠、覆盖全部的区域。现在放进去5个点相当于5只鸽子飞进4个巢必然有2个点落在同一个小正三角形里。而每个小正三角形的直径也就是内部任意两点能达到的最大距离是它的边长1/2。因此这两个落在同一个小三角形里的点距离一定不超过1/2。这个解法最值得学习的地方在于抽屉不是天然存在的而是你画出来的。当你感觉无从下手时试着把图形均匀切割、把区间等分、把对象分组往往就能硬生生地造出鸽巢来。几何极值问题里这种切割造抽屉的手法极其常见从三角形到正方形从线段到圆周到处都能用。3.3 六人相识问题从这里通向拉姆齐理论第三个经典题很多人在大学离散数学里见过它的影子任意6个人中必有3个人两两认识或者3个人两两不认识。这题乍看像社交问题实际上可以用图论建模6个人看成6个点任意两个人之间连一条线认识染红色不认识染蓝色。于是问题变成任意给K6的每条边染红蓝两色必存在一个同色三角形。证明分两步走第一步用鸽巢原理第二步用排除法。任取其中一个点A。从A出发连到其他5个点一共5条边。这5条边只有红蓝两种颜色根据鸽巢原理至少3条边是同色的。不妨假设AB、AC、AD三条边都是红色。现在看B、C、D这三个点之间的连线一共三条。如果其中任何一条是红色比如BC是红的那么A、B、C就构成了一个红色三角形。如果这三条边一条红的都没有那它们就全是蓝色B、C、D三个人就构成一个蓝色三角形。两种可能无论如何都会出现同色三角形。这个结论就是组合数学中拉姆齐理论的经典起点R(3,3) 6意思是要让同色三角形必然出现至少需要6个点。这道题的精彩之处在于它先用鸽巢原理从A点出发保证了至少三条同色边再通过排除法把剩下的情况一网打尽。鸽巢原理负责制造局部的不均匀排除法负责把这些不均匀扩展到全局。这种组合拳在竞赛题里非常常见。3.4 复盘发现鸽子和鸽巢的做题顺序讲完三道题我想把解题时的思考路径复盘一下因为这才是真正能迁移到其他题目的东西。我一般按下面这个顺序走第一先盯住题目里的关键字眼。出现任意至少保证这样的词鸽巢原理就该进入候选名单了。第二判断物体数是否大于类别数。如果题目给出了明确的类别数比如月份、颜色、余数、区间那我先数一数物体数看m是不是比n大。不大就换角度。第三尝试构造抽屉。没有现成抽屉时优先考虑等分分组按余数分类按某种不变属性分类。构造完以后务必检查三点每个物体都落在某个抽屉里吗抽屉之间有重叠吗抽屉数量是否确实小于物体数量第四计算目标。如果题目要求证明至少有一个抽屉有k个物体那就要验证⌈m/n⌉≥k。不满足说明抽屉切得不合适得重新划分。这套流程不能保证解决所有难题但至少能让你在看到一个陌生题目时不至于大脑空白。鸽巢原理最难的部分不是使用它而是识别它而这种识别能力只能靠经典例题的积累来喂出来。4. 更强形式的鸽巢原理平均值、加权与无限延伸很多人以为鸽巢原理就是n1只鸽子塞进n个巢这么一锤子买卖其实它有三个明显的进阶方向每一个都让威力上升一个量级。4.1 广义形式物体数远大于抽屉数时最基础的推广是把n1个物体改成m个物体结论变成把m个物体放进n个抽屉至少有一个抽屉里至少有⌈m/n⌉个物体。这个我在第1.3节已经提过但它的应用价值值得再说透一点。比如18个苹果放进4个抽屉⌈18/4⌉ 5所以必然有个抽屉有5个苹果。换成更大的数也一样100万个数按照1000个余数类划分⌈1000000/1000⌉ 1000必有一个余数类里至少有1000个数。这个形式的重要性在于它把存在一个增强为存在一个而且这个至少是多少。做题时如果你的目标是证明至少存在k个某种对象只要物体总数m和类别数n满足⌈m/n⌉≥k目标就直接达成了不需要任何精巧构造。4.2 平均值语言和、平均与必有超过第二种进阶是把鸽巢原理翻译成平均值的话你会发现它其实无处不在。比如一学期有20次小测平均分是82分那么必然存在一次小测分数不低于82分。这是废话因为平均值的定义就保证了这一点。但换成复杂场景就不那么废话了如果100个数的总和超过10000那么至少有一个数大于100。再比如连续30天的日均气温高于28°C那必然有某一天的气温高于28°C。这些表述本质上都是同一个原理如果所有个体都低于某个阈值那么平均值不可能超过这个阈值一旦平均值超过了个体里就必然存在超过者。竞赛里这种用法也很常见。比如M个数之和超过某个界限证明存在若干个数加起来超过某个下界这样的题切入点往往就是把整体按平均值切一刀。我当时学到这里才意识到原来鸽巢原理和不等式、平均值定理是血脉相连的。4.3 无限版本有限抽屉里的无穷成员鸽巢原理还有一个专门处理无穷集合的版本说法是这样的把无穷多个物体放进有限个抽屉至少有一个抽屉里装着无穷多个物体。证明依然靠反证如果每个抽屉都只有有限个物体那么有限个抽屉加起来也就只有有限个物体这和无穷多个物体矛盾。这个版本听起来也很平凡但它比有限版本更加强大。举个例子正整数无穷多如果按末位数字分成10类末位0、1、...、9那么必有一类包含无穷多个正整数——这几乎是一句废话。但更深刻的应用在数论里给定一个整数序列如果把它按对某个数取模的余数分成有限类就能立刻知道至少有一类余数对应着无穷多个序列项。这种从无穷中砍出一块来研究的手法是很多数论和组合论证的基本功。从无限鸽巢原理再往前走一步就通向了拉姆齐理论的深层领域——只要某个结构足够大必然包含某种规则的局部结构。六人相识问题只是这个宏大理论的一扇小门门后面是无限组合学里的大片疆土。5. 为什么鸽巢原理容易用错常见误区与破题习惯讲了这么多成功案例我也得说说翻车案例。鸽巢原理看起来简单实际做题时出错率却高得吓人。我总结了三个最常见的使用误区再加上我这些年养成的破题习惯供你对照自查。5.1 方向别搞反物体数必须大于抽屉数先说最容易犯的低级错误把鸽子和巢的位置搞反了。鸽巢原理成立的前提是m n。如果你手里只有5个人却要分到12个星座那什么也保证不了——5个人完全可以各自落在不同的星座里。有些人做这类题看到12个星座和5个人就直接写必有两个人在同一个星座这就是典型的套公式失败。反过来13个人对12个月就一定产生碰撞5个人对12个星座则完全没有碰撞保证。原理本身不关心具体是人还是星座它只关心数量关系。所以做题的第一步一定是确认物体数是不是严格大于抽屉数我还见过有人把方向记成抽屉数大于物体数时必有空抽屉——这个说法本身在特定条件下可以成立如果物体数小于抽屉数且每个物体占用一个抽屉那么不可能装满所有抽屉必然有空抽屉但它和鸽巢原理是两码事不能混淆。最好的办法是每次使用前在心里默念一遍物体数 抽屉数才会出碰撞。5.2 抽屉要覆盖划分不能有遗漏或重叠第二个误区更隐蔽那就是构造抽屉时没有保证覆盖全体和互不重叠。举个例子。假设你想证明10个数里必有两个数之和为偶数你可能会想把数分成大于5的和小于5的两类然后期待什么。但这个分类根本不完整——等于5的数放哪而且就算分成两类每类里的数相加也不一定是偶数。除非你改用奇偶性10个数分到奇数、偶数两个抽屉⌈10/2⌉ 5必有一个抽屉至少5个。可光有5个同奇偶的数还不够你要的是两个那5显然是够的。关键是这里要意识到你选的分类标准必须和结论逻辑关联否则就算鸽巢原理成立了也推不出目标结论。我见过不少学生在练习1到10中任取6个数必有两个数之和为11这道题时尝试过用大小分类结果举步维艰。正确的做法是把数配成5对抽屉(1,10)、(2,9)、(3,8)、(4,7)、(5,6)取6个数就是6只鸽子飞进5对抽屉必然有一对的两个数都被取到它们的和正好是11。这里有个很好的操作习惯先画一张覆盖表把每个物体标记到它所属的抽屉里亲眼确认没有一个物体落空也没有一个物体同时属于两个抽屉。数学直觉会骗人但一张仔细画的表不会。5.3 保证与概率是两回事第三个误区是把鸽巢原理的必然保证和现实中的大概率混为一谈。最经典的例子还是生日367个人必有两人同日生这是确定性结论。而23个人中两个人生日相同的概率超过50%这是概率论中生日悖论的结果。一个是一定会一个是超过一半可能会两者虽然数值接近但逻辑上完全不同。我见过有人把这两个结论混在一起说因为鸽巢原理23个人里必有两个人同日生——这显然是错的。23个人放到366个日期里m n鸽巢原理根本不适用它只是大概率有重复而不是必然有。还有一个好例子掷一枚骰子掷7次鸽巢原理能保证什么它保证至少有一种点数出现不少于2次。但它不能保证至少出现一次6点。你可能连续6次都是5点第七次是1点那就一次6点都没有。原理只保证重复不保证指定结果。鸽巢原理给出的结论永远是存在性的它不会告诉你是谁、在哪、什么时候这一点一定要习惯。5.4 我的破题习惯与练习清单最后分享几个我自己多年积累的破题习惯希望能帮你少走些弯路。第一个习惯拿到题目先划关键词。出现任意至少保证必然存在这类词我立刻在草稿纸上画两个框物体是什么抽屉可能是什么哪怕最后发现不是鸽巢题这个动作也能帮我理清结构。第二个习惯先用简单数字试出感觉。比如题目说任取n1个数我就先代入n 3或n 5动手枚举一个小范围看看碰撞大概出现在哪。很多时候小规模的直觉会直接告诉你抽屉该怎么构造。第三个习惯抽屉候选清单化。我脑子里常备一份抽屉来源清单余数类、奇偶性、颜色、区间等分、图形分割、配对分组、同余类、相同某种结构。遇到难题就逐个试试到能推出⌈m/n⌉达到目标为止。再给你一组适合上手的练习自己做完以后对照检查任取11个整数证明必有两个数之差是10的倍数。提示按模10的余数分类从1到10中任取6个数证明必有两个数之和为11。提示把和为11的数配成5对5对当抽屉在一个边长为1的正方形内任取5个点证明必有两个点的距离不超过√2/2。提示把正方形等分成4个小正方形任意给定5个整数证明其中必有3个数之和能被3整除。提示按模3余数分类后分情况讨论最后一道题相对难一点但做完之后你会对鸽巢 分类讨论的组合有更深的理解。我记得第一次在有经验的教练面前演示这道题时对方问了我一句你知道吗这道题再往下推广就是任意n个整数里必有若干个之和被n整除的经典定理了。那个瞬间我才意识到鸽巢原理不是一个孤立的技巧它是一整片知识网络的源头节点。这么多年过去了我最大的体会是原理简单难的是你愿不愿意先在草稿纸上把抽屉画出来。很多人不是不懂鸽巢原理而是面对新题时脑子里只有原理的文字而没有操作。当你开始认真地划分、列表、查覆盖、算⌈m/n⌉的时候鸽子自然就藏不住了。希望这篇内容能让你在下次遇到至少保证这类字眼时多一种从容的底气。