天平称重与决策树

九枚硬币外观相同，恰有一枚比其余硬币重，其余八枚质量完全相等。只用理想等臂天平，没有砝码。最少称几次能保证找到偏重币？演示可选真实偏重币，逐次显示相应结果。

前置：整数幂、分类计数、充分与必要条件。目标：画出决策树（Decision tree），证明次数下界，并写出每一条分支的可执行方案。本页为项目S班编排，不代表当地官方课程要求。

一个候选状态，是一种仍与全部已知结果相容的可能。本题已知偏重，所以状态只需记录“哪一枚偏重”。每次观察只有左盘低、平衡、右盘低三种结果。决策树的节点表示称法，边表示结果，叶子表示最终判断。

要保证辨认，每两个不同身份必须在某一步产生不同结果，否则沿同一路径无法区分。最多称 k 次的三分支树至多有 3ᵏ 个叶子，所以 N 枚至少要满足 N ≤ 3ᵏ。即使方案根据先前结果改变称法，上界仍成立：第一层至多3支，每支剩余k−1次，递推相乘。

下界不能代替构造。在已知一枚偏重、其余等重的条件下，可以达到这个界。若剩余n个候选且n≤3ᵏ，令 C=3ᵏ⁻¹，取 a=min(C,⌊n/2⌋)，两盘各放a枚，余下n−2a枚暂不称。若不平衡，偏重币在较低盘；若平衡，在未上秤组。三组均不超过C：当a=C，余组≤C；当a=⌊n/2⌋，余组至多1。每支递归，直到只剩1枚，无须再称。

N≥1且恰有一枚偏重时，最少保证次数是使 N≤3ᵏ 的最小非负整数k。N=1时不称就知道。这里每次两盘枚数相同；不能用枚数不同却只看方向的称法套三等分。

未知轻重不能沿用候选枚数。三枚中恰一枚异常但轻重未知，称1对2后若左低，可能是1偏重，也可能是2偏轻；不能断言异常在较低盘。此时候选需要保留“身份＋方向”。

信息数足够也可能没有方案。只有两枚硬币，恰一枚异常，偏轻偏重未知，无已知正常币，也无砝码；即使允许两次，3²=9≥4种身份方向状态，仍无法保证找出异常币。若1对2时左低，“1偏重”和“2偏轻”结果相同；交换两盘也仍相同。空称或两币一起放同盘只显示相同方向；没有外部标准无法分辨。若题目另给质量差或标准币，需重新分析。

• 保证次数看最坏分支，不能用一次碰巧称出的情形替代。
• 没有异常币、多个异常币、天平误差或正常币不等重时，本页方案不再有保证。
• 天平倾角只表示哪边重，不由角度读出质量差。
• 每次放币的方案必须合法，并覆盖所有可能结果；不可能分支要说明为何不可能。

先列候选状态 → 用3ᵏ给次数下界 → 等枚数分组 → 逐支构造 → 核对每个身份有唯一终点。

文字稿默认展开。点击章节标题可定位视频相应位置。

例题、练习为自拟。依据是正文三分支树证明与全身份枚举，动画只帮助观察。采用理想等臂天平，不按质量差绘制倾角。演示允许指定偏重币以核对分支，解题者实际并不知道它的位置。视频的动画、旁白与字幕使用同一时间轴。