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

[mathzhaoliang]

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

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

欢迎 v 友们讨论。

[loryyang]

说实话我很难理解 lz 发这个帖子为了什么，如果你想分享，那么就直接把背后的数学知识贴出来，没必要卖关子。知识这东西，都是建立在前人的基础上的，没看过的人，你要让他从低基础开始直接赶上前人那么多年的积累，那根本不可能。而如果想引导别人思考一遍，你给出原理，大家学习一下也就都受益了
如果你只是想看看大家对你已掌握的知识如何的无知，给自己增加点快感，那就当我没说

[jkeylu]

楼主题目用词不严谨，不是“最少”而是“至多”

[ballshapesdsd]

@mathzhaoliang #40 大佬可以公布答案了，这都发帖三个小时了

[mathzhaoliang]

@ballshapesdsd 正在写 ing，说清楚的话比较长，所以麻烦等一会。

@loryyang
”如果你想分享，那么就直接把背后的数学知识贴出来“。就是想分享，很快就会贴的，只是我还没看到那个中文网页上有现成的，所以正在写 ing。

[jaleo]

只要求答案的话 第一题是小学五年级数学题 最少 3 次 至少 4 次 大纲里要求掌握的

[mathzhaoliang]

@jaleo 现在小学生都这么厉害了？我有点担心我家娃将来跟不上啊 ..

[iceheart]

第一题有通解，大概 01 年或者 02 年在水木清华上看到过，有个叫袁哥的用信息论分析，给出的解法。

[zjxlim]

第一题可以看成二叉树叶结点的最大深度，有不同的构造方法，（最少 2 次最多 5 次的和最少 3 次最多 4 次的）
第二题同理有不同构造方法

[mathzhaoliang]

我先大致说一下吧。这两个题都有一个共同点 "恰好有一个 xxx 和其它不同"，也就是说，在一个码子中有一个位置发生了错误，要纠正这个错误。

这就是纠错码理论可以应用的地方，而且纠正一个错误的当然就是 Hamming 码 ~。

[maswang]

题 1 想到还有一个方法：
分成 4 组，每组 3 个。
第一次称其中 2 组。
如果一样重，则假币在另外两组中
如果不一样重，假币正在在称的两组中
即第一次称之后确定 1/6

第二次：
在确定假币的 6 个中，分成 3 组，每组 2 个
称其中两组：
如果一样重，则假币在剩下的 1/2 中
如果不一样重，则假币在 1/4 中

如果第二次一样重，1/2 确定假币，只需要再称 1 次了，拿 10 个正常币中的 1 个来比较一下就行了，即 3 次确定假币
如果第二次不一样重，因为最后 4 个已经 2 个 2 个称过一次了，所以也有 50%概率一次确定到假币，具体就不详细说了

[loryyang]

@mathzhaoliang 期待大作，真的，你完全可以写完再发这个帖子，一样很多人来看的

[talen666]

“最少”称几次才能找出假币，最少 emmm

[swordmaster]

第二题李永乐讲二进制的时候用过这个例子

[MisakaTian]

请把烧脑两个字去掉？

[mario85]

第一题我居然想歪到分解质因数上去了，最多 4 次，不知道能不能更少。
前面楼的 3 次好像都是剩两枚算最后一次，个人觉得只有两枚硬币的情况下无法知道哪个是假，只剩两枚的情况下还需要用已知的真币再测一次

[sun1719]

问题一: 之前思考过，也看过些文章。
具体数学考虑是用信息熵的理论（香农）；
结论: n 个硬币(不知道假币是轻还是重)，至多需要次数 log3(2n)确定真假。

[mathzhaoliang]

@sun1719 不是的，信息论只能给出一个直观的解释，并不是严格的论证。用到的是纠错码的理论。

[ballshapesdsd]

@mathzhaoliang #57 大哥，我等了一下午了

[jin5354]

你一个数学科班的人，来满是工业界程序员的论坛问题解，我们用标准 leetcode 刷题解题思路给你回，你表示 nonono 都不是我要的，这不是鸡同鸭谈

[murmur]

@A3m0n 杯子没碎但是出现裂纹怎么办？