第一次看到“天平秤球问题”是在一场面试前的算法复习里。原题不复杂12个外观完全一样的球其中1个质量异常可能比标准球重也可能比标准球轻给你一架没有砝码的天平最多称3次找出这个异常球并且说清楚它到底是偏重还是偏轻。真正动手推一遍才发现难的不是“想出一种称法”而是“想明白为什么这样称”。这道题看起来是个智力题本质上却是一门决策树设计课一次实验有三种结果三次实验只有27条结果路径你要在24种候选状态之间建立一一对应关系。本文就把我完整推演的过程写出来包括经典分组解法、三进制编码解法、13球无解的信息论证明以及我在实际讲这道题时踩过的坑。1. 先把问题的边界弄清楚三次称量的极限从哪来1.1 问题定义里最容易被忽视的那句话很多人第一次接触这个问题都会直奔“三分法”12个球分成3堆一次称两堆运气好一次就锁定运气差再来一次。这个思路在“知道异常球比标准球重”的时候完全正确但题目里那句“可能偏重也可能偏轻”直接让三分法失效。为什么如果第一次左边4个、右边4个天平左边沉了你是能得出“异常球在左边”吗不行。也可能是右边某个球偏轻。只要异常球有可能偏轻天平的倾斜方向就和“哪边有坏球”不是简单对应关系。你面对的不是“在12个球里找1个”而是“在24种状态里找1种状态”——每个候选球都有“偏重”和“偏轻”两种可能性。这题难就难在这里每一个球对应两种互斥状态你的称量方案必须同时区分“谁异常”和“异常方向”。如果你只是说“我找到了异常球但不知道它偏重还是偏轻”那不算完整解。因为异常方向本身也是题目要你回答的输出。1.2 一次称量到底能带来多少信息先做一道简单的信息量计算。天平一次称量有三种结果左边沉右边沉平衡三次称量最多能产生[ 3 \times 3 \times 3 27 ]种结果排列组合。12个球有多少种候选状态每个球可能是偏重或偏轻所以是[ 12 \times 2 24 ]24小于27信息量够用这就是“3次称12个球”在信息论层面可行的原因。反过来说为什么不能用2次2次称量最多产生9种结果最多区分9种状态连6个球的情况6×212种都覆盖不了。所以至少要3次而3次的理论上限看起来足够覆盖12个球。但这里有个关键认知信息量足够只是必要条件不是充分条件。因为天平的称量规则有物理约束——每次左右两个盘里放的球数必须相等。这个约束会卡掉很多看起来“信息够”的方案。1.3 13个球为什么就差一口气信息论上13个球有26种状态26仍然小于27按理说也应该可行。但实际不可行。我当年在这个问题上纠结了很久后来找到一个特别干净的证明假设第一次称量时左边放a个球右边放a个球必须相等那么有两种大情况第一次平衡异常球在没上秤的13-2a个球里候选状态数是2(13-2a)。剩下两次称量最多产生9种结果所以必须满足2(13-2a)≤9推出a≥4.5。第一次不平衡异常球要么在左边a个球里且偏重要么在右边a个球里且偏轻候选状态数是2a。同样必须满足2a≤9推出a≤4.5。两个条件合在一起要求a同时大于等于4.5又小于等于4.5也就是a4.5但a必须是整数。所以不存在这样的第一次称量。这就是13个球3次无解的根因不是信息量不够而是第一次称量这个物理动作无法同时照顾到“平衡后腾出的候选状态别太多”和“不平衡后留下的候选状态别太多”。12个球能做到是因为第一次称4对4时无论平衡还是不平衡两边都正好剩下8种候选状态恰好塞进剩余两次称量的9条路径里。2. 经典决策树解法四四分组后的三种走法理解完边界再来看可操作的解法。经典思路是第一次称量先把12个球分成三组每组4个编号为1-12。第一次称量1、2、3、4 对 5、6、7、8。剩下9、10、11、12暂时不上秤。这一步之后局面自然分成三大分支需要分别处理。2.1 第一次平衡异常球在9-12中如果第一次天平平衡说明1-8都是标准球异常球在9、10、11、12中。第二次称量9、10、11 对 1、2、3。右边是3个已知标准球左边是3个待定球。这里用标准球去“陪称”是整道题最关键的一步目的是把9、10、11当作一个整体去判断。如果第二次平衡异常球是12。第三次称12对1如果12重则12偏重如果12轻则12偏轻。如果第二次左边沉说明9、10、11里有一个偏重。第三次称9对10哪边沉哪边的球就是偏重异常球如果平衡则11偏重。如果第二次右边沉说明9、10、11里有一个偏轻。第三次称9对10哪边轻哪边的球就是偏轻异常球如果平衡则11偏轻。这个分支非常顺畅因为它把所有状态都收敛到了“至少给了你3个标准球”的有利局面。2.2 第一次左边沉需要一个不对称的第二次称量如果第一次是1、2、3、4 比 5、6、7、8更重事情就复杂了。这时候候选状态有8种1、2、3、4中有一个偏重或者5、6、7、8中有一个偏轻。9-12因为没上秤且第一次已经失衡所以必定是标准球。第二次不能再简单称“1、2、3、4 对 5、6、7、8”那样只是重复第一次的信息。要做一次“交叉换位”第二次称量1、2、5 对 3、6、9。注意右边用了9号标准球因为9在这个分支里确定是标准的。这样设计的目的是把8种候选状态打散到三个结果分支里每个分支最多3种方便第三次一称收尾。第二次结果分三种情况如果1、2、5这边更沉候选状态只剩三种——1偏重、2偏重、6偏轻。第三次称1对2。如果1沉则1偏重如果2沉则2偏重如果平衡则6偏轻。如果1、2、5这边更轻候选状态只剩两种——3偏重、5偏轻。第三次称3对标准球1。如果3更沉则3偏重如果平衡则5偏轻。如果第二次平衡候选状态只剩三种——4偏重、7偏轻、8偏轻。第三次称7对8。哪边轻哪边的球就是偏轻异常球如果平衡则4偏重。这个分支设计的巧妙之处在于它把第一次“左边沉”带来的方向信息保留住了同时用换位把“可能偏重的球”和“可能偏轻的球”混合在一个天平里让一个结果能同时排除掉多个状态。2.3 第一次右边沉对称镜像处理如果第一次是1、2、3、4 比 5、6、7、8更轻直接镜像对称处理即可。候选状态是1、2、3、4中有一个偏轻或者5、6、7、8中有一个偏重。第二次仍然称1、2、5 对 3、6、9。如果1、2、5这边更轻候选是1偏轻、2偏轻、6偏重。第三次称1对2。哪边轻哪边就是异常球如果平衡则6偏重。如果1、2、5这边更重候选是3偏轻、5偏重。第三次称3对标准球1。如果3更轻则3偏轻如果平衡则5偏重。如果第二次平衡候选是4偏轻、7偏重、8偏重。第三次称7对8。哪边重哪边就是异常球如果平衡则4偏轻。这套分支覆盖了24种状态里除“第一次平衡且9-11参与”的那些情况之外的全部路径没有遗漏也没有任何一条路径同时指向两个不同状态。3. 另一种解题路径用三进制编码一次设计三次称重经典决策树是“看一步走一步”的自适应策略。但如果把思路换一下可以做到更暴力也更优雅提前把三次称重方案全部定死然后直接查表。这就是三进制编码法。3.1 给每个球分配一个三位代号编码思想是这样的每个球用一个三位向量表示它在三次称量里的位置。第一位表示第1次称量里放哪边第二位表示第2次称量里放哪边第三位表示第3次称量里放哪边1表示放左盘-1表示放右盘0表示不参与这次称量如果某个球偏重那么它的实际称量结果就等于它的编码本身如果某个球偏轻实际结果就等于编码的相反数。所以只要给12个球分配12个三位向量并且保证任意两个球的编码互不相反那么24种状态就会对应24种不同的结果模式最后查表即可。分配编码时有两条硬约束在每一次称量中放左盘的球数必须等于放右盘的球数否则天平一开始就不平衡。任意两个球的编码不能是彼此的相反数否则一个球偏重和另一个球偏轻会产生完全相同的结果无法区分。我设计的一组可行编码如下球号三次称量编码意义11, 1, 0第1次左第2次左第3次不上21, -1, 0第1次左第2次右第3次不上31, 0, 1第1次左第2次不上第3次左41, 0, -1第1次左第2次不上第3次右50, 1, 1第1次不上第2次左第3次左60, 1, -1第1次不上第2次左第3次右7-1, 0, 0第1次右第2次不上第3次不上80, -1, 0第1次不上第2次右第3次不上90, 0, -1第1次不上第2次不上第3次右10-1, -1, -1三次都在右盘11-1, -1, 1第1、2次右第3次左12-1, 1, 1第1次右第2、3次左3.2 把编码表展开成三次称重计划按上面的编码整理成实际操作的三次称量称量次数左盘右盘第1次1、2、3、47、10、11、12第2次1、5、6、122、8、10、11第3次3、5、11、124、6、9、10可以先自己检查一下每次左右都是4个球满足盘面平衡条件12个球的编码两两之间没有相反数关系。这套方案和经典决策树最大的区别在于不需要根据上一次结果做判断称完三次直接拿着三次结果查表。3.3 结果反查一张表搞定全部24种状态实际称完三次后你会得到一个长度为3的结果序列比如“左、右、左”。然后按下面的表反查。球号偏重时的三次结果偏轻时的三次结果1左、左、平右、右、平2左、右、平右、左、平3左、平、左右、平、右4左、平、右右、平、左5平、左、左平、右、右6平、左、右平、右、左7右、平、平左、平、平8平、右、平平、左、平9平、平、右平、平、左10右、右、右左、左、左11右、右、左左、左、右12右、左、左左、右、右比如说三次结果是“右、右、左”查表发现11号球偏重时会产生这个序列所以结论就是11号球偏重。如果结果是“右、右、平”那只有1号球偏轻时会产生这个模式判断为1号球偏轻。编码法的哲学和决策树法完全相反决策树法是人脑跟着结果走编码法是提前把答案的“地址”安排到位最后一次性读取。放在计算机里前者是if-else嵌套后者是哈希查找。哪种更适合你取决于你是手算还是写程序。4. 从12推广到N个球一般规律与真实应用这类问题如果只看12个球很容易被当成一道可背答案的面试题。但只要把数字换一换它立刻变成一个组合搜索问题。4.1 已知异常球偏重时三次最多称27个球如果题目改成“已知异常球一定偏重”那难度断崖式下降。每次称量仍然有三种结果三轮三次就是三叉树最多能区分27个结果所以理论最多能处理27个球。而且这个上限可以达到第一次9对9平衡则去剩下9个里找第二次3对3第三次1对1每一步都是标准的三分查找。反过来如果知道异常球一定偏轻处理方式完全一样只是判断方向反一下。这个变体告诉我们一个直觉题目里的不确定性主要来源不是“多一个球”而是“不知道偏重还是偏轻”。4.2 不知轻重时的一般公式在“恰好有一个异常球且不知道轻重”的版本里k次称量最多能处理[ \frac{3^k - 3}{2} ]个球。当k2时结果是3个球验证一下确实可行当k3时结果是12个球正是经典的极限当k4时理论上最多可以处理39个球。这个公式背后的逻辑仍然和信息论相关3^k种结果模式里有三种模式在结构上被“预留”出来剩下的结果模式两两配对一组对应一个球的“偏重/偏轻”两种状态。但要强调这个公式给出的是理论上限不是所有情况都能轻松构造。正如前面证明的13个球问题虽然数字上满足信息量要求但在实际的称量平衡约束下就会翻车。4.3 13个球加一个标准球为什么可行13个球本身3次无解但如果再给你一个已知标准球局面就变了。第一次称量可以在左盘放4个未知球加1个标准球右盘放5个未知球。这样盘面仍然是5对5但参与搜索的未知球只有9个。如果平衡剩下4个未知球有8种状态剩余两次称量能覆盖如果不平衡左盘4个未知球偏重加上右盘5个未知球偏轻正好9种状态也正好卡进剩余两次称量的9条路径里。这个例子很能说明问题标准球在这个模型里不是冗余而是宝贵的“已知量”它可以帮助你调整盘面参与球数让平衡和不平衡两个方向都能塞进剩余的结果空间。4.4 现实世界里的影子这种模型到处都有影子。最直接的是伪币检测问题本质就是在一片相似物里用有限次测试定位异常项。计算机领域的纠错码设计也是同一个思想用若干位校验信息让错误发生时能定位到具体位置甚至能判断出错误的方向。现在的物流品控里常见的分组测试也是先把样本混合再通过一次检测结果缩小范围。这些场景里你花掉一次“实验”的代价换取三种结果的反馈和天平称球在信息结构上完全同构。5. 我在解这类题时踩过的坑与复盘这类题看起来答案只有几行但真正自己推一遍很容易掉进几个显眼的坑。5.1 最常见的翻车思路三分法的诱惑几乎所有新手都会先把球分成3堆然后称其中两堆。如果异常球“确定偏重”这个思路完美但一旦不知道轻重第一次称量如果失衡你会面临左边4个可能偏重或右边4个可能偏轻的8种状态。如果此时你直接继续在左盘集合里找偏重球就会漏掉右边偏轻的情况。这个错误的本质是把“未知方向”问题简化成了“已知方向”问题。正确做法是必须把“偏重”和“偏轻”当成两种并列候选状态来管理而不是把它们当作次要因素处理。你设计的每一次称量都要同时覆盖两个方向的可能性。5.2 第二次称量设计时最容易犯的错在第一次失衡的分支里第二次称量如果只是对称地称“1、2、3、4 对 5、6、7、8”得到的结果和第一次完全一样等于浪费了一次称量。经典的解法之所以用1、2、5对3、6、9这种不对称组合是因为它把候选状态重新洗牌让第三次称量无论出现什么结果都能唯一锁定。我自己在复盘时发现检查方案是否正确最好的办法不是凭感觉而是把所有候选状态逐个代入。比如某个分支下候选是3偏重和5偏轻你设计第三次称3对1标准球那就把两种情况都代进去看结果是否不同。出现“两个不同状态产生同一结果”的组合就是方案有漏洞。5.3 验证答案的实用办法想在面试里或者讨论中验证自己答案正确可以写一张决策树表每一行是一种候选状态每一列是三次称量的预期结果。只有当所有行对应的结果序列两两不同这个方案才算真正成立。编码法里那张反查表本质上就是这张决策树表的另一种呈现。如果你习惯用程序验证可以把12个球、一个异常标记、三次称量结果写成一个简单枚举脚本把所有候选状态跑一遍检查结果序列是否唯一。我第一次写这个验证脚本的时候立刻发现我一版方案里有两条状态的结果重复了这也是为什么我一直强调称球问题的答案必须靠状态结果唯一性来验证不能靠记忆和信心。5.4 这类问题后续还能怎么扩展如果你已经熟练掌握12球版本可以试试这些方向把球数改成13个只要求找出异常球不要求判断轻重看看是否比原题容易。允许第一次称量后使用已知标准球推演13球加标准球的完整策略体验“信息刚好卡满”的感觉。把称量次数从3次改成4次用公式(3^4 - 3)/2算出理论极限是39个球再尝试设计一个39球的称量分配表你会对编码法有更深的理解。我个人实际做下来最大的体会是这种题并不需要背答案。真正理解了“一次称量三种结果每次盘面必须平衡所有状态结果一一对应”这三个原则无论题目怎么改数字你都能从原理出发推出一个可行方案而不是靠灵光一闪。