问题描述

已知正整数 $n \geq 3$，有 $2^n-1$ 个球，其中一个坏球，其余都是好球。好球重量都相等，坏球重量和好球不同。有一台电子秤，每次可以称量任意多的球，精确显示平均重量。

证明： 可以用 $n$ 次称量，找出坏球，并且知道坏球比好球轻还是重。

证明思路

将 $2^n-1$ 个球编号为 $1, 2, \ldots, 2^n-1$，用 $n$ 位二进制表示（从 $000\ldots1$ 到 $111\ldots1$）。

称量策略

第 $j$ 次称量 ($j=1,\ldots,n$)：称量所有编号二进制第 $j$ 位为 1 的球。

为什么可行？

设好球重量为 $w$，坏球重量为 $w+\delta$（$\delta \neq 0$）。

两种情况

  • 若某次称量的集合中不含坏球 → 平均重量 = $w$
  • 若包含坏球且有 $k$ 个球 → 平均重量 = $\frac{(k-1)w + (w+\delta)}{k} = w + \frac{\delta}{k}$

判断逻辑

  1. 定位坏球：从哪些称量的读数 ≠ $w$，即可重建坏球的二进制编号
  2. 判断轻重：若所有异常读数都 > $w$，则坏球偏重；若都 < $w$，则坏球偏轻（因为 $\delta/k$ 的符号始终相同）

唯一性保证

每个球有唯一的二进制编码，故其对应的”异常称量模式”也是唯一的。第 $j$ 个球是坏球当且仅当所有二进制第 $j$ 位为 1 的称量读数偏离 $w$。

结论

✅ $n$ 次称量足以找出坏球并判断其轻重

这个问题巧妙地将组合优化转化为二进制编码，体现了数学之美。