出几个烧脑的智力/算法题，顺便聊聊它们背后的数学

[mathzhaoliang]

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

问题之二：有 100 瓶药水和若干只小白鼠，其中一瓶药水是有毒的。正常的药水对小白鼠是无害的，但是有毒的药水则会杀死小白鼠。问最少需要几只小白鼠才能找出有毒的是哪一瓶？

欢迎 v 友们讨论。

第二个问题原表述有歧义：有的读者理解为取一只小白鼠，让它挨个喝下去不就行了？
现在重新表述为：规则允许每次可以将若干瓶药水搭配起来给某一只小白鼠喝下，且每只小白鼠只能被使用一次。问最少需要几只小白鼠。

我知道很多人做过这个题目，"称三次"，"二进制"。但是注意题目："背后的数学"。如果不说清背后的数学，那么它对你来说只是一道智力题而已，它的真正价值没有被发掘。举个例子：

如果把第二个问题改成有其中有两瓶是毒药呢？或者改成 "已知在你使用的小白鼠中，有一只小白鼠发生了变异，它对毒酒是免疫的，喝下去不会死，但是你不知道是哪一只“。
这两种情况下分别最少需要几只小白鼠？

我正在写一篇文章，打算详细聊聊这些问题背后的数学，其实如果你学过纠错码的知识的话，它们是很好理解的，而且对那些推广型的问题，你也能举一反三找到解答。

这里就显出数学在编程中的作用了。

此外如果有写过二维码编码器的同学，里面不就是一个 RS 码吗？如果你会懂 RS 码是怎么回事的话，小小 Hamming 码岂不更是不在话下？

博客文章已经写完，增加了对 leetcode 上的一道类似题目的解释。请移步 https://neozhaoliang.github.io/post/coin-and-coding-theory/

[mathzhaoliang]

@loryyang 是的，仓促成文，肯定很多不足。
@MisakaTang 我想你的问题可以从几个角度回答：1。程序复杂性上。如果是 39 枚硬币呢？或者更多呢？代码量增加多少？写起来快不快？至少纠错码的角度看只要遍历一次不共线的向量就行了。2. 程序可推广性如何？如果问题难度增加，程序怎么写？ 3. 我不用记忆具体步骤，理解了这个原理，随时可以写出一种正确的称法来。这算不算由技入道了呢？

[ballshapesdsd]

@mathzhaoliang #101 有一点不理解 2*2=1 是可以任意定义的吗？如果可以任意定义，那为什么 s1 可以用累加呢？还是说 s1 中的累加项只能有一个非零值？

[MisakaTang]

@mathzhaoliang 1. 程序复杂性 确实纠错码的构造更巧妙 2. 程序推广性 这得看问题的难度从哪个角度增加,如果现在给第一个问题加一个限制:每次把一个硬币放到天平上都记为使用硬币一次,给出在最少称重次数下使用硬币次数最少的解法.请给出纠错码角度的解法 3. 不用记忆具体步骤 搜索的方法也是推导出来的理解了之后也不用记忆步骤,这难道就不是由技入道了吗?

[ballshapesdsd]

@keylor #65 四分法：如果两份不相等，则再需要一次三分法就可确定假币，两次就找出假币。这时候你只确定在 6 个硬币中间，怎么一次就找出来了？又不知道假币更重还是更轻。另外你说的三分法，重量不同，也只确定了在 8 个硬币之中。还有 2 次怎么确定哪个是假币？

[mathzhaoliang]

@ballshapesdsd 不是任意定义的，必须满足域的公理。域算法里面有加法和乘法，每个非零元都有 "倒数"，且乘法满足结合律 a(bc) = (ab)c，加法乘法满足交换律 a(b+c) = ab + ac 等等。

如果定义 2x2 = 2, 则 2 = 2 x( 1 + 1) = 2 + 2 = 1 矛盾。若定义 2x2 = 0 则 2 没有倒数。若不然 2 x m = m x 2 = 1，则 2 x 2 x m = 2 x 1 = 2, 即 0 = 2，矛盾。

模一个素数 p 得到的剩余类满足域的公理，这个叫做有限域。密码学和纠错码理论就是建立在有限域上的。

[ballshapesdsd]

@mathzhaoliang #105 有意思。。

[ballshapesdsd]

@mathzhaoliang #105 leetcode 那道题答案好像有问题，猪死了就不能进行下一次实验了

[mathzhaoliang]

@ballshapesdsd 你说得对，我也在想这个事儿。

[ballshapesdsd]

@mathzhaoliang #108 想了想，死一次好像没什么问题。。唯一的问题就是这个和有限域好像没什么关系了，5=60/15+1 （ 4 个死亡时间和 1 个不死亡的可能），然后 5 的 r 次方大于 1000 就行了

[keylor]

@ballshapesdsd 也有道理哈

[dhsss]

@wohenyingyu02 …震惊了 还有这么理解的

[l00t]

@Kirscheis #69 再想了想，我之前的方案还是不对。因为最后要从有毒的里面找无毒的，和无毒里面找有毒的，难度完全不对等。

[l00t]

@mathzhaoliang 文章看完了，所以两瓶有毒怎么解？

[mathzhaoliang]

@l00t 在有限域上，按照本原元素的幂排列，加一组校验方程，这就得用程序算了。

[l00t]

@mathzhaoliang #114 能否再详细点， 你一句话里我有一半没看懂…… 本原元素是什么？幂排列是什么…… 假如 10 瓶里面有两瓶，这个有限域要怎么构建，里面几个值？可否给个例子演示下。

[mathzhaoliang]

@l00t 几句话说不清楚，需要你懂 Galois 域的知识。可以见[这本书]( http://vdisk.weibo.com/s/AcSJGKVz_Xdzf?category_id=0&parents_ref=AcSJGKVz_X6Sx,AcSJGKVz_Xe4e)的第 9 章。

[Xs0ul]

@mathzhaoliang 起手就是一个有限域，建议加一段介绍有限域上的加法和乘法

[l00t]

@mathzhaoliang #116 大致看了下，不是很能看懂。主要就是一个问题，我看到的 Galois 域里面的运算好像有用到异或？但是毒药的情况里，有毒的和有毒的在一起并不能变成无毒的。

不说 2 瓶的事，就说一瓶吧。假设题目改成 3 瓶药里面 2 瓶是毒药，一瓶没毒的。几次能找出没毒的那瓶？

[mathzhaoliang]

@ballshapesdsd 我想明白了，这个方法没有问题，猪死了它给出的校验子就是它死时对应的实验次数。

[mathzhaoliang]

@l00t Galois 域的知识对没学过的人不好解释。你写过二维码的编码器或者解码器吗？里面的 RS 码用的就是 Galois 域。

[mathzhaoliang]

@l00t 我知道两瓶毒药的时候怎么做了，我现在可以证明至少需要 9 只老鼠，大致方案也有，今晚想想。