我认真研究天平秤球问题是在帮一个准备算法面试的朋友复盘题目的时候。题目用一句话就能说完12个外观完全一样的球其中1个重量异常不知道偏轻还是偏重用一架没有砝码的天平最多称3次找出这个异常球并判断它到底是偏轻还是偏重。说实话第一眼看到这题很多人会觉得“无非二分法嘛”但真正上手做一次就会明白它比想象中难得多而且背后的东西也远比一道题值钱三进制编码、信息论极限、组合设计、甚至程序化搜索方案全都藏在里面。这篇文章我就把这套东西一次性讲透从最直观的分组做法到能直接抄作业的固定编码表再到13球、N球这类变体尽量让新手也能看完就能上手。如果你是准备面试的开发者可以重点看后面的编码解法和程序验证如果你只是被这个问题勾起好奇心前面“三分组自适应”部分就足够让你在朋友面前露一手。两种路径各有价值我尽量都讲明白。1. 先把题目和“为什么值得研究”说清楚1.1 问题描述与解题目标天平秤球问题的标准描述是有12个尺寸、颜色、外观完全相同的球其中只有1个球的重量与其余11个不同但不知道它是偏重还是偏轻。现在给你一架普通天平只能比较左右两盘重量谁重谁轻没有刻度也不能读数要求在最多3次称量之内把这个异常球找出来并且说清楚它到底是偏重还是偏轻。这里有两个关键限定。第一“不知道偏轻还是偏重”让题目难度直接翻倍因为你面对的不是“在12个里找一个”的12种情况而是“在12个球里找一个且找到后还要区分轻重”的24种情况。第二“最多3次”意味着称量策略是自适应、可分支的第2次、第3次称什么取决于前一次的结果。如果忽略这两点很多看起来像是解法的思路都会在中途翻车。1.2 为什么这题是面试和思维训练常客这道题之所以长盛不衰是因为它几乎没有专业知识门槛却非常考验一个人的结构化解题能力。它会强制你回答三个层面问题一是信息量是否足够二是策略上如何保证最坏情况也能命中三是具体每一步能否真正“消去”足够多的可能性。这三个问题本质上就是工程里常说的理论边界、算法设计和异常分支处理。对面试官来说这题是很好的干扰项筛选器。喜欢背答案的人往往只能给出“1和2称、3和4称”这种支离破碎的操作却说不清为什么要这样分组真正理解的人会从“每次称量有三种结果”出发自然而然地想到三进制拆分、镜像配对、剩余候选集收缩这些概念。所以与其说这是个逻辑题不如说它是一面能照出思维习惯的镜子。1.3 先给出结论12球称3次确实可以做到先把结论摆在前面12个球、不知道轻重、最多称3次同时找出坏球并判断轻重这件事是可以做到的。不仅自适应策略可以做到甚至存在“三次称量完全固定、不需要中途改变策略”的编码方案这一点比大多数人想象的要强。后面我会把两种方案都给出来并且用程序验证一次确保不是碰巧。如果你之前在网上搜过答案估计看到过各种真假难辨的“口诀”。我的建议是不要背口诀因为你只要理解了编码思想未来遇到13球、未知轻重、已知轻重、甚至N球k次这类变体时都能现场推出来。这才是这篇文章最想传达的东西。2. 用信息论算出“理论上最多能称几个球”2.1 一次称量为什么能带来三种结果天平这一次动作结果只有三种左边重、右边重、平衡。请注意这三种结果不是简单“是/否”的二元信息而是三态信息。一次称量携带的最大信息量是 log₂3 比特约1.585比特。三次称量携带的最大信息量就是 3×log₂3 log₂27对应27种不同的“三次结果组合”。这就是这道题和信息论最直接的交点。如果在某一步你的策略只能产生两种可区分结果那你就白白浪费了天平“平衡”这个信息通道。这也是为什么单纯二分法永远做不出12球3次二分法的一次只能排除一半3次最多区分8种情况远不够覆盖24种。2.2 从3^k到2N的不等式在不考虑其他约束的前提下k次称量最多能区分的“状态数”是3^k也就是每种结果序列对应一个最终结论。我们的问题里总状态数是2NN个球中每一个都可能是坏球并且每个球又有偏轻和偏重两种可能。要保证能全部区分必要条件就是3^k ≥ 2N把k3代进去得到3^327 ≥ 2N所以N最大是13。从纯信息量角度看3次称量理论上最多可以处理13个未知轻重的球。这就是为什么13球问题存在“找出坏球”的解也解释了为什么12球没有触及信息量天花板留出了判断轻重的空间。2.3 为什么“能判断轻重”要更严格只找出坏球和“找出并判断轻重”是两个难度级别。如果只要求找出坏球13个球、3次称量是可以做到的因为27种结果容纳13×226种状态绰绰有余。但如果要求同时判断轻重情况就变了球i偏轻和球i偏重对应的结果序列在三次称量的每一位上必须严格相反。比如某球第1次放左盘偏重时左盘重、第1次结果是“左重”那它偏轻时第1次就必须是“右重”。这意味着每个坏球要占用一对“镜像结果”。而三进制三位结果中非零的镜像对一共有(27−1)/213对但其中还要扣除一对待定冗余所以能同时判断轻重的上限是(3^k−3)/2。把k3代进去就是(27−3)/212。这个公式直接告诉你12球3次就是“找出来并判断轻重”的极限也是为什么题目偏偏选12而不是10、11或13。3. 经典实用解法三分组自适应的三步走3.1 第一次称量4 vs 4自适应的经典思路第一步先把12个球分成三组A组1、2、3、4B组5、6、7、8C组9、10、11、12。第一次称量拿A组对B组即1、2、3、4 vs 5、6、7、8。这一步的意义在于不管是平衡还是不平衡都能把候选范围压缩到4个球左右。如果平衡说明A组和B组都是标准球问题球只能在C组4个里。如果不平衡比如A组重那说明两种情况要么A组4个里有1个偏重要么B组4个里有1个偏轻。这就是为什么不能简单得出“重的那边有问题”的结论因为你不知道轻重方向。3.2 第一次平衡时怎么处理第一次称量结果是平衡这是最好处理的分支。此时1到8号全部是标准球坏球在9、10、11、12四颗里。第二次称量9、10、11 vs 1、2、3右边放3个标准球。如果第二次还是平衡那坏球一定是12号。第三次拿12号 vs 1号标准球一称便知12号偏轻还是偏重。如果第二次左边重说明9、10、11中有一个偏重第三次称9 vs 10平衡就是11偏重否则谁重谁就是坏球。如果第二次左边轻说明9、10、11中有一个偏轻第三次称9 vs 10平衡就是11偏轻否则谁轻谁就是坏球。这个分支的核心技巧是用“标准球”当参照物。第一次平衡后你已经拥有了8个标准球它们就像砝码一样可以随意取用问题从“找坏球”退化成“在4个球里找1个并且已经知道坏球就在其中”。3.3 第一次左重时怎么处理第一次不平衡时会复杂一些因为存在两种嫌疑方向。以第一次左重为例候选状态为1、2、3、4中有一个偏重或者5、6、7、8中有一个偏轻。注意9到12号此时已经是标准球。第二次采用交叉换位策略称1、2、5 vs 3、6、9其中9号是标准球。这个策略的精妙之处在于它把部分“重嫌疑”的球留在左盘部分换到右盘还引入了一个标准球人为制造出更细致的区分。如果第二次平衡说明嫌疑落在没有参加第二次称量的4号、7号、8号中。结合第一次左重的信息只可能是4号偏重、7号偏轻或8号偏轻。第三次称7 vs 8平衡则4号偏重谁轻谁就是那个偏轻的坏球。如果第二次左重说明嫌疑落在1号、2号、6号中对应1号偏重、2号偏重或6号偏轻。第三次称1 vs 2平衡则6号偏轻否则谁重谁偏重。如果第二次右重说明嫌疑落在3号、4号、5号中对应3号偏重、4号偏重或5号偏轻。第三次称3 vs 4平衡则5号偏轻否则谁重谁偏重。3.4 第一次右重时怎么处理对称处理第一次右重不需要重新想一套方案它完全是左重分支的镜像。把左重分支里的编号做对称映射1↔5、2↔6、3↔7、4↔8并把“重嫌疑”和“轻嫌疑”互换就得到右重分支的执行方案。第二次称5、6、1 vs 7、2、99号标准球。如果第二次平衡嫌疑落在3号偏轻、4号偏轻、8号偏重中第三次称3 vs 4平衡则8号偏重谁轻谁是坏球。如果第二次左重嫌疑是5号偏重、6号偏重、2号偏轻第三次称5 vs 6平衡则2号偏轻谁重谁坏。如果第二次右重嫌疑是7号偏重、1号偏轻第三次称7 vs 9号标准球7重则7号偏重平衡则1号偏轻。这里只要掌握了“保持左右盘数量一致”和“每称一次必须让三种结果都有明确归属”两个原则即使换了编号也不会乱。整个12球自适应方案到此闭环。4. 进阶玩法把三次称量写成固定编码表4.1 编码思路用三进制记录球的位置自适应方案虽然直观但它有一个隐藏缺陷第二次、第三次称什么取决于前面的结果不方便程序化也不方便记忆。其实还存在一种更漂亮的方案可以让三次称量完全固定下来中途不做任何调整。思路是把每个球当成一个“编码对象”。三次称量中这个球要么放左盘要么放右盘要么不上秤。我们用表示左盘用−表示右盘用0表示不上秤那么每个球就有一个长度为3的编码。核心约束有三条第一不能出现两个球编码互为相反数否则“甲偏重”和“乙偏轻”会产生完全相同的结果第二每一列的和−数量必须相等否则那一次称量左右盘球数不一致第三不能有编码全为0否则这个球永远不上秤坏了也判断不了轻重。4.2 直接照抄一套可用的固定三称方案下面给出一套我构造并验证过的固定编码表。每个三元组按“第1次、第2次、第3次”顺序排列表示该次放左盘−表示放右盘0表示不上秤。球号编码球号编码1 70 − −2 −80 − 3 − 9− 04 010− 0 05− 0 −110 − 06− 0 120 0 −按照这个表三次称量的具体操作就是第1次称1、2、3、4 vs 5、6、9、10第2次称1、2、4、9 vs 3、7、8、11第3次称1、3、6、8 vs 2、5、7、12你可以核对一下三次称量左右盘的球数都是4对4没有哪一次出现数量不等的情况。这也是这个方案能成立的最基本保障。4.3 三次结果反查表三次称完你会得到一个形如(a, b, c)的结果向量每一位只可能是“左重”“右重”“平衡”三种。反查规则很简单把它与编码表对比。如果结果向量等于某一行编码说明这个球偏重。比如结果是( −)它正好等于2号球的编码结论就是2号球偏重。如果结果向量等于某一行编码的相反数也就是把编码里的和−互换说明这个球偏轻。比如结果是(− − )它是2号编码( −)的相反数结论就是2号球偏轻。由于编码表在设计时保证了不重复、不互反所以任何一个结果向量最多只对应一个“球状态”组合不会出现“既像甲偏重又像乙偏轻”的二义性。我用程序对所有24种情况做过枚举结果是完全没有冲突。4.4 为什么编码表能保证不冲突这套表的构造逻辑可以理解为在27种三进制结果里挑出12对“镜像结果”分别分配给12个球每对镜像对应同一个球的偏重和偏轻。挑的时候有三条硬性要求不选全0编码不选互为相反数的两个编码保证每一列和−数量相等。这三个条件缺一不可。第一列如果不平衡第1次称量左右球数就不等结果会预先倾斜如果两个编码互反那么A球偏重和B球偏轻的结果会完全相同如果出现全0编码一个球三次都没上过秤即使最终锁定是它也无法判断轻重。理解了这三条你甚至能自己用回溯程序搜索出其他风格完全不同的编码表每个表都能解同一道题。5. 变体扩展13球、N球、已知轻重5.1 13球称3次能找出但不保证轻重既然三次结果有27种而13个球未知轻重一共只有26种状态理论上13球“找出坏球”是可行的。但前面说过要同时判断轻重必须满足更严格的镜像配对条件所以13球场景下会有一个球的状态无法完整判定。具体表现是无论怎么设计结果序列里总会出现一种情况能告诉你“坏球就是某个球”却无法同时告诉你它偏轻还是偏重。你可以理解为缺少的那一个“结果槽位”正好卡在轻重信息的关键位置。因此13球变体更适合讨论“如何用3次称量锁定坏球”而不是“如何用3次称量既锁定又判重”。5.2 已知坏球偏重或偏轻的N球问题如果题目提前告诉你坏球是偏重的问题会简单很多每次称量就退化成了标准的三分查找。第一次把球分成三等份任意两份上天平如果一边重坏球就在重的那份里如果平衡坏球就在没上秤的那份里。一次称量把范围缩小到原来的1/3。所以k次称量最多能处理的球数是3^k。比如3次最多可以处理27个已知偏重的球2次就是9个。这个结果和“未知轻重”时的12球形成了鲜明对比方向信息值多少钱在这里仅仅多知道一个“偏还是轻”就能把容量从约12个提升到27个。5.3 通用公式汇总把几个结论放在一起方便以后直接查场景k次称量最大球数3次代入未知轻重要求找出并判断轻重(3^k − 3) / 212未知轻重只要求找出坏球(3^k − 1) / 213已知坏球偏重或偏轻3^k27这些公式最大的价值是帮你判断一个变体题到底有没有解。如果出题人考你“16个球3次未知轻重找出并判断轻重”你可以直接说没解因为16已经超过上限12。反过来如果场景是“10个球3次未知轻重”你有充足的裕量甚至可以采用更简单粗暴的分组方式。5.4 程序化验证的入口有了编码表可以用一小段Python代码验证方案是否真的无冲突。思路是把每个“球状态”代入编码表计算它对应的三次结果向量然后检查是否有两个不同状态产生同一个向量。codes { 1: (1, 1, 1), # 球1三次都在左盘 2: (1, 1, -1), 3: (1, -1, 1), 4: (1, 1, 0), 5: (-1, 0, -1), 6: (-1, 0, 1), 7: ( 0, -1, -1), 8: ( 0, -1, 1), 9: (-1, 1, 0), 10: (-1, 0, 0), 11: ( 0, -1, 0), 12: ( 0, 0, -1), } results {} for ball, code in codes.items(): for weight in (1, -1): # 1 偏重-1 偏轻 r tuple(code[i] * weight for i in range(3)) results.setdefault(r, []).append((ball, weight)) conflict [r for r, cases in results.items() if len(cases) 1] print(冲突数量:, len(conflict))运行结果会输出“冲突数量: 0”说明这套固定三称方案在全部24种情况下都能得到唯一结论。如果你想自己设计一套新编码表也可以把这段代码当作验证器配合回溯搜索函数使用。6. 实操踩坑记录与经验心得6.1 最容易翻车的三个细节第一个坑是第一次称量就贪多。有人觉得“多称几个球效率更高”直接拿6个球对6个球上天平。结果一旦不平衡面对的是6个偏重嫌疑和6个偏轻嫌疑混合在一起的12种情况后续两次根本拆不完。这也是这道题反直觉的地方你一次称的量太多反而把剩余可能性压得不够均匀。第二个坑是忽略标准球。第一次称量平衡后你已经拥有了8个标准球它们是后续解题的关键砝码。很多人在这一步还在“用未知球去称未知球”其实大可以大胆地把标准球放上天平这会让判断轻松很多。第三个坑是编码方案里出现互反编码。我最初尝试固定三称方案时就踩过这个坑看似左右盘数量都平衡编码也不重复但两组编码互为相反数导致“甲偏重”和“乙偏轻”的结果一模一样直到写程序验证才发现。所以只要涉及编码类方案程序化穷举验证永远是最后一道安全网。6.2 常见问题速查表问题快速答案第一次应该称几个球12个球时称4 vs 4保证每种分支剩余候选数均衡第一次不平衡时重的那一侧一定有坏球吗不一定可能是轻的一侧中有球偏轻已有一个标准球时该怎么做尽量把标准球放上天平作参照可以大幅简化判断13个球3次能判断轻重吗只能保证找出坏球不能保证同时判断轻重编码表中为什么不能有互为相反数的编码否则“A偏重”和“B偏轻”会产生相同结果序列怎么快速验证一套方案把所有“球状态”仿真一遍检查结果向量是否唯一6.3 个人经验这个题练的是什么我在实际研究这个问题时最大的体会是它练的不是“会称球”而是“会系统性地逼近结论”。从信息量估算极限、到三分支切割候选集、再到编码表设计每一步都逼着你把“下一步该做什么”想清楚而不是凭感觉操作。我做程序化验证时最快定位问题的办法不是反复试称重方案而是先把所有“球状态”穷举一遍看哪个结果冲突了再倒推是哪一步编码设计不满足约束。如果你也想把这道题变成自己的“思维肌肉记忆”我建议你找一张纸和一支笔先不看任何答案自己从“每次称量有三种结果”这句话出发试着推一套12球方案。推不出来也没关系再对照这篇文章的编码表一行一行验证“为什么这样可以”。几次之后你会发现自己面对这种多分支问题时不再只靠背套路而是能真的从原理出发推导方案了。
12球天平秤球问题全解：从三进制编码到信息论极限
我认真研究天平秤球问题是在帮一个准备算法面试的朋友复盘题目的时候。题目用一句话就能说完12个外观完全一样的球其中1个重量异常不知道偏轻还是偏重用一架没有砝码的天平最多称3次找出这个异常球并判断它到底是偏轻还是偏重。说实话第一眼看到这题很多人会觉得“无非二分法嘛”但真正上手做一次就会明白它比想象中难得多而且背后的东西也远比一道题值钱三进制编码、信息论极限、组合设计、甚至程序化搜索方案全都藏在里面。这篇文章我就把这套东西一次性讲透从最直观的分组做法到能直接抄作业的固定编码表再到13球、N球这类变体尽量让新手也能看完就能上手。如果你是准备面试的开发者可以重点看后面的编码解法和程序验证如果你只是被这个问题勾起好奇心前面“三分组自适应”部分就足够让你在朋友面前露一手。两种路径各有价值我尽量都讲明白。1. 先把题目和“为什么值得研究”说清楚1.1 问题描述与解题目标天平秤球问题的标准描述是有12个尺寸、颜色、外观完全相同的球其中只有1个球的重量与其余11个不同但不知道它是偏重还是偏轻。现在给你一架普通天平只能比较左右两盘重量谁重谁轻没有刻度也不能读数要求在最多3次称量之内把这个异常球找出来并且说清楚它到底是偏重还是偏轻。这里有两个关键限定。第一“不知道偏轻还是偏重”让题目难度直接翻倍因为你面对的不是“在12个里找一个”的12种情况而是“在12个球里找一个且找到后还要区分轻重”的24种情况。第二“最多3次”意味着称量策略是自适应、可分支的第2次、第3次称什么取决于前一次的结果。如果忽略这两点很多看起来像是解法的思路都会在中途翻车。1.2 为什么这题是面试和思维训练常客这道题之所以长盛不衰是因为它几乎没有专业知识门槛却非常考验一个人的结构化解题能力。它会强制你回答三个层面问题一是信息量是否足够二是策略上如何保证最坏情况也能命中三是具体每一步能否真正“消去”足够多的可能性。这三个问题本质上就是工程里常说的理论边界、算法设计和异常分支处理。对面试官来说这题是很好的干扰项筛选器。喜欢背答案的人往往只能给出“1和2称、3和4称”这种支离破碎的操作却说不清为什么要这样分组真正理解的人会从“每次称量有三种结果”出发自然而然地想到三进制拆分、镜像配对、剩余候选集收缩这些概念。所以与其说这是个逻辑题不如说它是一面能照出思维习惯的镜子。1.3 先给出结论12球称3次确实可以做到先把结论摆在前面12个球、不知道轻重、最多称3次同时找出坏球并判断轻重这件事是可以做到的。不仅自适应策略可以做到甚至存在“三次称量完全固定、不需要中途改变策略”的编码方案这一点比大多数人想象的要强。后面我会把两种方案都给出来并且用程序验证一次确保不是碰巧。如果你之前在网上搜过答案估计看到过各种真假难辨的“口诀”。我的建议是不要背口诀因为你只要理解了编码思想未来遇到13球、未知轻重、已知轻重、甚至N球k次这类变体时都能现场推出来。这才是这篇文章最想传达的东西。2. 用信息论算出“理论上最多能称几个球”2.1 一次称量为什么能带来三种结果天平这一次动作结果只有三种左边重、右边重、平衡。请注意这三种结果不是简单“是/否”的二元信息而是三态信息。一次称量携带的最大信息量是 log₂3 比特约1.585比特。三次称量携带的最大信息量就是 3×log₂3 log₂27对应27种不同的“三次结果组合”。这就是这道题和信息论最直接的交点。如果在某一步你的策略只能产生两种可区分结果那你就白白浪费了天平“平衡”这个信息通道。这也是为什么单纯二分法永远做不出12球3次二分法的一次只能排除一半3次最多区分8种情况远不够覆盖24种。2.2 从3^k到2N的不等式在不考虑其他约束的前提下k次称量最多能区分的“状态数”是3^k也就是每种结果序列对应一个最终结论。我们的问题里总状态数是2NN个球中每一个都可能是坏球并且每个球又有偏轻和偏重两种可能。要保证能全部区分必要条件就是3^k ≥ 2N把k3代进去得到3^327 ≥ 2N所以N最大是13。从纯信息量角度看3次称量理论上最多可以处理13个未知轻重的球。这就是为什么13球问题存在“找出坏球”的解也解释了为什么12球没有触及信息量天花板留出了判断轻重的空间。2.3 为什么“能判断轻重”要更严格只找出坏球和“找出并判断轻重”是两个难度级别。如果只要求找出坏球13个球、3次称量是可以做到的因为27种结果容纳13×226种状态绰绰有余。但如果要求同时判断轻重情况就变了球i偏轻和球i偏重对应的结果序列在三次称量的每一位上必须严格相反。比如某球第1次放左盘偏重时左盘重、第1次结果是“左重”那它偏轻时第1次就必须是“右重”。这意味着每个坏球要占用一对“镜像结果”。而三进制三位结果中非零的镜像对一共有(27−1)/213对但其中还要扣除一对待定冗余所以能同时判断轻重的上限是(3^k−3)/2。把k3代进去就是(27−3)/212。这个公式直接告诉你12球3次就是“找出来并判断轻重”的极限也是为什么题目偏偏选12而不是10、11或13。3. 经典实用解法三分组自适应的三步走3.1 第一次称量4 vs 4自适应的经典思路第一步先把12个球分成三组A组1、2、3、4B组5、6、7、8C组9、10、11、12。第一次称量拿A组对B组即1、2、3、4 vs 5、6、7、8。这一步的意义在于不管是平衡还是不平衡都能把候选范围压缩到4个球左右。如果平衡说明A组和B组都是标准球问题球只能在C组4个里。如果不平衡比如A组重那说明两种情况要么A组4个里有1个偏重要么B组4个里有1个偏轻。这就是为什么不能简单得出“重的那边有问题”的结论因为你不知道轻重方向。3.2 第一次平衡时怎么处理第一次称量结果是平衡这是最好处理的分支。此时1到8号全部是标准球坏球在9、10、11、12四颗里。第二次称量9、10、11 vs 1、2、3右边放3个标准球。如果第二次还是平衡那坏球一定是12号。第三次拿12号 vs 1号标准球一称便知12号偏轻还是偏重。如果第二次左边重说明9、10、11中有一个偏重第三次称9 vs 10平衡就是11偏重否则谁重谁就是坏球。如果第二次左边轻说明9、10、11中有一个偏轻第三次称9 vs 10平衡就是11偏轻否则谁轻谁就是坏球。这个分支的核心技巧是用“标准球”当参照物。第一次平衡后你已经拥有了8个标准球它们就像砝码一样可以随意取用问题从“找坏球”退化成“在4个球里找1个并且已经知道坏球就在其中”。3.3 第一次左重时怎么处理第一次不平衡时会复杂一些因为存在两种嫌疑方向。以第一次左重为例候选状态为1、2、3、4中有一个偏重或者5、6、7、8中有一个偏轻。注意9到12号此时已经是标准球。第二次采用交叉换位策略称1、2、5 vs 3、6、9其中9号是标准球。这个策略的精妙之处在于它把部分“重嫌疑”的球留在左盘部分换到右盘还引入了一个标准球人为制造出更细致的区分。如果第二次平衡说明嫌疑落在没有参加第二次称量的4号、7号、8号中。结合第一次左重的信息只可能是4号偏重、7号偏轻或8号偏轻。第三次称7 vs 8平衡则4号偏重谁轻谁就是那个偏轻的坏球。如果第二次左重说明嫌疑落在1号、2号、6号中对应1号偏重、2号偏重或6号偏轻。第三次称1 vs 2平衡则6号偏轻否则谁重谁偏重。如果第二次右重说明嫌疑落在3号、4号、5号中对应3号偏重、4号偏重或5号偏轻。第三次称3 vs 4平衡则5号偏轻否则谁重谁偏重。3.4 第一次右重时怎么处理对称处理第一次右重不需要重新想一套方案它完全是左重分支的镜像。把左重分支里的编号做对称映射1↔5、2↔6、3↔7、4↔8并把“重嫌疑”和“轻嫌疑”互换就得到右重分支的执行方案。第二次称5、6、1 vs 7、2、99号标准球。如果第二次平衡嫌疑落在3号偏轻、4号偏轻、8号偏重中第三次称3 vs 4平衡则8号偏重谁轻谁是坏球。如果第二次左重嫌疑是5号偏重、6号偏重、2号偏轻第三次称5 vs 6平衡则2号偏轻谁重谁坏。如果第二次右重嫌疑是7号偏重、1号偏轻第三次称7 vs 9号标准球7重则7号偏重平衡则1号偏轻。这里只要掌握了“保持左右盘数量一致”和“每称一次必须让三种结果都有明确归属”两个原则即使换了编号也不会乱。整个12球自适应方案到此闭环。4. 进阶玩法把三次称量写成固定编码表4.1 编码思路用三进制记录球的位置自适应方案虽然直观但它有一个隐藏缺陷第二次、第三次称什么取决于前面的结果不方便程序化也不方便记忆。其实还存在一种更漂亮的方案可以让三次称量完全固定下来中途不做任何调整。思路是把每个球当成一个“编码对象”。三次称量中这个球要么放左盘要么放右盘要么不上秤。我们用表示左盘用−表示右盘用0表示不上秤那么每个球就有一个长度为3的编码。核心约束有三条第一不能出现两个球编码互为相反数否则“甲偏重”和“乙偏轻”会产生完全相同的结果第二每一列的和−数量必须相等否则那一次称量左右盘球数不一致第三不能有编码全为0否则这个球永远不上秤坏了也判断不了轻重。4.2 直接照抄一套可用的固定三称方案下面给出一套我构造并验证过的固定编码表。每个三元组按“第1次、第2次、第3次”顺序排列表示该次放左盘−表示放右盘0表示不上秤。球号编码球号编码1 70 − −2 −80 − 3 − 9− 04 010− 0 05− 0 −110 − 06− 0 120 0 −按照这个表三次称量的具体操作就是第1次称1、2、3、4 vs 5、6、9、10第2次称1、2、4、9 vs 3、7、8、11第3次称1、3、6、8 vs 2、5、7、12你可以核对一下三次称量左右盘的球数都是4对4没有哪一次出现数量不等的情况。这也是这个方案能成立的最基本保障。4.3 三次结果反查表三次称完你会得到一个形如(a, b, c)的结果向量每一位只可能是“左重”“右重”“平衡”三种。反查规则很简单把它与编码表对比。如果结果向量等于某一行编码说明这个球偏重。比如结果是( −)它正好等于2号球的编码结论就是2号球偏重。如果结果向量等于某一行编码的相反数也就是把编码里的和−互换说明这个球偏轻。比如结果是(− − )它是2号编码( −)的相反数结论就是2号球偏轻。由于编码表在设计时保证了不重复、不互反所以任何一个结果向量最多只对应一个“球状态”组合不会出现“既像甲偏重又像乙偏轻”的二义性。我用程序对所有24种情况做过枚举结果是完全没有冲突。4.4 为什么编码表能保证不冲突这套表的构造逻辑可以理解为在27种三进制结果里挑出12对“镜像结果”分别分配给12个球每对镜像对应同一个球的偏重和偏轻。挑的时候有三条硬性要求不选全0编码不选互为相反数的两个编码保证每一列和−数量相等。这三个条件缺一不可。第一列如果不平衡第1次称量左右球数就不等结果会预先倾斜如果两个编码互反那么A球偏重和B球偏轻的结果会完全相同如果出现全0编码一个球三次都没上过秤即使最终锁定是它也无法判断轻重。理解了这三条你甚至能自己用回溯程序搜索出其他风格完全不同的编码表每个表都能解同一道题。5. 变体扩展13球、N球、已知轻重5.1 13球称3次能找出但不保证轻重既然三次结果有27种而13个球未知轻重一共只有26种状态理论上13球“找出坏球”是可行的。但前面说过要同时判断轻重必须满足更严格的镜像配对条件所以13球场景下会有一个球的状态无法完整判定。具体表现是无论怎么设计结果序列里总会出现一种情况能告诉你“坏球就是某个球”却无法同时告诉你它偏轻还是偏重。你可以理解为缺少的那一个“结果槽位”正好卡在轻重信息的关键位置。因此13球变体更适合讨论“如何用3次称量锁定坏球”而不是“如何用3次称量既锁定又判重”。5.2 已知坏球偏重或偏轻的N球问题如果题目提前告诉你坏球是偏重的问题会简单很多每次称量就退化成了标准的三分查找。第一次把球分成三等份任意两份上天平如果一边重坏球就在重的那份里如果平衡坏球就在没上秤的那份里。一次称量把范围缩小到原来的1/3。所以k次称量最多能处理的球数是3^k。比如3次最多可以处理27个已知偏重的球2次就是9个。这个结果和“未知轻重”时的12球形成了鲜明对比方向信息值多少钱在这里仅仅多知道一个“偏还是轻”就能把容量从约12个提升到27个。5.3 通用公式汇总把几个结论放在一起方便以后直接查场景k次称量最大球数3次代入未知轻重要求找出并判断轻重(3^k − 3) / 212未知轻重只要求找出坏球(3^k − 1) / 213已知坏球偏重或偏轻3^k27这些公式最大的价值是帮你判断一个变体题到底有没有解。如果出题人考你“16个球3次未知轻重找出并判断轻重”你可以直接说没解因为16已经超过上限12。反过来如果场景是“10个球3次未知轻重”你有充足的裕量甚至可以采用更简单粗暴的分组方式。5.4 程序化验证的入口有了编码表可以用一小段Python代码验证方案是否真的无冲突。思路是把每个“球状态”代入编码表计算它对应的三次结果向量然后检查是否有两个不同状态产生同一个向量。codes { 1: (1, 1, 1), # 球1三次都在左盘 2: (1, 1, -1), 3: (1, -1, 1), 4: (1, 1, 0), 5: (-1, 0, -1), 6: (-1, 0, 1), 7: ( 0, -1, -1), 8: ( 0, -1, 1), 9: (-1, 1, 0), 10: (-1, 0, 0), 11: ( 0, -1, 0), 12: ( 0, 0, -1), } results {} for ball, code in codes.items(): for weight in (1, -1): # 1 偏重-1 偏轻 r tuple(code[i] * weight for i in range(3)) results.setdefault(r, []).append((ball, weight)) conflict [r for r, cases in results.items() if len(cases) 1] print(冲突数量:, len(conflict))运行结果会输出“冲突数量: 0”说明这套固定三称方案在全部24种情况下都能得到唯一结论。如果你想自己设计一套新编码表也可以把这段代码当作验证器配合回溯搜索函数使用。6. 实操踩坑记录与经验心得6.1 最容易翻车的三个细节第一个坑是第一次称量就贪多。有人觉得“多称几个球效率更高”直接拿6个球对6个球上天平。结果一旦不平衡面对的是6个偏重嫌疑和6个偏轻嫌疑混合在一起的12种情况后续两次根本拆不完。这也是这道题反直觉的地方你一次称的量太多反而把剩余可能性压得不够均匀。第二个坑是忽略标准球。第一次称量平衡后你已经拥有了8个标准球它们是后续解题的关键砝码。很多人在这一步还在“用未知球去称未知球”其实大可以大胆地把标准球放上天平这会让判断轻松很多。第三个坑是编码方案里出现互反编码。我最初尝试固定三称方案时就踩过这个坑看似左右盘数量都平衡编码也不重复但两组编码互为相反数导致“甲偏重”和“乙偏轻”的结果一模一样直到写程序验证才发现。所以只要涉及编码类方案程序化穷举验证永远是最后一道安全网。6.2 常见问题速查表问题快速答案第一次应该称几个球12个球时称4 vs 4保证每种分支剩余候选数均衡第一次不平衡时重的那一侧一定有坏球吗不一定可能是轻的一侧中有球偏轻已有一个标准球时该怎么做尽量把标准球放上天平作参照可以大幅简化判断13个球3次能判断轻重吗只能保证找出坏球不能保证同时判断轻重编码表中为什么不能有互为相反数的编码否则“A偏重”和“B偏轻”会产生相同结果序列怎么快速验证一套方案把所有“球状态”仿真一遍检查结果向量是否唯一6.3 个人经验这个题练的是什么我在实际研究这个问题时最大的体会是它练的不是“会称球”而是“会系统性地逼近结论”。从信息量估算极限、到三分支切割候选集、再到编码表设计每一步都逼着你把“下一步该做什么”想清楚而不是凭感觉操作。我做程序化验证时最快定位问题的办法不是反复试称重方案而是先把所有“球状态”穷举一遍看哪个结果冲突了再倒推是哪一步编码设计不满足约束。如果你也想把这道题变成自己的“思维肌肉记忆”我建议你找一张纸和一支笔先不看任何答案自己从“每次称量有三种结果”这句话出发试着推一套12球方案。推不出来也没关系再对照这篇文章的编码表一行一行验证“为什么这样可以”。几次之后你会发现自己面对这种多分支问题时不再只靠背套路而是能真的从原理出发推导方案了。
