1. 问题引入与核心价值“12枚硬币称重问题”是我在职业生涯早期一次技术面试中遇到的经典逻辑题它远不止是一个简单的脑筋急转弯。乍一看这只是一个关于天平找假币的谜题但深入下去你会发现它是一把绝佳的钥匙能打开算法思维、信息论和系统设计的大门。很多面试官青睐它不是想考倒你而是想观察你如何将一个模糊的需求拆解成清晰的逻辑步骤并最终构建出一个高效、鲁棒的解决方案。这恰恰是我们在处理复杂系统、设计数据流或排查线上问题时每天都在重复的核心能力。这个问题描述起来很简单你有12枚外观一模一样的硬币其中恰好有一枚是“假币”。假币可能比真币轻也可能比真币重但你不知道是轻是重。你有一架没有砝码的天平只能进行三次称量。目标是通过这三次称量不仅找出那枚假币还要确定它比真币轻还是重。我第一次面对这个问题时感觉信息量严重不足12个嫌疑对象每个都有两种“犯罪可能”轻或重而调查手段称重只有三次并且每次调查只能获得“左倾”、“右倾”或“平衡”三种结果之一。这怎么可能完成但正是这种“不可能”的感觉驱使我们去寻找信息的最优编码和解码方式。今天我就来彻底拆解这个问题不仅给出标准解法更分享如何将这种思维模式应用到实际的编程和系统设计中去。2. 问题本质与信息论基础在动手设计称重方案前我们必须先理解我们拥有的“资源”和需要完成的“任务”从信息论的角度进行量化分析。这是将直觉转化为可执行方案的关键一步。2.1 状态空间与信息熵首先明确问题的“状态空间”。我们有12枚硬币标记为1到12。其中一枚是假币且它要么轻要么重。因此所有可能的情况有第1枚轻、第1枚重、第2枚轻、第2枚重……第12枚轻、第12枚重。总共是12枚 × 2种情况 24种可能的最终状态。我们的目标是通过称量从这24种可能性中唯一确定出是哪一种。每一次称量就像一次实验会产生一个结果。这个天平有三种可能的结果左边重记作L、右边重记作R、两边平衡记作B。2.2 称量过程的信息获取上限那么三次称量最多能区分多少种不同的情况呢第一次称量有3种结果对于每一种结果进行第二次称量又有3种结果所以前两次最多能产生3 × 3 9种不同的结果路径对于这9条路径中的每一条进行第三次称量最终会产生9 × 3 27条不同的结果路径。27 24。这是一个至关重要的不等式。它从理论上证明了三次称量所蕴含的信息量27种可能的结果序列足以覆盖我们需要区分的24种情况。这给了我们解决问题的信心方案是存在的。我们的任务就是设计一种称重策略使得这24种情况能够均匀、无冲突地映射到那27条结果路径中去并且要留有余地因为2724我们甚至有3条路径是冗余的。注意这里的信息论分析是解题的“灯塔”。在实际面试或解决问题时即使你不能瞬间算出27你也应该向面试官展示这种量化思考的过程“我们需要区分24种状态每次实验有3种输出那么N次实验最多能提供3^N种信息编码。我们需要3^N 24所以N至少为3。这证明了三次称量在理论上是足够的。” 这种思维方式比直接抛出解法更有价值。2.3 策略选择决策树与自适应策略如何设计称量方案有两种核心策略预定义策略在第一次称量前就完全决定好三次称量分别放哪些硬币。无论第一次结果如何第二次、第三次的称量方案都是预先固定好的。这种策略构建的是一棵静态的决策树。自适应策略根据上一次称量的结果动态决定下一次称哪些硬币。这更符合我们自然的思考过程也更容易找到解法。我们通常采用自适应策略来思考和阐述。但无论是哪种策略其背后的决策树都必须满足从根节点第一次称量到每个叶子节点最终结论的路径即三次称量结果的序列必须唯一对应24种情况中的一种。3. 标准解法步骤拆解与逻辑推演下面我将采用自适应策略一步步推演出一个经典且对称优美的解决方案。请跟随我的思路重点关注每次决策背后的“为什么”。3.1 第一次称量建立基准与分组第一次称量的设计至关重要它要能达到两个目的1) 尽可能多地获取信息缩小嫌疑范围2) 为后续称量创造有利条件例如获得一部分“标准真币”。一个经过验证的优秀分组是将12枚硬币分成三组每组4枚。我们称量其中两组。左盘硬币 1, 2, 3, 4右盘硬币 5, 6, 7, 8未称硬币 9, 10, 11, 12现在天平有三种可能的结果情况 A天平平衡B这无疑是最好的情况之一。它直接告诉我们左盘1-4和右盘5-8这8枚硬币全部是真币。因为如果假币在这8枚中并且假币轻或重天平就不可能平衡。那么假币一定在未称量的那组9, 10, 11, 12中。情况 B天平左倾L即左边重。这说明要么左边有假币且假币重要么右边有假币且假币轻。此时未称量的9-12号硬币可以暂时认定为真币但还需后续确认不过在此分支下它们作为参照物是安全的。情况 C天平右倾R与情况B对称。即要么左边有假币且假币轻要么右边有假币且假币重。同样9-12号硬币暂时视为真币。第一次称量后我们成功地将24种可能性的大海分流成了三条主要的河流每条河流的“嫌疑犯”数量都大幅减少并且我们获得了一批宝贵的“已知真币”作为后续称量的砝码。3.2 第二次称量分支策略与信息精炼接下来我们需要针对第一次称量的三种不同结果设计第二次称量。这是整个方案中最精巧的部分。3.2.1 分支一第一次平衡B此时假币在9, 10, 11, 12中且我们手上有大量8枚确定无疑的真币。问题简化为4枚硬币中找1枚不知轻重的假币且有2次称量机会并拥有无限多的标准砝码真币。第二次称量设计如下左盘9号硬币 一枚真币例如1号右盘10号硬币 另一枚真币例如2号未称11, 12号硬币可能的结果及推理平衡B说明9和10都是真币因为真币真币 真币真币。假币在11和12中。第三次称量用一枚真币如1号与11号称量。若平衡则12是假币再通过一次与真币的称量或根据之前信息可判断轻重实际上此时我们不知道轻重需要额外信息这里有个关键点当假币锁定在2枚且不知轻重时第三次称量必须能同时判断出是哪一枚以及轻重。所以更优的第三次称量是拿11和12互称不对这样只能知道谁轻谁重但不知道标准重量。正确做法是用一枚真币与11号称。如果平衡则12是假币但轻重未知这里出现了逻辑漏洞我们需要回溯并修正方案。让我们重新严谨推理 实际上在B分支下假币在{9,10,11,12}中但我们不知道假币是轻是重。第二次称量9真 vs 10真如果平衡只能证明9和10重量相等它们要么都是真要么都是假且同轻或同重。但根据第一次平衡假币只有一枚所以9和10不可能都是假因此它们都是真币。假币在11和12中且我们仍不知其轻重。第三次称量取11号与一枚已知真币如1号称量。如果平衡则11是真币12是假币。但是我们无法知道12是轻是重问题出现了吗不我们还有一次称量机会吗没有了。这似乎是个死胡同。 这说明我的第二次称量设计有缺陷。经典的、能确保成功的第二次称量方案是左盘9, 10, 11右盘三枚真币例如1, 2, 3 这样如果左盘重则假币在9,10,11中且为重币如果左盘轻则假币在9,10,11中且为轻币如果平衡则假币是12但12的轻重依然未知不此时我们还有一次称量机会可以称量12与真币直接得知轻重。完美。 让我们按经典方案重述第二次称量经典方案左盘9, 10, 11右盘三枚真币1, 2, 3可能结果左重假币在9,10,11中且为重币。第三次称量比较9和10。谁重谁就是假重币平衡则11是假重币。左轻假币在9,10,11中且为轻币。第三次称量比较9和10。谁轻谁就是假轻币平衡则11是假轻币。平衡假币是12。第三次称量用12与任何一枚真币比较即可知12是轻是重。3.2.2 分支二第一次左倾L或右倾R这两个分支是对称的我们以第一次左倾L为例进行详解。此时嫌疑范围是{1,2,3,4}可能为重币或者{5,6,7,8}可能为轻币。而{9,10,11,12}是真币。第二次称量的设计需要能有效区分这8种可能性4枚可能重 4枚可能轻。一个巧妙的方案是进行“混编”左盘1, 2, 5 即一枚可能重的“嫌疑犯”1一枚可能重的“嫌疑犯”2和一枚可能轻的“嫌疑犯”5右盘3, 6, 9 即一枚可能重的“嫌疑犯”3一枚可能轻的“嫌疑犯”6和一枚已知的真币9未称4, 7, 8 即可能重的4可能轻的7和8分析第二次称量的结果平衡B说明左盘的{1,2,5}和右盘的{3,6,9}重量相等。由于9是真币那么1,2,5与3,6的重量组合必须与真币组合等价。这意味着什么嫌疑犯{1,2,3}如果重或者{5,6}如果轻都会破坏平衡。既然平衡了就说明{1,2,3,5,6}这五枚硬币的行为都符合真币特征。因此假币在未称量的{4,7,8}中。结合第一次左倾的线索左边重如果假币是4它必须是重币如果假币是7或8它必须是轻币。第三次称量比较7和8。如果7轻则7是假轻币。如果8轻则8是假轻币。如果平衡则4是假重币。左盘重L左盘重了。看看谁可能导致这个结果左盘中的1或2如果是重币会导致左重右盘中的6如果是轻币会导致右盘变轻从而显得左盘重。但右盘中的3如果是重币反而会导致右盘重这与左重矛盾。左盘中的5如果是轻币会导致左盘变轻这也与左重矛盾。因此可能的嫌疑犯缩小为{1重2重6轻}。第三次称量比较1和2。如果左边重则1是假重币。如果右边重则2是假重币。如果平衡则6是假轻币。右盘重R推理逻辑类似。可能导致右重的原因有右盘中的3是重币或者左盘中的5是轻币导致左盘轻显得右重。同时1或2是重币会导致左重与结果矛盾6是轻币会导致右盘轻也与结果矛盾。因此嫌疑犯缩小为{3重5轻}。第三次称量这已经很简单了。用3与一枚真币比较即可。但为了统一可以称量3和5不5是可能轻的。更直接取3与真币称。如果3重则3是假重币如果平衡则5是假轻币因为嫌疑只有这两个。通过这样精细的设计第二次称量无论出现什么结果都能将嫌疑范围缩小到2-3枚硬币并且明确了假币是“可能重”还是“可能轻”的子集从而让第三次称量可以一锤定音。3.3 第三次称量一锤定音与结论输出第三次称量的设计通常比较简单因为经过前两次的筛选我们面对的情况已经非常明确要么是2-3枚已知轻重属性的嫌疑币通过一次比较即可找出异常者要么是1枚孤立的硬币只需与真币比较一次即可知其轻重。关键在于第三次称量的方案必须根据第二次的结果动态决定。它没有固定的公式而是决策树上的最后一个分支。例如在“第一次平衡第二次左重”的情况下我们面对的是{9,10,11}三枚硬币且已知假币在其中且为重币。第三次称量只需比较其中两枚如9和10就能通过谁重或是否平衡来判断出假币。4. 思维延伸从谜题到工程实践解决了这个具体的12硬币问题固然有趣但它的真正价值在于其背后普适的思维模型。这些模型可以直接迁移到软件开发和系统设计中。4.1 分治与递归思想将12枚硬币分成3组每次称量排除掉至少一部分“真币”或确定一部分嫌疑犯的属性这正是分治算法的体现。在面对海量数据或复杂系统时我们首先思考的就是如何将其划分为更小、更易处理的子问题。例如在排查一个分布式系统的性能瓶颈时你不会同时检查所有服务。你会先通过监控指标第一次“称量”判断问题是出在接入层、业务逻辑层还是数据层。锁定某一层后再进一步检查该层内的具体服务或模块第二次“称量”直至定位到有问题的代码行或配置第三次“称量”。4.2 信息论与日志设计三次称量对应27种结果路径覆盖24种情况这体现了信息编码的效率。在我们的系统中日志和监控事件就是我们的“称量结果”。设计良好的日志等级DEBUG, INFO, WARN, ERROR和结构化字段就是为了用最少的数据量日志行数/体积携带最多的问题定位信息。冗余的、无结构的日志就像低效的称量方案查问题时需要翻看大量无关信息而精准的、结构化的日志能让你像这个谜题的解法一样通过有限的几次查询“称量”迅速收敛到问题根因。4.3 决策树与自动化运维整个称重过程构成了一棵完美的决策树。这棵树可以预先定义预定义策略也可以根据中间结果动态生成分支自适应策略。这正是自动化故障诊断和根因分析RCA系统的核心思想。我们可以将常见的故障场景、监控指标阈值、关联关系预先编写成决策规则当告警触发时系统自动沿着决策树执行检查命令、调用诊断API最终输出最可能的故障原因和修复建议极大提升了运维效率。4.4 状态空间与测试用例设计24种可能的“假币状态”可以类比为我们程序可能存在的缺陷状态。27种称量结果路径可以类比为我们设计的测试用例集合。一个好的测试套件其测试用例应该能像称量方案一样覆盖所有重要的、可能导致程序行为异常的状态组合并且尽可能高效用例数少但覆盖率高。思考如何用最少的测试用例发现最多类型的bug其本质和“用最少的称量次数区分所有假币可能性”是相通的。5. 常见误区与实战心得在向别人解释或自己思考这个问题时有几个坑很容易掉进去。这里分享我总结的几个关键点和心得。5.1 误区一忽视“轻重未知”的约束最经典的错误是假设自己知道假币是轻还是重。如果知道轻重问题会简化为二分查找3次称量足以从12枚中找出假币因为2^38 12? 等等2^38不足以区分12枚需要更多次。但若知道轻重可以用天平比较3次确实足够但策略不同。而“轻重未知”使得每个嫌疑对象都有两种可能状态空间翻倍大大增加了难度。任何解决方案如果没能在过程中同时推断出轻重都是不完整的。5.2 误区二第二次称量方案设计僵化很多人卡在第二次称量上因为他们试图用一个“对称”或“简单”的分组比如仍然像第一次一样拿4枚和4枚称。这在某些分支下尤其是第一次不平衡时是行不通的因为此时你拥有的信息是不对称的一部分硬币嫌疑重一部分嫌疑轻。必须利用好第一次称量后获得的“已知真币”和“嫌疑属性”信息设计一个“混编”的称量方案就像我们之前做的将可能重和可能轻的硬币与真币混合这样才能最大化信息获取。5.3 误区三认为存在唯一“标准答案”这个问题的解法不是唯一的。分组方式、第二次称量的具体排列都可以有变化只要逻辑自洽能构建出覆盖24种状态的决策树即可。在面试中展示你构建解决方案的过程——如何分析约束、如何设计实验、如何根据反馈调整——比单纯背诵一个答案重要得多。面试官更想看到的是你系统化的解决问题能力。5.4 实战心得从特例到通用的推导方法当你第一次遇到这类问题时不要试图直接想出12个硬币的解法。可以从更简单的情况开始推导建立直觉3枚硬币1次称量已知假币较轻很简单任意两枚一称即可。3枚硬币1次称量假币轻重未知不可能。因为一次称量只有3种结果但需要区分6种状态3枚×2种轻重。4枚硬币2次称量假币轻重未知可以解决吗状态空间是82次称量最多提供9种信息理论可行。试着设计一下能加深对“混编”策略的理解。通过解决这些小规模问题你能更好地理解信息量与状态空间的关系以及如何利用“已知标准件”真币进行比对。这种从简单到复杂、从特殊到一般的推导方法是解决任何复杂逻辑或算法问题的利器。6. 问题变种与扩展思考掌握了基础解法后我们可以思考一些变种问题这能进一步锻炼思维。6.1 变种一13枚硬币问题如果给你13枚硬币三次称量还能解决吗我们来计算一下状态空间 13枚 × 2种轻重 26种。三次称量的信息上限是27种。27 26理论上是可行的。但实际操作中你会发现因为27比26只多1方案必须设计得极其高效几乎不能有任何信息浪费。经典的12硬币方案有3条冗余路径27-243而13硬币方案只有1条冗余设计难度更大但仍然是存在的。这提醒我们理论上的可能性不等于构造的简易性。6.2 变种二知道假币较轻或较重如果提前知道假币是较轻的那么问题就变成了单纯的“找出异常项”。状态空间从24缩减为12。三次称量27种信息绰绰有余。实际上你可以用类似二分查找的策略第一次6 vs 6找到较轻的一组第二次3 vs 3找到较轻的一组第三次从3个中任取2个称平衡则剩下的是假币否则轻的是假币。这是一个更简单的信息检索问题。6.3 变种三天平有砝码或使用电子秤如果天平有砝码或者直接使用能读数的电子秤问题性质就完全变了。电子秤一次称量可以得到一个具体的重量数值通过一次称量所有硬币的总重量再与标准总重量比较就能直接计算出哪枚硬币是假的以及它的偏差。这从“信息论游戏”变成了“数学计算问题”。这告诉我们工具的能力决定了解决问题的范式。在工程中引入更强大的监控工具如分布式链路追踪、深度性能剖析工具往往能将复杂的排查问题降维打击。6.4 扩展到N枚硬币与K次称量这是一个更一般的数学问题给定N枚硬币1枚假币轻重未知用一架天平至少需要称量多少次K才能保证找出假币并知其轻重答案与信息论紧密相关我们需要找到最小的K使得 3^K 2N。因为每次称量有3种结果K次就有3^K种可能序列需要覆盖2N种状态N个位置×2种轻重。例如对于12枚硬币3^327 24所以K3。对于13枚3^327 26K也是3。对于更大的N我们可以用这个公式估算所需的最少称量次数。回过头看这个经典的面试题绝不仅仅是一个逻辑游戏。它是一个微缩的、关于如何在有限资源三次称量和不确定条件轻重未知下通过精心设计的实验称量方案来获取最大信息量从而唯一确定一个隐藏状态哪枚硬币、轻或重的完美案例。它所训练的分治、信息编码、决策树构建和递归思维是每一位优秀的工程师、数据分析师乃至产品经理都应具备的核心能力。下次当你面对一个复杂的、信息不全的难题时不妨回想一下这12枚硬币先定义清楚状态空间评估你获取信息的手段和能力然后设计一系列能够最大程度消除不确定性的实验或步骤。这就是理性解决问题的通用法门。 信息论与决策树实战：12硬币称重问题的算法思维与工程启示
1. 问题引入与核心价值“12枚硬币称重问题”是我在职业生涯早期一次技术面试中遇到的经典逻辑题它远不止是一个简单的脑筋急转弯。乍一看这只是一个关于天平找假币的谜题但深入下去你会发现它是一把绝佳的钥匙能打开算法思维、信息论和系统设计的大门。很多面试官青睐它不是想考倒你而是想观察你如何将一个模糊的需求拆解成清晰的逻辑步骤并最终构建出一个高效、鲁棒的解决方案。这恰恰是我们在处理复杂系统、设计数据流或排查线上问题时每天都在重复的核心能力。这个问题描述起来很简单你有12枚外观一模一样的硬币其中恰好有一枚是“假币”。假币可能比真币轻也可能比真币重但你不知道是轻是重。你有一架没有砝码的天平只能进行三次称量。目标是通过这三次称量不仅找出那枚假币还要确定它比真币轻还是重。我第一次面对这个问题时感觉信息量严重不足12个嫌疑对象每个都有两种“犯罪可能”轻或重而调查手段称重只有三次并且每次调查只能获得“左倾”、“右倾”或“平衡”三种结果之一。这怎么可能完成但正是这种“不可能”的感觉驱使我们去寻找信息的最优编码和解码方式。今天我就来彻底拆解这个问题不仅给出标准解法更分享如何将这种思维模式应用到实际的编程和系统设计中去。2. 问题本质与信息论基础在动手设计称重方案前我们必须先理解我们拥有的“资源”和需要完成的“任务”从信息论的角度进行量化分析。这是将直觉转化为可执行方案的关键一步。2.1 状态空间与信息熵首先明确问题的“状态空间”。我们有12枚硬币标记为1到12。其中一枚是假币且它要么轻要么重。因此所有可能的情况有第1枚轻、第1枚重、第2枚轻、第2枚重……第12枚轻、第12枚重。总共是12枚 × 2种情况 24种可能的最终状态。我们的目标是通过称量从这24种可能性中唯一确定出是哪一种。每一次称量就像一次实验会产生一个结果。这个天平有三种可能的结果左边重记作L、右边重记作R、两边平衡记作B。2.2 称量过程的信息获取上限那么三次称量最多能区分多少种不同的情况呢第一次称量有3种结果对于每一种结果进行第二次称量又有3种结果所以前两次最多能产生3 × 3 9种不同的结果路径对于这9条路径中的每一条进行第三次称量最终会产生9 × 3 27条不同的结果路径。27 24。这是一个至关重要的不等式。它从理论上证明了三次称量所蕴含的信息量27种可能的结果序列足以覆盖我们需要区分的24种情况。这给了我们解决问题的信心方案是存在的。我们的任务就是设计一种称重策略使得这24种情况能够均匀、无冲突地映射到那27条结果路径中去并且要留有余地因为2724我们甚至有3条路径是冗余的。注意这里的信息论分析是解题的“灯塔”。在实际面试或解决问题时即使你不能瞬间算出27你也应该向面试官展示这种量化思考的过程“我们需要区分24种状态每次实验有3种输出那么N次实验最多能提供3^N种信息编码。我们需要3^N 24所以N至少为3。这证明了三次称量在理论上是足够的。” 这种思维方式比直接抛出解法更有价值。2.3 策略选择决策树与自适应策略如何设计称量方案有两种核心策略预定义策略在第一次称量前就完全决定好三次称量分别放哪些硬币。无论第一次结果如何第二次、第三次的称量方案都是预先固定好的。这种策略构建的是一棵静态的决策树。自适应策略根据上一次称量的结果动态决定下一次称哪些硬币。这更符合我们自然的思考过程也更容易找到解法。我们通常采用自适应策略来思考和阐述。但无论是哪种策略其背后的决策树都必须满足从根节点第一次称量到每个叶子节点最终结论的路径即三次称量结果的序列必须唯一对应24种情况中的一种。3. 标准解法步骤拆解与逻辑推演下面我将采用自适应策略一步步推演出一个经典且对称优美的解决方案。请跟随我的思路重点关注每次决策背后的“为什么”。3.1 第一次称量建立基准与分组第一次称量的设计至关重要它要能达到两个目的1) 尽可能多地获取信息缩小嫌疑范围2) 为后续称量创造有利条件例如获得一部分“标准真币”。一个经过验证的优秀分组是将12枚硬币分成三组每组4枚。我们称量其中两组。左盘硬币 1, 2, 3, 4右盘硬币 5, 6, 7, 8未称硬币 9, 10, 11, 12现在天平有三种可能的结果情况 A天平平衡B这无疑是最好的情况之一。它直接告诉我们左盘1-4和右盘5-8这8枚硬币全部是真币。因为如果假币在这8枚中并且假币轻或重天平就不可能平衡。那么假币一定在未称量的那组9, 10, 11, 12中。情况 B天平左倾L即左边重。这说明要么左边有假币且假币重要么右边有假币且假币轻。此时未称量的9-12号硬币可以暂时认定为真币但还需后续确认不过在此分支下它们作为参照物是安全的。情况 C天平右倾R与情况B对称。即要么左边有假币且假币轻要么右边有假币且假币重。同样9-12号硬币暂时视为真币。第一次称量后我们成功地将24种可能性的大海分流成了三条主要的河流每条河流的“嫌疑犯”数量都大幅减少并且我们获得了一批宝贵的“已知真币”作为后续称量的砝码。3.2 第二次称量分支策略与信息精炼接下来我们需要针对第一次称量的三种不同结果设计第二次称量。这是整个方案中最精巧的部分。3.2.1 分支一第一次平衡B此时假币在9, 10, 11, 12中且我们手上有大量8枚确定无疑的真币。问题简化为4枚硬币中找1枚不知轻重的假币且有2次称量机会并拥有无限多的标准砝码真币。第二次称量设计如下左盘9号硬币 一枚真币例如1号右盘10号硬币 另一枚真币例如2号未称11, 12号硬币可能的结果及推理平衡B说明9和10都是真币因为真币真币 真币真币。假币在11和12中。第三次称量用一枚真币如1号与11号称量。若平衡则12是假币再通过一次与真币的称量或根据之前信息可判断轻重实际上此时我们不知道轻重需要额外信息这里有个关键点当假币锁定在2枚且不知轻重时第三次称量必须能同时判断出是哪一枚以及轻重。所以更优的第三次称量是拿11和12互称不对这样只能知道谁轻谁重但不知道标准重量。正确做法是用一枚真币与11号称。如果平衡则12是假币但轻重未知这里出现了逻辑漏洞我们需要回溯并修正方案。让我们重新严谨推理 实际上在B分支下假币在{9,10,11,12}中但我们不知道假币是轻是重。第二次称量9真 vs 10真如果平衡只能证明9和10重量相等它们要么都是真要么都是假且同轻或同重。但根据第一次平衡假币只有一枚所以9和10不可能都是假因此它们都是真币。假币在11和12中且我们仍不知其轻重。第三次称量取11号与一枚已知真币如1号称量。如果平衡则11是真币12是假币。但是我们无法知道12是轻是重问题出现了吗不我们还有一次称量机会吗没有了。这似乎是个死胡同。 这说明我的第二次称量设计有缺陷。经典的、能确保成功的第二次称量方案是左盘9, 10, 11右盘三枚真币例如1, 2, 3 这样如果左盘重则假币在9,10,11中且为重币如果左盘轻则假币在9,10,11中且为轻币如果平衡则假币是12但12的轻重依然未知不此时我们还有一次称量机会可以称量12与真币直接得知轻重。完美。 让我们按经典方案重述第二次称量经典方案左盘9, 10, 11右盘三枚真币1, 2, 3可能结果左重假币在9,10,11中且为重币。第三次称量比较9和10。谁重谁就是假重币平衡则11是假重币。左轻假币在9,10,11中且为轻币。第三次称量比较9和10。谁轻谁就是假轻币平衡则11是假轻币。平衡假币是12。第三次称量用12与任何一枚真币比较即可知12是轻是重。3.2.2 分支二第一次左倾L或右倾R这两个分支是对称的我们以第一次左倾L为例进行详解。此时嫌疑范围是{1,2,3,4}可能为重币或者{5,6,7,8}可能为轻币。而{9,10,11,12}是真币。第二次称量的设计需要能有效区分这8种可能性4枚可能重 4枚可能轻。一个巧妙的方案是进行“混编”左盘1, 2, 5 即一枚可能重的“嫌疑犯”1一枚可能重的“嫌疑犯”2和一枚可能轻的“嫌疑犯”5右盘3, 6, 9 即一枚可能重的“嫌疑犯”3一枚可能轻的“嫌疑犯”6和一枚已知的真币9未称4, 7, 8 即可能重的4可能轻的7和8分析第二次称量的结果平衡B说明左盘的{1,2,5}和右盘的{3,6,9}重量相等。由于9是真币那么1,2,5与3,6的重量组合必须与真币组合等价。这意味着什么嫌疑犯{1,2,3}如果重或者{5,6}如果轻都会破坏平衡。既然平衡了就说明{1,2,3,5,6}这五枚硬币的行为都符合真币特征。因此假币在未称量的{4,7,8}中。结合第一次左倾的线索左边重如果假币是4它必须是重币如果假币是7或8它必须是轻币。第三次称量比较7和8。如果7轻则7是假轻币。如果8轻则8是假轻币。如果平衡则4是假重币。左盘重L左盘重了。看看谁可能导致这个结果左盘中的1或2如果是重币会导致左重右盘中的6如果是轻币会导致右盘变轻从而显得左盘重。但右盘中的3如果是重币反而会导致右盘重这与左重矛盾。左盘中的5如果是轻币会导致左盘变轻这也与左重矛盾。因此可能的嫌疑犯缩小为{1重2重6轻}。第三次称量比较1和2。如果左边重则1是假重币。如果右边重则2是假重币。如果平衡则6是假轻币。右盘重R推理逻辑类似。可能导致右重的原因有右盘中的3是重币或者左盘中的5是轻币导致左盘轻显得右重。同时1或2是重币会导致左重与结果矛盾6是轻币会导致右盘轻也与结果矛盾。因此嫌疑犯缩小为{3重5轻}。第三次称量这已经很简单了。用3与一枚真币比较即可。但为了统一可以称量3和5不5是可能轻的。更直接取3与真币称。如果3重则3是假重币如果平衡则5是假轻币因为嫌疑只有这两个。通过这样精细的设计第二次称量无论出现什么结果都能将嫌疑范围缩小到2-3枚硬币并且明确了假币是“可能重”还是“可能轻”的子集从而让第三次称量可以一锤定音。3.3 第三次称量一锤定音与结论输出第三次称量的设计通常比较简单因为经过前两次的筛选我们面对的情况已经非常明确要么是2-3枚已知轻重属性的嫌疑币通过一次比较即可找出异常者要么是1枚孤立的硬币只需与真币比较一次即可知其轻重。关键在于第三次称量的方案必须根据第二次的结果动态决定。它没有固定的公式而是决策树上的最后一个分支。例如在“第一次平衡第二次左重”的情况下我们面对的是{9,10,11}三枚硬币且已知假币在其中且为重币。第三次称量只需比较其中两枚如9和10就能通过谁重或是否平衡来判断出假币。4. 思维延伸从谜题到工程实践解决了这个具体的12硬币问题固然有趣但它的真正价值在于其背后普适的思维模型。这些模型可以直接迁移到软件开发和系统设计中。4.1 分治与递归思想将12枚硬币分成3组每次称量排除掉至少一部分“真币”或确定一部分嫌疑犯的属性这正是分治算法的体现。在面对海量数据或复杂系统时我们首先思考的就是如何将其划分为更小、更易处理的子问题。例如在排查一个分布式系统的性能瓶颈时你不会同时检查所有服务。你会先通过监控指标第一次“称量”判断问题是出在接入层、业务逻辑层还是数据层。锁定某一层后再进一步检查该层内的具体服务或模块第二次“称量”直至定位到有问题的代码行或配置第三次“称量”。4.2 信息论与日志设计三次称量对应27种结果路径覆盖24种情况这体现了信息编码的效率。在我们的系统中日志和监控事件就是我们的“称量结果”。设计良好的日志等级DEBUG, INFO, WARN, ERROR和结构化字段就是为了用最少的数据量日志行数/体积携带最多的问题定位信息。冗余的、无结构的日志就像低效的称量方案查问题时需要翻看大量无关信息而精准的、结构化的日志能让你像这个谜题的解法一样通过有限的几次查询“称量”迅速收敛到问题根因。4.3 决策树与自动化运维整个称重过程构成了一棵完美的决策树。这棵树可以预先定义预定义策略也可以根据中间结果动态生成分支自适应策略。这正是自动化故障诊断和根因分析RCA系统的核心思想。我们可以将常见的故障场景、监控指标阈值、关联关系预先编写成决策规则当告警触发时系统自动沿着决策树执行检查命令、调用诊断API最终输出最可能的故障原因和修复建议极大提升了运维效率。4.4 状态空间与测试用例设计24种可能的“假币状态”可以类比为我们程序可能存在的缺陷状态。27种称量结果路径可以类比为我们设计的测试用例集合。一个好的测试套件其测试用例应该能像称量方案一样覆盖所有重要的、可能导致程序行为异常的状态组合并且尽可能高效用例数少但覆盖率高。思考如何用最少的测试用例发现最多类型的bug其本质和“用最少的称量次数区分所有假币可能性”是相通的。5. 常见误区与实战心得在向别人解释或自己思考这个问题时有几个坑很容易掉进去。这里分享我总结的几个关键点和心得。5.1 误区一忽视“轻重未知”的约束最经典的错误是假设自己知道假币是轻还是重。如果知道轻重问题会简化为二分查找3次称量足以从12枚中找出假币因为2^38 12? 等等2^38不足以区分12枚需要更多次。但若知道轻重可以用天平比较3次确实足够但策略不同。而“轻重未知”使得每个嫌疑对象都有两种可能状态空间翻倍大大增加了难度。任何解决方案如果没能在过程中同时推断出轻重都是不完整的。5.2 误区二第二次称量方案设计僵化很多人卡在第二次称量上因为他们试图用一个“对称”或“简单”的分组比如仍然像第一次一样拿4枚和4枚称。这在某些分支下尤其是第一次不平衡时是行不通的因为此时你拥有的信息是不对称的一部分硬币嫌疑重一部分嫌疑轻。必须利用好第一次称量后获得的“已知真币”和“嫌疑属性”信息设计一个“混编”的称量方案就像我们之前做的将可能重和可能轻的硬币与真币混合这样才能最大化信息获取。5.3 误区三认为存在唯一“标准答案”这个问题的解法不是唯一的。分组方式、第二次称量的具体排列都可以有变化只要逻辑自洽能构建出覆盖24种状态的决策树即可。在面试中展示你构建解决方案的过程——如何分析约束、如何设计实验、如何根据反馈调整——比单纯背诵一个答案重要得多。面试官更想看到的是你系统化的解决问题能力。5.4 实战心得从特例到通用的推导方法当你第一次遇到这类问题时不要试图直接想出12个硬币的解法。可以从更简单的情况开始推导建立直觉3枚硬币1次称量已知假币较轻很简单任意两枚一称即可。3枚硬币1次称量假币轻重未知不可能。因为一次称量只有3种结果但需要区分6种状态3枚×2种轻重。4枚硬币2次称量假币轻重未知可以解决吗状态空间是82次称量最多提供9种信息理论可行。试着设计一下能加深对“混编”策略的理解。通过解决这些小规模问题你能更好地理解信息量与状态空间的关系以及如何利用“已知标准件”真币进行比对。这种从简单到复杂、从特殊到一般的推导方法是解决任何复杂逻辑或算法问题的利器。6. 问题变种与扩展思考掌握了基础解法后我们可以思考一些变种问题这能进一步锻炼思维。6.1 变种一13枚硬币问题如果给你13枚硬币三次称量还能解决吗我们来计算一下状态空间 13枚 × 2种轻重 26种。三次称量的信息上限是27种。27 26理论上是可行的。但实际操作中你会发现因为27比26只多1方案必须设计得极其高效几乎不能有任何信息浪费。经典的12硬币方案有3条冗余路径27-243而13硬币方案只有1条冗余设计难度更大但仍然是存在的。这提醒我们理论上的可能性不等于构造的简易性。6.2 变种二知道假币较轻或较重如果提前知道假币是较轻的那么问题就变成了单纯的“找出异常项”。状态空间从24缩减为12。三次称量27种信息绰绰有余。实际上你可以用类似二分查找的策略第一次6 vs 6找到较轻的一组第二次3 vs 3找到较轻的一组第三次从3个中任取2个称平衡则剩下的是假币否则轻的是假币。这是一个更简单的信息检索问题。6.3 变种三天平有砝码或使用电子秤如果天平有砝码或者直接使用能读数的电子秤问题性质就完全变了。电子秤一次称量可以得到一个具体的重量数值通过一次称量所有硬币的总重量再与标准总重量比较就能直接计算出哪枚硬币是假的以及它的偏差。这从“信息论游戏”变成了“数学计算问题”。这告诉我们工具的能力决定了解决问题的范式。在工程中引入更强大的监控工具如分布式链路追踪、深度性能剖析工具往往能将复杂的排查问题降维打击。6.4 扩展到N枚硬币与K次称量这是一个更一般的数学问题给定N枚硬币1枚假币轻重未知用一架天平至少需要称量多少次K才能保证找出假币并知其轻重答案与信息论紧密相关我们需要找到最小的K使得 3^K 2N。因为每次称量有3种结果K次就有3^K种可能序列需要覆盖2N种状态N个位置×2种轻重。例如对于12枚硬币3^327 24所以K3。对于13枚3^327 26K也是3。对于更大的N我们可以用这个公式估算所需的最少称量次数。回过头看这个经典的面试题绝不仅仅是一个逻辑游戏。它是一个微缩的、关于如何在有限资源三次称量和不确定条件轻重未知下通过精心设计的实验称量方案来获取最大信息量从而唯一确定一个隐藏状态哪枚硬币、轻或重的完美案例。它所训练的分治、信息编码、决策树构建和递归思维是每一位优秀的工程师、数据分析师乃至产品经理都应具备的核心能力。下次当你面对一个复杂的、信息不全的难题时不妨回想一下这12枚硬币先定义清楚状态空间评估你获取信息的手段和能力然后设计一系列能够最大程度消除不确定性的实验或步骤。这就是理性解决问题的通用法门。