朝花夕拾

轻飘飘的旧时光就这么溜走 转头回去看看时已匆匆数年

称硬币问题、小白鼠找毒药问题与编码理论

2018-11-05


本文要讨论的问题比较常见,但是好像很少有人从纠错码的角度给出解释。从纠错码的角度看问题的好处是可以很容易理解为什么要这样设计策略,而且能举一反三处理其它类似的问题。事实上我觉得这种趣味问题正是帮助初学者理解纠错码基本概念的绝好例子。

不过本文并不假定读者事先学过编码论,但是需要懂一点有限域的知识。


称硬币问题

问题:有 12 枚外表一模一样的硬币,其中一枚是假币,其余都是真币。假币的重量与真币不同,但是更重还是更轻不知道。给你一个没有砝码和刻度的天平,最少称几次才能确保找出假币?

我们在有限域 \(\mathbb{F}_3=\{0, 1, 2\}\) 上考虑问题。记 \({\bf x}=(x_1,x_2,\ldots, x_{12})\),其中 \(x_i\in\mathbb{F}_3\)\(x_i=0\)\(x_i=1\)\(x_i=2\) 分别表示第 \(i\) 枚硬币是真币、是假币且重量为轻、是假币且重量为重。根据已知条件,\({\bf x}\) 中恰好有一个分量非零 (即发生了错误),我们的任务是设计一个称重策略找出错误的位置并确定错误的值。

任何称重策略都可以用一个 \(\mathbb{F}_3\) 上的 \(r\times 12\) 的矩阵 \(H\) 来完全刻画:\(r\) 是称重的次数,\(H\) 的每一行 \({\bf y}=(y_1,y_2,\ldots,y_{12})\) 对应一次称重,\({\bf y}\) 的第 \(i\) 个分量等于 1 表示第 \(i\) 个硬币在这次称重中放在了天平左边,等于 2 表示第 \(i\) 个硬币在这次称重中放在了天平右边,等于 0 表示第 \(i\) 个硬币在这次称重中没有被使用。

注意每次称重天平两边的硬币数目应当相同,这样才能得出有用的信息 (比如两边硬币数目相同且天平平衡,那它们一定都是真币)。如果你一定要在两边放上不同数目的硬币,那除非极特殊的情况 (比如假币特别重),否则你得不到任何有用的信息,白白浪费了一次机会。换句话说,在 \(H\) 的每一行中,1 和 2 出现的次数应该是相等的。

\({\bf s} = H{\bf x}^T\),则 \({\bf s}\) 是一个 \(r\times 1\) 的向量,\({\bf s}\) 叫做 \({\bf x}\) 的校验子 (syndrome)。这里的神奇之处在于 \({\bf s}\) 的值是可以从天平的状态推出来的,然后我们可以由此反解出 \({\bf x}\)

我们用第一次称重为例来说明这一点:设 \({\bf y}=(y_1,y_2,\ldots,y_{12})\)\(H\) 的第一行,则 \({\bf s}\) 的第一个分量 (记作 \(s_1\)) 为 \[s_1=\langle{\bf x},{\bf y}\rangle=x_1y_1 + x_2y_2 +\cdots+x_{12}y_{12}=x_iy_i.\] 其中 \(i\) 是假币的下标。

  1. 如果天平是平衡的,由于两边硬币数目相同,那么两边一定都是真币,假币不出现,即 \(y_i=0\),从而 \(s_1=0\)
  2. 如果天平左边向上翘起,由于两边硬币数目相同,这有两种可能:假币要轻一些,且放在了左边;或者假币重一些,放在了右边。即 \(x_i=y_i=1\) 或者 \(x_i=y_i=2\),总之 \(s_1=x_iy_i=1\) (注意在 \(\mathbb{F}_3\)\(2\times2=1\))。
  3. 如果天平右边向上翘起,由于两边硬币数目相同,这有两种可能:假币要轻一些,且放在了右边;或者假币重一些,放在了左边。即 \(x_i=1\)\(y_i=2\) 或者 \(x_i=2\)\(y_i=1\),总之 \(s_1=x_iy_i=2\)

于是 \({\bf s}\) 的值确实可以从天平的状态得出。

另一方面将 \(H\) 写成列向量的形式:\(H=({\bf c_1, c_2,\ldots, c_{12}})\),仍然假设编号 \(i\) 的硬币是假币,则 \[{\bf s} = x_1{\bf c_1}+x_2{\bf c_2}+\cdots+x_{12}{\bf c_{12}}=x_i{\bf c}_i.\]

\({\bf s}\) 与错误位置对应向量是共线的,所以只要找到 \(H\) 的列向量中与 \({\bf s}\) 共线的那一个 \({\bf c}_i\),则 \(i\) 就是出错的硬币,根据 \({\bf s}={\bf c}_i\) 还是 \({\bf s}=2{\bf c}_i\) 可以得出这枚硬币是轻了还是重了。但是这样做有一个前提,就是 \(H\) 的列向量必须两两不共线 (这蕴含了 \(H\) 的列向量都是非零向量),这样才能唯一地确定 \(i\),于是我们的问题转化为设计一个 \(r\times 12\) 的矩阵 \(H\)\(H\) 的每一行中 1 和 2 的个数相同,且 \(H\) 的任何两列互不共线,这个 \(H\) 叫做校验矩阵。

由于 \(\mathbb{F}_3\) 上总共有 \(3^r-1\) 个长度为 \(r\) 的非零向量,它们可以两两组成 \(\frac{3^r-1}{2}\) 对,每对中的两个向量是互相共线的,所以 \(\mathbb{F}_3\) 上最多可以取出 \(\frac{3^r-1}{2}\) 个互不共线的向量,于是 \(\frac{3^r-1}{2}\geq 12\)\(r\geq 3\),即至少需要称 3 次。

剩下的任务就是取出 12 个这样的向量组成 \(H\) 的列,然后适当给它们乘以 1 或者 2 使得 \(H\) 的每一行中 1 和 2 的个数相等,这样得到的 \(H\) 就符合要求。

比如我们取 \(H\) 如下:(这个取的规则是将它们三进制下对应的整数从小到大依次选取,比如第 1 列就是 001,下一个整数 002 与 001 共线不要,所以第 2 列是再下一个整数 010,第 3 列是下一个整数 011,第 4 列是下一个整数 012,下一个整数 020 与 010 共线不要,再下一个整数 021 与 012 共线不要,所以第 5 列是下下一个整数 100,以此类推)

1  2  3  4  5  6  7  8  9  10  11  12
0  0  0  0  1  1  1  1  2   2   2   2
0  1  1  1  0  0  0  1  2   2   1   1
1  0  1  2  0  1  2  0  2   1   0   2

这个矩阵的第一行已经符合要求,但是第二行有 6 个 1 和 2 个 2,不符合要求。我们在那些第一个分量是 0 但第二个分量不是 0 的列中调整使得第二行符合要求:这样的列是 2, 3, 4列,给靠右的两列第 3 和第 4 列乘以 2 得到

1  2  3  4  5  6  7  8  9  10  11  12
0  0  0  0  1  1  1  1  2   2   2   2
0  1  2  2  0  0  0  1  2   2   1   1
1  0  2  1  0  1  2  0  2   1   0   2

这时的 \(H\) 符合要求,于是一个称重策略应该是

第一次:5, 6,  7,  8 | 9, 10, 11, 12

第二次:2, 8, 11, 12 | 3,  4,  9, 10

第三次:1, 4,  6, 10 | 3,  7,  9, 12

如果第一次称重天平左边翘起,第二次称重右边翘起,第三次称重天平平衡,则校验子 \({\bf s}=(1,2,0)\),此向量等于 \(H\) 的第 11 个列向量 \(\times\) 2,于是第 11 枚硬币是假币且其重量比真币更重。

那么 3 次称重能不能称 13 枚硬币呢?答案是不行的,因为虽然我们可以从 \(\mathbb{F}_3^3\) 中选出 13 个互不共线的向量来,但是不可能适当给它们乘以 1 或 2 使得 \(H\) 的每一行中 1 和 2 的个数相等 (这个证明留给你,提示一下,每一行必然恰好有 4 个 0)。所以 13 枚硬币的话就需要至少 4 次称重了。

用同样的方法可以说明 \(n\) 次称重可以在 \(\frac{3^n-1}{2}-1\) 枚硬币中找出假币来,而硬币个数大于等于 \(\frac{3^n-1}{2}\) 则不行。

最后回顾一下这个解法的流程:

  1. 要能够从天平的状态得出有用的信息,必须在天平两边放置同样数目的硬币,即 \(H\) 的每一行有相同个数的 1 和 2,这时我们可以推断出校验子 \({\bf s}\) 的值;

  2. 另一方面 \({\bf s}\) 必然与 \(H\) 的某个列向量共线,所以只要 \(H\) 的列向量互不共线,就可以唯一地确定错误位置对应的列向量 \({\bf c}_i\) 并得出错误值。


小白鼠找毒药问题

问题 2:有 100 瓶药水和若干只小白鼠,其中一瓶药水是有毒的。正常的药水对小白鼠是无害的,但是有毒的药水则会杀死小白鼠。规则允许每次可以将若干瓶药水搭配起来给某一只小白鼠喝下,且每只小白鼠只能被使用一次。问最少需要几只小白鼠才能找出有毒的是哪一瓶?

如果你已经理解了前面称硬币的问题,那这个问题就更简单了。这又是一个 "在 xxx 中出现了一个错误,要求将其纠正之" 的问题,所以我们还是故技重施,用纠错码的思路来解决它。

在这个问题中,药水只有有毒和无毒两种可能,小白鼠也只有死活两种可能,所以只要在二元域 \(\mathbb{F}_2\) 上考虑问题即可。

\({\bf x}=(x_1,x_2,\ldots, x_{100})\),其中 \(x_i\in\mathbb{F}_2\)\(x_i=1\) 当且仅当第 \(i\) 瓶药水是毒药。根据已知 \({\bf x}\) 中恰好有一个位置为 1,即发生了一个错误,我们只要检测出这个错误位置即可。

注意在这个问题中,由于错误位置的值只能是 1,"检测一个错误" 和 "纠正一个错误" 是等价的:知道了错误的位置就知道了错误的值。但是一般来说它们是不同的,比如前面称硬币的例子。其中的差别马上就会看到。

跟上一个问题一样,任何策略都对应 \(\mathbb{F}_2\) 上的一个 \(r\times 100\) 的矩阵 \(H\),其中 \(r\) 是小白鼠的个数,\(H\) 的每一行 \({\bf y}=(y_1,y_2,\ldots,y_{100})\) 对应这只小白鼠喝下的药水编号:\(y_i=1\) 当且仅当这只小白鼠喝下了第 \(i\) 瓶药水。校验子 \({\bf s}=H{\bf x}^T\) 可以从小白鼠的状态得出 (\({\bf s}\) 的第 \(i\) 个分量是 1 当且仅当第 \(i\) 只小白鼠毒发身亡),而且 \({\bf s}\) 等于出错位置 \(i\) 对应的列向量 \({\bf c}_i\),所以只要 \(H\) 的任何两列互不相同即可根据 \({\bf s}\) 定出 \({\bf x}\) 的错误位置。

\(\mathbb{F}_2\) 上总共有 \(2^r\) 个不同的向量,于是 \(2^r\geq 100\)\(r\geq 7\),从而 7 只小白鼠就足够了。只要从 \(\mathbb{F}_2^7\) 中任选 100 个向量,将它们作为 \(H\) 的列向量即可。根据校验子 \({\bf s}\) 找到 \(H\) 与之相同的列向量 \({\bf c}_i={\bf s}\),则第 \(i\) 瓶药水就是毒药。

你注意到了吗?在这个问题中检测一个错误的时候只需要列向量两两不同即可,而上一个问题中纠正一个错误则需要列向量两两不共线。


Leetcode 上的一道题目

Leetcode 上有这样一道题

There are 1000 buckets, one and only one of them contains poison, the rest are filled with water. They all look the same. If a pig drinks that poison it will die within 15 minutes. What is the minimum amount of pigs you need to figure out which bucket contains the poison within one hour?

这个题目跟小白鼠找毒药很类似,但是有一个显著的不同,翻译过来就是:

有 1000 桶水,其中恰好有一瓶有毒。规则允许每次可以将若干桶搭配起来给某一头猪喝下,且每头猪至多可以被使用 4 次。问最少需要几头猪才能找出有毒的是哪一瓶?

注意原题中的表述 "在 15 分钟内死亡,要求在一小时内找出毒药" 其实是一个烟雾弹,它的本质含义就是一头猪最多可以被使用四次。

现在一头猪有 5 种可能的状态:始终活着,或者在第 \(k\) 次实验 (\(k=1,2,3,4\)) 后死亡,所以我们应该在模 5 的有限域 \(\mathbb{F}_5=\{0,1,2,3,4\}\) 上考虑问题,其中零元素对应活着,\(k(k \geq1)\) 对应猪死于第 \(k\) 次实验。

\({\bf x}=(x_1,x_2,\ldots, x_{1000})\),其中 \(x_i\in\mathbb{F}_5\),每个 \(x_i\) 只有 0, 1 两种取值,且 \(x_i=1\) 当且仅当第 \(i\) 桶水有毒。根据已知 \({\bf x}\) 中恰好有一个位置为 1,即发生了一个错误,由于错误的值是已知的,我们仍然只要检测这个错误位置即可。

问题又转化为设计一个 \(\mathbb{F}_5\) 上的 \(r\times 1000\) 的矩阵 \(H\),其中 \(H\) 的一行对应一头猪,该行的第 \(k\) 个分量值为 \(j\) 表示这头猪在第 \(j\) 次实验中喝下第 \(k\) 桶水,其中 \(j=0\) 表示猪不喝这桶水。容易验证若这头猪死于第 \(i\) 次实验则校验子 \({\bf s}=H{\bf x}^T\) 对应的分量即为 \(i\),否则猪始终活着从而此分量为 0。要使得 \(H\) 能够检测一个错误,只要 \(H\) 的任何两列互不相同即可,这时校验子 \({\bf s}\) 与错误位置对应的列向量是相同的。

由于 \(\mathbb{F}_5\) 上最多可以取出 \(5^r\) 个不同的向量,\(5^r\geq 1000\) 说明 \(r\geq 5\),即 5 头猪足矣。