智力题:有12个外观相同的芯片、其中一个重量不同(不知轻重),用天平最少称几次能找出这张芯片
1️⃣ 考察意图
面试官并非单纯考你“会不会解12球问题”，而是考察信息论直觉与分治策略的工程化应用。这道题是典型的“带噪声的二分查找”变体——你不仅要找出异常芯片，还要在不知轻重的情况下同时确定“偏重还是偏轻”。刁钻点在于：每次称量有3种结果（左倾/右倾/平衡），12个芯片有24种可能状态（12个芯片 × 轻重2种），\log_3(24)\approx 2.89，理论上界是3次。答好了能展示你从信息论下界反推策略的能力，以及将抽象逻辑转化为可执行决策树的工程思维——这正是AI Agent中多步推理（如ReAct循环）的核心。
2️⃣ 标准答
核心结论：最少3次。 下面给出可复现的称量策略，并解释为什么2次不可能。
策略树（分治 + 信息论驱动）
- 第一次称量：分三组，每组4个
- 将芯片编号1-12，分成A组(1-4)、B组(5-8)、C组(9-12)。
- 称A vs B。
- 三种结果：
- 平衡：异常在C组，且已知A/B均为正常（标准品）。
- 左倾：异常在A或B，且若在A则偏重，若在B则偏轻。
- 右倾：对称推理。
- 第二次称量：缩小范围至2-3个
- Case 1（第一次平衡）：C组4个（9-12）可疑。取9、10、11 vs 三个正常芯片（如1、2、3）。
- 平衡 → 异常是12，第三次称12 vs 正常即可知轻重。
- 左倾 → 异常在9/10/11中且偏重，第三次称9 vs 10即可。
- 右倾 → 异常在9/10/11中且偏轻，同理。
- Case 2（第一次左倾）：A组可能偏重，B组可能偏轻。取A中1、2、3 + B中5 vs A中4 + B中6、7 + 一个正常（如9）。
- 平衡 → 异常在B的8或A的4？不，实际是A中4或B中8？这里需精确：剩余未称的是A中4和B中8，第三次称4 vs 正常即可。
- 左倾 → 异常在1/2/3中且偏重，第三次称1 vs 2。
- 右倾 → 异常在5/6/7中且偏轻，第三次称5 vs 6。
- Case 3（第一次右倾）：对称处理。
- 第三次称量：二选一或三选一
- 无论哪种分支，第三次都能从最多3个可疑芯片中唯一确定异常及其轻重。
为什么2次不可能？
- 信息论下界：24种可能状态，每次称量3种结果，2次最多区分3²=9种状态 < 24。
- 工程取舍：这里不能“贪心”地每次只缩小一半（二分法），因为天平返回的是三元信息，必须利用“标准品”来消除轻重歧义。实际落地中，类似策略用于分布式系统故障检测——用少量对比节点定位异常节点，代价是决策树复杂度O(\log_3 N)。
实际落地的坑 + 解法
- 坑：面试时容易陷入“手动模拟所有分支”的泥潭，忘记用信息论证明下界。解法：先给出\log_3(24)\approx 2.89，断言3次是理论最优，再画决策树。这展示了你从第一性原理推导的习惯。
- 坑：Case 2的第二次称量设计容易出错（比如忘记留标准品）。解法：记住“三组互斥”原则——第一次称量后，可疑芯片被分为“可能偏重组”和“可能偏轻组”，第二次称量必须混搭这两组并引入标准品，才能最大化信息熵。
3️⃣ 答题模板（30 秒电梯版）
“这个问题我从信息论下界、分治策略、工程取舍三个层面回答。信息论层面：12个芯片有24种状态，每次称量3种结果，2次最多区分9种，所以最少3次。分治策略层面：第一次分三组每组4个，第二次利用标准品将可疑范围缩至2-3个，第三次直接比较。工程取舍层面：不能简单二分，必须利用天平的三元输出设计互斥分支。总结一句：最少3次，且策略树可推广到N个芯片的通用解法。”
4️⃣ 高频追问 & 应对
追问 1：如果芯片数量变成13个，最少几次？
13个芯片有26种状态，\log_3(26)\approx 2.97，理论下界仍是3次。但实际策略需调整：第一次称8 vs 8（各留1个未称），平衡则异常在剩余5个中，3次可解；不平衡则需更复杂的分组。关键在于：13个时3次仍可行，但14个时状态数28，\log_3(28)\approx 3.03，必须4次。这展示了信息论下界的严格性——不是整数时向上取整。
追问 2：如果天平只能告诉你“是否平衡”（即二元输出），最少几次？
此时每次称量只有2种结果，\log_2(24)\approx 4.58，最少5次。策略退化为二分法：第一次6 vs 6，第二次3 vs 3，第三次1 vs 1（但需考虑轻重歧义）。实际中，二元天平对应布尔测试，常用于软件测试中的二分定位bug——每次只能判断“是否在区间内”，效率更低。
追问 3：如何用代码实现这个策略树？
可以用递归+状态压缩：每个状态用(可疑芯片列表, 轻重标记)表示，每次称量枚举所有可能的分组，用BFS搜索最少步数。核心是剪枝——利用信息论下界提前终止不可能的分支。实际工程中，这类算法用于自动化测试用例生成，比如用决策树最小化测试次数。复杂度O(3^N)，但N≤20时可接受。
5️⃣ 避坑 · 常见错误答法
- ❌ 直接说“3次”，然后开始手动模拟所有分支，但没解释为什么2次不行。→ ✅ 先给出信息论下界证明2次不可能，再画策略树。这展示了你从理论到实践的推导能力，而非死记硬背。
- ❌ 第一次称量用6 vs 6（二分法），然后发现第二次无法处理轻重歧义。→ ✅ 第一次必须用4 vs 4，留4个作为标准品。二分法在“不知轻重”时无效，因为天平倾斜无法区分“左重”还是“右轻”。这体现了对问题约束的敏感度。
- ❌ 回答中混淆“找出芯片”和“知道轻重”，认为只需找出即可。→ ✅ 明确问题要求“找出”，但策略天然会同时确定轻重。如果只找不辨轻重，状态数减半为12，\log_3(12)\approx 2.26，2次理论可行但实际仍需3次（因为天平结果无法直接映射）。这展示了严谨性。
6️⃣ 简历呼应
- 如果你有AI Agent项目：从“多步推理的决策树”角度切入，类比Agent的ReAct循环——每次称量相当于一次action，结果反馈更新belief state，最终收敛到目标。强调信息论在Agent规划中的应用（如主动学习采样策略）。
- 如果你只做过传统后端开发：用“分布式故障定位”类比——12个节点中一个异常，用对比测试（类似天平）定位。可扩展讨论如何用二分法减少日志分析次数，或设计健康检查策略。
- 如果你是校招无项目：聚焦信息论下界的推导过程，展示数学功底。可提及用Python写一个模拟程序（递归搜索策略树），并开源到GitHub作为demo。强调“从问题到代码”的完整流程能力。
- 《The Art of Computer Programming》Vol.3 – 查找与排序中的信息论下界
- 《Information Theory, Inference, and Learning Algorithms》by David MacKay – 第4章“The 12-coin problem”
- 论文：”Optimal Strategies for the 12-Coin Problem” – 通用解法证明
- 工具：Python
itertools+ 递归搜索实现策略树（可参考LeetCode 讨论区“12 balls problem”） - 博客：”Why 3 Weighings? Information Theory and the 12-Ball Problem” – 直观解释信息论下界