--- description: "三次称重 27 种读数装下 24 个假设；Dyson 三进制编码给出写死的称法，$n$ 次的上限是 $(3^n-3)/2$，恰好 12" --- # 12 个球找假球 ## 题 12 个外观相同的球，恰有一个是假球，重量和其他球不同——但不知道偏轻还是偏重。一架没有砝码的天平，最多称 3 次，找出假球并说出它偏轻还是偏重。 ## 一句话 能做到，而且**三次称法可以事先写死**、不看前面的结果：给每个球发一个三位三进制码字，三次读数拼成的三位数直接报出是哪个球、偏重还是偏轻。 ## 关键技巧 **天平是三进制仪器。** 每次读数只有左沉、平、右沉三种，3 次共 $3^3 = 27$ 种读数。要分开的假设是"哪个球 × 偏轻或偏重" $= 12 \times 2 = 24$ 个。$24 \le 27$，信息量够，但只余 3——每次称重都得把剩余假设尽量三等分，这就是为什么 6 对 6 开局必败。 **Dyson 的编码观点（1946）。** 读数记 0 = 左沉、1 = 平、2 = 右沉。给球 $k$ 一个码字 $c_k \in \{0,1,2\}^3$：第 $i$ 位是 0 就在第 $i$ 次放左盘，是 2 就放右盘，是 1 就不上秤。 - 假球偏重：它在左盘时左沉、右盘时右沉、不上秤时平——**读数恰好等于它的码字 $c_k$**； - 假球偏轻：左右全反，**读数是补码字 $2 - c_k$**。 所以只要 12 个码字和它们的 12 个补码字共 24 个两两不同，读数就能唯一反解。27 个三位数里，$111$ 是自己的补（假球从没上秤，轻重无从判断），$000$ 和 $222$ 这一对也剔掉、好让每次称重两边个数相等，去掉这 3 个，剩下 24 个正好配成 12 对。每对挑哪一个？Dyson 的规则：**挑数字"首次变化"是 $0 \to 1$、$1 \to 2$ 或 $2 \to 0$ 的那个**（循环向前一格）。这条规则让每一位上 0、1、2 各出现 4 次——每次称重恰好 4 对 4，不需要标准球。 ## 解 按 Dyson 规则挑出的 12 个码字，依字典序发给球 1–12： | 球 | 码字 | 三次位置 | 偏重时读数 | 偏轻时读数 | | --- | --- | --- | --- | --- | | 1 | 001 | 左 左 — | 左沉 左沉 平 | 右沉 右沉 平 | | 2 | 010 | 左 — 左 | 左沉 平 左沉 | 右沉 平 右沉 | | 3 | 011 | 左 — — | 左沉 平 平 | 右沉 平 平 | | 4 | 012 | 左 — 右 | 左沉 平 右沉 | 右沉 平 左沉 | | 5 | 112 | — — 右 | 平 平 右沉 | 平 平 左沉 | | 6 | 120 | — 右 左 | 平 右沉 左沉 | 平 左沉 右沉 | | 7 | 121 | — 右 — | 平 右沉 平 | 平 左沉 平 | | 8 | 122 | — 右 右 | 平 右沉 右沉 | 平 左沉 左沉 | | 9 | 200 | 右 左 左 | 右沉 左沉 左沉 | 左沉 右沉 右沉 | | 10 | 201 | 右 左 — | 右沉 左沉 平 | 左沉 右沉 平 | | 11 | 202 | 右 左 右 | 右沉 左沉 右沉 | 左沉 右沉 左沉 | | 12 | 220 | 右 右 左 | 右沉 右沉 左沉 | 左沉 左沉 右沉 | 读成三次称法： 1. **第 1 次**：$\{1, 2, 3, 4\}$ 对 $\{9, 10, 11, 12\}$ 2. **第 2 次**：$\{1, 9, 10, 11\}$ 对 $\{6, 7, 8, 12\}$ 3. **第 3 次**：$\{2, 6, 9, 12\}$ 对 $\{4, 5, 8, 11\}$ 称完把读数按"左沉 0、平 1、右沉 2"拼成三位数，在码字列里查到就是那个球偏重；查不到，就把每位换成 $2 - x$ 再查，查到的球偏轻。例：读数"左沉 右沉 平" $= 021$，码字里没有；补码 $201$ 是球 10——**球 10 偏轻**。24 种合法读数各对应一个答案，$000$、$111$、$222$ 永远不会出现。 ### 上限为什么恰好是 12 $n$ 次称重、没有标准球时，最多能处理 $\frac{3^n - 3}{2}$ 个球： - **先看有标准球的子问题**：$m$ 个可疑球、手边有标准球、称 $n'$ 次。$2m$ 个假设要装进 $3^{n'}$ 种读数，"全平"读数判不出轻重得去掉，$2m \le 3^{n'} - 1$，即 $m \le \frac{3^{n'} - 1}{2}$。 - **第一次称重没有标准球**，两边只能各放 $k$ 个可疑球。若失衡，剩 $2k$ 个假设（左边 $k$ 个可能偏重、右边 $k$ 个可能偏轻）装进 $3^{n-1}$ 种读数，$2k \le 3^{n-1}$，$k$ 是整数所以 $k \le \frac{3^{n-1} - 1}{2}$。若平衡，秤上的 $2k$ 个全成了标准球，剩下的球落进上一条的子问题，至多 $\frac{3^{n-1} - 1}{2}$ 个。 - **合计** $2k + \frac{3^{n-1}-1}{2} \le 3 \cdot \frac{3^{n-1}-1}{2} = \frac{3^n - 3}{2}$。$n = 3$ 时恰好 **12**。 ## 延伸 - **13 个球**：3 次能找出假球，但不能保证说出轻重。上限推导里第一次至多 4 对 4，平衡后剩 5 个可疑球，比有标准球的两次称重能判的 4 个多一个——这第 5 个球可以始终不上秤、靠排除法认出来，轻重却无从知道。 - **多给一个标准球**：第一次称重就能两边不等量、用标准球补齐，上限变成 $\frac{3^n - 1}{2}$，13 个球可以找出并判轻重。 - **$n$ 次的上限序列**：没有标准球 3、12、39（$n = 2, 3, 4$）；有标准球 4、13、40。折叠块里的穷举搜索逐一核对过。 - **常见错误：6 对 6 开局**。一旦失衡，剩下 6 个可能偏重 + 6 个可能偏轻 = 12 个假设，两次称重只有 9 种读数，装不下。3 对 3 开局也不行——平衡时剩 6 个可疑球，有标准球的两次称重最多处理 $\frac{9-1}{2} = 4$ 个。**第一次必须 4 对 4。** - **已知假球偏重**：假设数就是球数，$n$ 次可以从 $3^n$ 个球里找出来——每次三等分，和 [1000 瓶酒找毒酒](poison-wine.md) 的"每次观测贡献一位"是同一回事，只是这里是三进制。 ??? note "数值验证" Dyson 码字逐一核对 24 种情况，再用穷举搜索确认上限（状态只记"轻重都可能 / 只可能偏重 / 只可能偏轻"三类球的个数和手边有没有标准球）： ```python from itertools import product from functools import lru_cache def clockwise(v): for a, b in zip(v, v[1:]): if a != b: return (b - a) % 3 == 1 # 首次变化是 0→1、1→2 或 2→0 return None # 000/111/222 剔除 codes = [v for v in product(range(3), repeat=3) if clockwise(v)] print(len(codes), codes) # 12 [(0, 0, 1), (0, 1, 0), (0, 1, 1), (0, 1, 2), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2), (2, 0, 0), (2, 0, 1), (2, 0, 2), (2, 2, 0)] for i in range(3): left = [k + 1 for k, c in enumerate(codes) if c[i] == 0] right = [k + 1 for k, c in enumerate(codes) if c[i] == 2] print(f"第 {i+1} 次: {left} vs {right}") # 第 1 次: [1, 2, 3, 4] vs [9, 10, 11, 12] # 第 2 次: [1, 9, 10, 11] vs [6, 7, 8, 12] # 第 3 次: [2, 6, 9, 12] vs [4, 5, 8, 11] def weigh(fake, heavy): out = [] for i in range(3): d = codes[fake][i] side = 0 if d == 0 else (2 if d == 2 else None) if side is None: out.append(1) # 假球不在秤上：平 elif (side == 0) == heavy: out.append(0) # 左沉 else: out.append(2) # 右沉 return tuple(out) def decode(r): for k, c in enumerate(codes): if c == r: return k, "重" if tuple(2 - x for x in c) == r: return k, "轻" all_ok = all(decode(weigh(k, h)) == (k, "重" if h else "轻") for k in range(12) for h in (True, False)) print(all_ok) # True @lru_cache(None) def ok(u, h, l, g, n, need_dir=True): """u 颗轻重都可能、h 颗只可能偏重、l 颗只可能偏轻；g=手里有无标准球；还剩 n 次。""" if need_dir and 2 * u + h + l <= 1: return True if not need_dir and u + h + l <= 1: return True if n == 0: return False for u1, u2, h1, h2, l1, l2 in product(range(u + 1), range(u + 1), range(h + 1), range(h + 1), range(l + 1), range(l + 1)): if u1 + u2 > u or h1 + h2 > h or l1 + l2 > l: continue L, R = u1 + h1 + l1, u2 + h2 + l2 if L == R == 0 or (L != R and not g): continue # 两边个数不等时用标准球补 rest = (u - u1 - u2, h - h1 - h2, l - l1 - l2) tip = [(0, u1 + h1, u2 + l2), (0, u2 + h2, u1 + l1)] # 左沉 / 右沉 cases = tip + [rest] total = u + h + l if all(ok(*c, g or (sum(c) < total), n - 1, need_dir) for c in cases): return True return False print(ok(12, 0, 0, False, 3), ok(13, 0, 0, False, 3)) # True False print(ok(13, 0, 0, False, 3, need_dir=False)) # True 13 球只找球、不判轻重 print(ok(13, 0, 0, True, 3), ok(14, 0, 0, True, 3)) # True False 带一个标准球 for n in (2, 3): print(n, max(N for N in range(1, 20) if ok(N, 0, 0, False, n)), (3**n - 3) // 2) # 2 3 3 # 3 12 12 print(ok(39, 0, 0, False, 4), ok(40, 0, 0, False, 4)) # True False 跑约 10 秒 ``` 有标准球时 $n = 2, 4$ 的上限 4、40 用同一个 `ok(N, 0, 0, True, n)` 查过。