称重问题

参考资料：「小球称重问题」完整版解答汇总

下界

假设对这 $n$ 枚硬币，需要称量 $k$ 次。

受作业（选做部分）启发，令 $H_i$ 表示第 $i$ 次称量后可能比真币重或是真币的硬币构成的集合，$L_i$ 表示第 $i$ 次称量后可能比真币轻或是真币的硬币构成的集合，$S_i$ 为 $|H_i|+|L_i|$ 的最大允许值。

为了最终找出假币，要求 $|H_k|+|L_k|=S_k=1$。

假设 $|H_{i+1}|+|L_{i+1}| \le S_{i+1}$，由于第 $i$ 次称量只有左侧重、右侧重和一样重三种情况，则 $|H_i|+|L_i| \le S_i=3 \cdot S_{i+1}$。因此，$S_1=3^{k-1}$。

特别地，对于第 $1$ 次称量，称量前有 $|H_0|=|L_0|=n$。我们将所有硬币不重不漏地分为 $A$、$B$ 和 $C$（$|A|=|B|$），并称量 $A$ 和 $B$：

  1. 如果 $A$ 更重，那么 $H_1=A$，$L_1=B$，$|A|+|B| \le S_1$；
  2. 如果 $B$ 更重，那么 $H_1=B$，$L_1=A$，$|A|+|B| \le S_1$；
  3. 如果一样重，那么 $H_1=C$，$L_1=C$，$|C|+|C| \le S_1$。

因此：

$$|A|=|B|=|C| \le \left\lfloor \dfrac{S_1}{2} \right\rfloor=\dfrac{3^{k-1}-1}{2}$$

$$n=|A|+|B|+|C| \le \dfrac{3^k-3}{2}$$

即：若只称量 $k$ 次，最多处理 $n=\dfrac{3^k-3}{2}$ 枚硬币。要处理 $n$ 枚硬币，最少要称量 $k=\lfloor \log_3(2n+3) \rfloor$ 次。

算法设计

根据下界的估计，若有一种三进制编码方法，使得 $k$ 位三进制编码可以表示 $n$ 枚硬币。$2$ 暗示一枚硬币有两个编号（比真币轻/重），$3$ 暗示有 $3$ 个编码是不使用的。

为了简单起见，我们先讨论 $n=\dfrac{3^k-3}{2}$ 的情况。

编码方法设计如下：每一枚硬币都有“正序编码”与“逆序编码”。

定义“轮换”：将编码原本的 $0$ 改为 $1$，$1$ 改为 $2$，$2$ 改为 $0$。

将硬币每三枚作为一组。

  1. 对于第 $1$ 组硬币：
    1. 对于第 $1$ 枚硬币，正序编码为 $\underbrace{0 \cdots 0}_{n-1\text{ 个}}1$；
    2. 对于第 $2$ 枚硬币，轮换一次，得到正序编码 $\underbrace{1 \cdots 1}_{n-1\text{ 个}}2$；
    3. 对于第 $3$ 枚硬币，轮换一次，得到正序编码 $\underbrace{2 \cdots 2}_{n-1\text{ 个}}0$；
  2. 对于第 $2$ 组硬币：
    1. 对于第 $4$ 枚硬币，将第 $1$ 枚硬币的三进制正序编码不断 $+1$，直到最高位为 $1$，得到 $\underbrace{0 \cdots 0}_{n-2\text{ 个}}10$。

以此类推，可以得到所有硬币的正序编码。

由此可以得到 $n$ 枚硬币的正序编码。再将正序编码中的 $0$ 改为 $2$，$2$ 改为 $0$，即可得到硬币的逆序编码。

正序编码的从左到右第一对相邻不同的数字只能是 $01$、$12$ 和 $20$，而逆序编码的从左到右第一对相邻不同的数字只能是 $02$、$10$ 和 $21$。

不存在编码 $\underbrace{0 \cdots 0}_{n\text{ 个}}$、$\underbrace{1 \cdots 1}_{n\text{ 个}}$ 和 $\underbrace{2 \cdots 2}_{n\text{ 个}}$。

接下来，进行称量。第 $i$ 次称量，将正序编码第 $i$ 位为 $0$ 的硬币放在左侧，正序编码第 $i$ 位为 $2$ 的硬币放在右侧。如果左侧重，结果记为 $0$；如果右侧重，结果记为 $2$；如果一样重，结果记为 $1$。最后将总共 $k$ 次称量的结果从低位到高位拼成一个 $k$ 位三进制数 $r$。

首先，$r$ 不可能由单一的数字组成，即 $r \notin \{\underbrace{0 \cdots 0}_{n\text{ 个}},\underbrace{1 \cdots 1}_{n\text{ 个}},\underbrace{2 \cdots 2}_{n\text{ 个}}\}$。

  1. 由于存在恰好一个假币，不可能每次称量都是一样重，即 $r \ne \underbrace{0 \cdots 0}_{n\text{ 个}}$。
  2. 由于对于假币，它的编号一定至少由两种数字组成，不可能一直在左侧或一直在右侧，所以 $r \ne \underbrace{1 \cdots 1}_{n\text{ 个}}$ 且 $r \ne \underbrace{2 \cdots 2}_{n\text{ 个}}$。

因此，$r$ 一定是某一枚硬币 $c$ 的正序编码或逆序编码。对于前者，表明 $c$ 是假币且比真币重；对于后者，表明 $c$ 是假币且比真币轻。

现在讨论 $n<\dfrac{3^k-3}{2}$ 的情况：先将硬币每三枚作为一组。讨论剩下的硬币：

  1. 若没有剩下的硬币，直接进行接下来的过程；
  2. 若有剩下的硬币，将最后一枚硬币的编号 $+1$，再进行接下来的过程。

硬币的正序编号最高位是 $0$ 和是 $2$ 的数量是相同的，第一次称量可以正常进行，后续只需在硬币数量少的一端补上已知的真币。