第一次被12个球的问题摁在桌前想了一整个下午,是在帮朋友准备一份逻辑题的讲解稿。当时我以为这只是个脑筋急转弯,称几次就能蒙出来,结果越推越乱,最后把草稿纸撕了三张才回过味来——这根本不是靠灵光一闪能解决的问题,它背后是一套很硬的信息论账本。天平秤球问题就是这样一道题:看着简单,几个球、一架天平、三次机会,但它把"信息量""编码""平衡约束"这些平时藏在工程里的东西全摊在了明面上。我后来在工作中遇到过类似的排查场景,比如从一堆几乎一样的样本里定位那个异常件,用的就是当年推这道题留下的思路。所以这篇东西写给两类人:一类是第一次见到这道题、想搞懂"为什么三次刚好够"的朋友;另一类是早就背下答案、但每次被追问"为什么是12不是13"就卡壳的人。我会从一个从业者的角度,把这道题从题目本身、上界证明、完整方案、程序化求解到常见变体,一层层拆开讲透,让你不但会称,还能讲清楚每一步的来龙去脉。
1. 先搞清楚题目:天平秤球问题到底是什么
这道题流传的版本很多,措辞一变,条件就跟着变,所以第一步必须把题面钉死,否则后面所有的推理都会建立在流沙上。
1.1 标准版本的完整表述
最经典的版本是这样:有12个外观完全一样的球,已知其中恰好有一个是次品,次品和好球的唯一区别是重量不同——注意,题目没有告诉你次品是偏重还是偏轻,这正是难点所在。你手边有一架天平,也就是那种只能给出"左重""右重""平衡"三种结果的称重工具,没有砝码,没有刻度。要求你在三次称重之内,不但要把那个次品球找出来,还要判断出它究竟是偏重还是偏轻。
我见过不少人第一次听到"还要判断偏重偏轻"时会觉得这是额外加码,其实这才是问题的核心约束。如果只要求找出次品而不判断轻重,那题目会简单一档,因为你可以放弃一部分信息。举个最直接的对比:如果题目一开始就告诉你"次品偏重",那三次称重能处理的球数会明显多于12个。所以"未知轻重"这四个字,直接决定了整道题的难度上限。
这里还有个容易被忽略的隐含条件:天平本身是理想的,不存在精度误差,也不会因为你放球的手法而抖动。这听起来是废话,但在实际推演里很关键,因为它保证了"平衡"是一个确定的结果,而不是概率事件。凡是把现实中的称重误差代入进来的人,最后都会陷入"平衡也可能有微小偏差"的泥潭,那是把数学题做成了物理题,方向就偏了。
1.2 为什么这题经久不衰
这类题能在面试、智力测试、算法入门里反复出现,不是因为它有多冷门,而是因为它同时踩中了好几个训练点。第一,它逼着你去做信息量的估算,也就是先算清楚"理论上够不够",再动手设计步骤。很多人上来就乱称一通,称到第三次发现还有两种可能没排除,问题就出在跳过了估账这一步。第二,它考察对"对称性"和"约束"的敏感度,天平左右盘球数必须相等的这个限制,看似理所当然,实则是压死13球方案的那根稻草。第三,它是一个可以完全程序化的问题,你写几十行代码就能把方案暴力搜出来,这对建立"数学问题可计算"的直觉很有帮助。
我自己对它的偏爱,是因为它特别适合拿来讲解"怎么把模糊的直觉变成可验证的结构"。你随便问一个人"三次称重最多几个球",多数人会给个感觉,可能是10个,也可能是15个,但很少有人能说清楚这个数字是怎么来的。而一旦你掌握了那套估算方法,后面无论题目变成13个球、还是变成每个球可能是次品也可能不是,你都能自己重新算一遍,而不是去背答案。这才是这类题真正的价值——它给的不是答案,而是一套可迁移的推导框架。
2. 动手之前先算账:信息论给出的上界
在任何方案设计之前,先问自己一个问题:三次称重,理论上有多少种可能的结果组合?答案算出来,上界基本就定了。这个顺序不能反,否则你会在细节里绕不出来。
2.1 每次称重的三种结局
天平每次称重,只有三种可能:左盘重、右盘重、平衡。这个没什么争议。那么三次称重串起来,结果组合的总数就是3乘3乘3,等于27种。你可以把这27种结果想象成一棵三叉树的27个叶节点,每一次称重就是你往下走一层,走三次就落在某个叶子上。
把27种结果和题目要求对应起来。12个球,每个球有两种状态(偏重或偏轻),那么需要区分的情况总数是12乘以2,等于24种。24小于27,所以从纯信息量的角度看,三次称重是够用的,还有3种结果的余量。这一步估账很关键,它告诉我们"理论上可行",你才值得花力气去构造具体方案。如果这里算出来可能情况比结果还多,那无论如何设计都是白搭,直接换思路即可。
但这里埋着一个坑:24虽然小于27,可27种结果里并不是每一种都能被方案用上。最典型的是"三次全平衡"这个结果。如果一个方案在每次称重时都把球分散到左右两盘,那么只要有一个次品存在,就必然会在某一次称重里打破平衡,全平衡这个结果根本不会出现。这就意味着实际可用的结果数要少于27,余量比表面上看起来更紧。这个观察很重要,它是后面卡死13球方案的伏笔。
2.2 一个奇偶性证明:为什么12就是极限
既然24种情况对27种结果还有富余,那为什么13个球就不行?13个球需要区分的情况是26种,26仍然小于27,按理说应该也能塞进去。这时候光靠数数的估账就不够了,得请出更细的约束——每次称重左右盘球数必须相等带来的奇偶性。
我们把每个球在三次称重中的"出场方式"编码成一个三元组,每一位取左盘、右盘或不放。为了让结果能够区分,我们约定球i的编码和它的相反向量不能同时代表两个球,也就是说,如果把某次称重的左右盘对调,结果会整体翻转,那么一个"偏重"的球和一个"偏轻"的球就会产生相反的结果,这种成对关系正好用来编码轻重。
关键来了:所有非零的三元组一共有26个,它们两两配成13对相反向量。要区分一个球的轻重,就得占用一整对,也就是说一个球对应一对结果。13个球,正好要用掉全部13对,也就是全部26个非零结果,一个不剩。
现在看第一次称重的平衡条件。在26个非零三元组里,第一位是正的有9个,第一位是负的有9个,第一位是0的有8个。配成13对之后,第一位非零的码共配出9对,第一位为0的码配出4对。如果你从每对里挑一个代表选出来给13个球用,那么第一位为正的代表个数和第一位为负的代表个数之和必然等于9。而天平第一次称重要平衡,要求左盘的球数等于右盘的球数,也就是第一位为正的球数等于第一位为负的球数。两个相等整数的和是9,也就是要求这个和是偶数,但9是奇数,矛盾。
所以13个球在没有任何参考球的情况下,是构造不出合法方案的。这个奇偶性证明非常干净,它解释了为什么3次称重的上限是12。推到一般情形,n次称重未知轻重、没有额外参考球时,能处理的球数上限是(3^n-3)/2;n取3,(27-3)/2,正好等于12。你可以用这个公式验证其他次数:n取2,(9-3)/2等于3,两次称重能处理3个球;n取4,(81-3)/2等于39,四次能处理39个。数字对得上,说明这套推导是自洽的。
2.3 有参考球时为什么能多一个
顺着上面的证明,你会发现矛盾点就在于那个9是奇数。如果旁边有一个确定的好球,情况就变了。你可以在第一次称重时把这个已知好球放到某一边补位,让它把奇偶性掰回来。这时候上限就抬升到(3^n-1)/2,n取3时等于13。所以多了个已知好球,就能多处理一个球,从12变成13。
这个细节在实战里很有用。有时候题目会变形成"你有一个标准球"或者"有一批已知正常球",很多人没意识到这多出来的一个球就是靠它撑起来的,反而还在那死磕12个球的方案。反过来,如果你的方案里用到了已知好球去补位,面试官问"如果没有这个好球怎么办",你得能答出那就只能降到12个,多出来的那个球要靠最后一步的特殊处理,或者根本处理不了。把这条边界记清楚,很多变体题就迎刃而解了。
3. 分组法的完整推演:12个球怎么称
估账解决的是"够不够"的问题,接下来才是"怎么做"。12球的标准解法我推荐用分组法,因为它的每一步都能讲清楚动机,而不是靠记一张神秘的对照表。
3.1 第一次称重的设计
先给12个球编号,从1号到12号,方便后面指认。第一次称重,最自然的选择是把球分成三组,每组4个,然后拿两组上天平。我把它记为:左盘放1、2、3、4号,右盘放5、6、7、8号,9、10、11、12号先搁一边。
为什么是4对4?因为要最大限度利用这一次称重。如果放得少,比如1对1,那第一次的结果只能排除掉很少的球,剩下三次机会压力巨大。如果放得多,比如5对5,也没必要,因为剩下待定的球数和可能性已经不多了。4对4这个划分,恰好让第一次称重产生三种结果后,每种结果剩下的可能性都在后续两次称重的能力范围内。这是设计称重方案的一个通用原则:让每一次称重尽量把当前的可能性集合切成三个大小接近的部分,而不是浪费在无所谓的划分上。
第一次称重后会出现三种情况:平衡、左盘重、右盘重。下面逐个拆解。
3.2 平衡分支:次品在9到12号里
如果第一次称重平衡,好消息是1到8号全部是好球,次品一定在9、10、11、12号里。更妙的是,现在你手上有8个确定的好球可以当参考。第二次称重,我安排左盘放9、10、11号,右盘放1、2、3号,这三个是已知好球。注意这里没有放12号。
看第二次称重的结果。如果平衡,说明9、10、11号也都是好球,次品只能是剩下的12号。但这时候你只知道12号是次品,还不知道它是轻是重。第三次称重,把12号放左盘,随便拿一个已知好球比如1号放右盘。12号那边重,它就是偏重;12号那边轻,它就是偏轻。这一步只是给12号定个性,不承担找人的任务,所以很轻松。
如果第二次称重左盘重,也就是9、10、11号这边压下去了,说明次品在这三个球里而且偏重。第三次称重,拿9号和10号上天平一对一对决。如果平衡,次品是11号且偏重;如果9号那边重,次品是9号且偏重;如果10号那边重,次品是10号且偏重。三种结果对应三个候选,刚好。
如果第二次称重左盘轻,逻辑完全对称,说明9、10、11号里有一个次品偏轻。第三次还是拿9号对10号,平衡则11号偏轻,9号轻则9号是次品,10号轻则10号是次品。这一整套下来,平衡分支只用两次称重就干净利落地解决了,剩下的球数和结果数卡得很准。
3.3 左重分支:一整套推理链
真正考验人的是第一次称重不平衡的分支。假设第一次称重结果是左盘重,即1、2、3、4号重于5、6、7、8号。这时候你能推出的信息是:次品要么是1到4号里某个偏重的,要么是5到8号里某个偏轻的。9、10、11、12号全是好球。
第二次称重要精心设计,既要缩小范围,又要让第三种可能结果都有意义。我的安排是:左盘放1、2、5号,右盘放3、6、9号。这里用到了一个关键技巧——把上一轮里"可能偏重"的球和"可能偏轻"的球混在一起称,同时借9号这个已知好球来凑平衡。左盘是1、2、5,右盘是3、6、9,两边各三个球,满足平衡条件。
现在看第二次称重的三种结果。如果平衡,说明1、2、5、3、6、9号都没问题,次品只能是4、7、8号之一。结合第一轮的结论,4号只可能偏重,7号和8号只可能偏轻。第三次称重拿7号和8号对拼:如果平衡,次品是4号且偏重;如果7号那边轻,次品是7号且偏轻;如果8号那边轻,次品是8号且偏轻。注意7号和8号都只可能偏轻,不可能偏重,所以天平只会朝一边倾斜或平衡,这正好对应三个候选。
如果第二次称重仍然是左盘重,说明左盘的1、2、5号里有问题,或者右盘的3、6号里有问题,但结合第一轮的信息能大幅收窄:5号在第一轮属于可能偏轻的组,它不可能偏重;3号在右盘且第一轮属于可能偏重的组,它偏重的话会让右盘更重,与左盘重矛盾。所以只可能是1号偏重、2号偏重,或者6号偏轻。第三次拿1号和2号对拼:平衡则6号偏轻,1号重则1号是次品,2号重则2号是次品。
如果第二次称重变成左盘轻,说明左盘的1、2、5号轻了,或者右盘重了。结合第一轮,1号和2号只可能偏重不可能偏轻,所以排除;右盘的3号可能偏重,会造成右盘重,符合左盘轻的现象;左盘的5号可能偏轻,也会造成左盘轻。所以候选是5号偏轻或3号偏重。第三次拿5号和一个已知好球(比如9号)对比:如果平衡,则3号偏重;如果5号轻,则5号偏轻。5号不可能比重,因为第一轮信息排除了它。
3.4 右重分支与完整决策表
第一次称重右重的分支,整套推理跟左重分支完全镜像。左重的方案里,凡是"偏重"的判断换成"偏轻","偏轻"的换成"偏重",左右对称即可得出结果。为了让你能直接抄作业,我把所有情形整理成一张表,称重时照着走就行。
| 第一次结果 | 第二次称重 | 第二次结果 | 第三次称重 | 结论 |
|---|---|---|---|---|
| 平衡 | 9,10,11 对 1,2,3 | 平衡 | 12 对 1 | 12号,看12轻重定性 |
| 平衡 | 9,10,11 对 1,2,3 | 左重 | 9 对 10 | 平衡11重;9重9重;10重10重 |
| 平衡 | 9,10,11 对 1,2,3 | 左轻 | 9 对 10 | 平衡11轻;9轻9轻;10轻10轻 |
| 左重 | 1,2,5 对 3,6,9 | 平衡 | 7 对 8 | 平衡4重;7轻7轻;8轻8轻 |
| 左重 | 1,2,5 对 3,6,9 | 左重 | 1 对 2 | 平衡6轻;1重1重;2重2重 |
| 左重 | 1,2,5 对 3,6,9 | 左轻 | 5 对 9 | 平衡3重;5轻5轻 |
| 右重 | 1,2,5 对 3,6,9 | 平衡 | 7 对 8 | 平衡4轻;7重7重;8重8重 |
| 右重 | 1,2,5 对 3,6,9 | 左重 | 5 对 9 | 平衡3轻;5重5重 |
| 右重 | 1,2,5 对 3,6,9 | 左轻 | 1 对 2 | 平衡6重;1轻1轻;2轻2轻 |
这张表看起来有9行,但实际执行时你只会走到其中一条路径上。第一次称重把可能性切成三块,第二次再切一次,第三次定位,全程不超过三次称重。你在实际操作中不需要背整张表,只要理解每一步"为什么这么选球"的逻辑,现场推也推得出来。
4. 换个思路:三进制编码法
分组法适合手工推演和讲解,但如果你要处理更多球数,或者想用程序自动生成方案,就该换一套更结构化的思路——编码法。它把称重问题翻译成向量和方程,虽然抽象一点,但一旦转过弯来,威力比手工分组大得多。
4.1 把球映射成三进制向量
核心想法是这样的:给每个球分配一个三元组,三个分量分别对应三次称重,每一位取正、负或零,正表示这个球放在左盘,负表示放在右盘,零表示这次不放它。这样,一个球的完整"出场安排"就被完整记录下来了。
为什么要用正负零这套编码?因为它和天平的三种结果天然对应。对某个球来说,如果它偏重,那么它放在左盘就会让左盘沉,对应结果为正;放在右盘就会让右盘沉,对应结果为负;不放就不影响结果,对应零。所以单纯一个偏重的球,会让整场称重结果序列恰好等于它的编码向量。如果它偏轻,效果正好相反,结果序列等于它编码的相反向量。这就是为什么一个球要占用"一对"结果——偏重走一个方向,偏轻走反方向。
编码法有个硬性约束:任何两个球不能使用互为相反数的编码。原因很明显,如果球A的编码是球B编码的相反数,那么"球A偏重"和"球B偏轻"会产生一模一样的结果序列,天平区分不出来。所以每对相反向量只能分配给一个球,这也是为什么有时候要绕开某些组合。
4.2 用程序暴力搜索合法方案
手工找一组合法编码很费劲,但这事特别适合交给程序。思路分三步:先把所有非零三元组按相反数配对,得到13对;然后从这13对里挑出12对(或者全部13对再想办法平衡),每对选一个方向;最后检查每一次称重的平衡条件——左盘球数必须等于右盘球数,也就是每个坐标上正分量的个数要等于负分量的个数。下面这段代码用暴力枚举就能搜出合法方案:
from itertools import product # 生成所有非零三元组作为候选编码 codes = [c for c in product([1, 0, -1], repeat=3) if any(c)] # 按相反数配对 pairs = [] used = set() for c in codes: neg = tuple(-x for x in c) if c in used or neg in used: continue pairs.append((c, neg)) used.add(c) used.add(neg) print("相反数对数量:", len(pairs)) # 枚举丢掉哪一对、每对选哪个方向,找到满足平衡的方案 solution = None for drop in range(len(pairs)): remain = [pairs[i] for i in range(len(pairs)) if i != drop] for choices in product([0, 1], repeat=len(remain)): selected = [remain[i][choices[i]] for i in range(len(remain))] if all(sum(x[k] for x in selected) == 0 for k in range(3)): solution = selected break if solution: break for idx, c in enumerate(solution, 1): print(f"球{idx}: {c}")跑一遍你会发现,13对里恰好要丢掉一对,剩下的12对才凑得出每次称重左右各相等。丢掉的是哪一对其实有多种可能,程序会给出第一个可行解,你可以改条件找不同的方案。这段代码的价值在于,它把"设计称重方案"这件事从玄学变成了搜索问题,你想验证12球、13球、甚至更多球,改个参数就行。
4.3 结果如何解读
有了编码,解读变得极其机械。三次称重做完,把结果记成一个向量,比如"左重、平衡、右重"就记成(1, 0, -1)。然后拿这个向量去比对所有球的编码:如果它正好等于某个球的编码,那个球就是次品且偏重;如果它等于某个球编码的相反数,那个球就是次品且偏轻。因为所有球的编码两两不互为相反数,所以这个比对是唯一可解的,绝不会出现两个球都匹配的情况。
这套解读法特别适合写进排查工具或者自动化脚本里。你甚至可以把编码表和比对逻辑固化成一个小程序,输入三次结果,直接输出结论,连人脑推理都省了。我自己在讲这道题时,习惯先用分组法讲清楚直觉,再用编码法收个尾,让听众明白这件事不仅有巧解,还有一套通用的、能编程的框架。两种方法互相印证,理解会扎实很多。
5. 常见变体与扩展玩法
把基础版本吃透之后,你会发现这道题能变出很多花样。这些变体在面试和技术交流里出现频率很高,提前理顺逻辑,临场不容易慌。
5.1 已知次品偏重或偏轻
如果题目明确告诉你"次品偏重",难度会大幅下降。原因在于,一个偏重的球对应的结果向量就是它的编码本身,不需要再占用相反方向来编码"偏轻"这种状态。每一次称重的三种结果可以更充分地利用,能处理的球数随之增加。三次称重、已知偏重的情况下,理论上可以处理到27个球,也就是3的3次方。你可以这么理解:已知偏重时,每次称重的三种结果不再被"轻重双向"分摊,信息利用率翻倍。
具体的操作思路是:把球按三进制编号,然后把每一位上为1的球放左盘、为2的球放右盘(或者反过来),使每次称重左右盘球数相等。最后哪种结果组合出现,就指向哪编号的球。这里唯一要小心的是,全零编码不能用,因为那意味着球从不参与称重,无法被定位。所以实际能处理的球数是3的n次方减掉全零的那一个,也就是27减1,26个是稳妥上限。这个跟未知轻重时的12对比一下,你就明白"已知条件"这部分省下来的信息量有多可观。
5.2 13个球的处理方式
前面证明过,13个球在没有参考球时是构造不出合法方案的。但如果题目额外给你一个确认的好球,或者允许你"只找出次品、不必判断轻重",13球就能处理了。这两种情况下,13号球可以借助外部已知好球来补平衡,或者干脆放弃轻重判断,把它对应到那个用不上的结果上。
实操层面,如果你真的遇到13球且没有参考球,正确的回应不是硬凑方案,而是指出这做不到,并说明理由——那个奇偶性矛盾就是最好的论据。这反而是加分项,因为它显示你不是在背答案,而是真的理解了上界。我见过有人为了凑出13球方案,强行让某个球重复称重,表面上称完了,实际上方案在特定情况下会自相矛盾,这种错误在面试里是硬伤。
5.3 n次称重的通项规律
把结论汇总成一张表会更清楚。设n为称重次数,未知轻重且无参考球时,能处理的球数上限是(3^n-3)/2;有参考球时是(3^n-1)/2;已知偏重或偏轻时接近3^n。
| 称重次数n | 未知轻重无参考球 | 未知轻重有参考球 | 已知偏重或偏轻 |
|---|---|---|---|
| 2 | 3 | 4 | 9 |
| 3 | 12 | 13 | 27 |
| 4 | 39 | 40 | 81 |
| 5 | 120 | 121 | 243 |
盯着这张表看,能看出一个规律:随着次数增加,无参考球和有参考球的上限差距始终是1,这个1就是那根"补平奇偶性"的救命稻草。而未知轻重和已知偏重之间隔了大约一半,这半个身位就是"双向信息"的代价。记住这张表的生成逻辑,比死记硬背数字有用得多,因为面试官很可能追问n等于4、5时的数字,你现场推也能推出来。
6. 踩过的坑与实操心得
这道题我推过很多遍,也看过别人推,踩的坑和总结的经验还挺有代表性,挑几个最典型的说说。
6.1 手工推演最容易错的三个地方
第一个坑是在第二次称重时选错了混搭的球。很多人做左重分支时,会下意识地让1号到4号继续上场,却没有掺进5到8号里那些"可能偏轻"的球,导致第二次称重结束后,剩下的候选划分不均匀,第三次压不住。正确做法是像我前面写的那样,把"可能偏重"的球和"可能偏轻"的球按比例混在一盘里,让三种结果各自对应一组清楚的候选。
第二个坑是第三次称重忘了带参考球。当候选只剩两个球、且它们在同一侧倾向上逻辑相反时,直接拿它们对拼是没问题的;但如果两个候选是同向的(都只可能偏重或都只可能偏轻),直接对拼只能判断出"哪个有问题",判断不出"是不是都不是",因为两个都不称的情况才是答案。这时候必须拉一个已知好球进来当对照组,让平衡也能给出信息。记住这个口诀:候选同向要掺好球,候选异向可直拼。
第三个坑是结果解读时搞混了左右。天平的"左重"和"右重"是站在观察者视角的,可你的编码里正负号谁代表左谁代表右必须前后一致。我吃过一次亏,前面用正号代表左盘,后面解读时拿反了,结果把偏重读成偏轻,排查了半天。建议写方案时就在纸头标注清楚"正=左盘",全程不改。
6.2 面试或讲解时的表达技巧
被问到这道题时,千万别一上来就报答案。正确的顺序是先算上界,说清楚"三次称重27种结果,12球有24种情况,理论上够用",再说"但由于平衡约束,实际是12而非13"。这一开口就能让面试官知道你不是背的。
讲方案时,重点放在第一次称重为什么选4对4,以及不平衡分支里为什么要混搭称重。这两处是最能体现思维深度的地方。至于后面迭代的具体步骤,如果面试官不追问,可以概括说"每步把候选集切成三块",不必逐球念。如果他们追问细节,你再展开那张决策表。这种先框架后细节的讲法,比一上来密密麻麻念球号要清晰得多。
最后一个小经验:如果你在面试里一时推岔了,比如第二次称重设计得不理想,不要硬编到最后。及时承认"这一步切分不够均匀,我换一种方式",然后重新设计第二次称重,往往比硬撑到第三次再崩要体面得多。这题考的是思维过程,允许你有调整,展示出你能自查和纠错,反而是加分项。