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

[mathzhaoliang]

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

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

欢迎 v 友们讨论。

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

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

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

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

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

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

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

[lookforsex]

问题一用二分法？

[mathzhaoliang]

@lookforsex 什么是二分法？

[murmur]

我记得第二个题的漏洞不是小白鼠喂水会被撑死么

[Rizio]

第二题，一只？让它一直喝到死。

[SuperNovaSonic]

转换成二进制去看这个问题就简单了

[mathzhaoliang]

@Rizio 应该加上限制，喝药 24 小时以后毒药就会发作。要求 24 小时内找出毒药。

[binxin]

@lookforsex
至少第一轮不能两等分，需要三等分。

[meefly]

第一题四次，不知道能不能更少

[binux]

@mathzhaoliang #5 24 小时以后才发作，24 小时内无论如何都找不出来。。

[chwhsen]

一般说到背后的数学时，第一步就是把具体的数量抽象成`n`个

[feiyuanqiu]

把 12 枚硬币按四个一组分成三组，找到重量与其他两组不一致的一组，同时能知道假币相对真币轻还是重（ 2 次）；将包含假币那组四个硬币按两个分成两组，找到假币那组（ 1 次）；比较假币组两枚硬币重量，找到假币（ 1 次）。需要称 4 次

[mathzhaoliang]

@chwhsen "一般说到背后的数学时，第一步就是把具体的数量抽象成 n 个"。有时候一上来就讨论一般的情形会把问题复杂化。很多数学定理是先对特殊情形加以证明，然后推广到一般的。

@Rizio
@mathzhaoliang
@binux
我也觉得这个原表述不好，应该直接告诉读者无歧义的规则，我觉得应该表述为 "规则允许每次可以将若干瓶药水搭配起来给某一只小白鼠喝下，且每只小白鼠只能被使用一次"。

[Myprincess]

我出一个:
例子:615+X^2=2^Y 求 X 与 Y 的值
Z+X^2=2^Y
Z 在什么情况下本题无解.

[rabbbit]

第二题不考虑撑死 1 个,考虑撑死 7 个,貌似在哪看过...

[chwhsen]

@mathzhaoliang 的确是这样的

[dnhzm]

第一个 4 次，先分成 3 份，比较两次，得到重量有差别的那份，然后再拿基准的硬币与那份比较。
第二个是 7 只老鼠，因为是 2 的 7 次方＞ 100，每个药按二进制编码，然后按位数等于 1 的投喂药。看死了几只就知道落在哪位为 1，然后就求出来了。
很久之前看过

[zhzer]

第一题二分，三次
第二题二进制分桶，七次

此贴完结

[Voichesapete]

@murmur 没说剂量。如果有毒的那瓶喝一滴也会死呢 2333

[Nimrod]

第一个三次 之前貌似做过这个题
第二个 DP

[stevenbipt]

第一个先四个一组分三个看哪一组和另外两组有差异，然后在把有差异的一组取三个对比，如果有一个与另外两个有差异则那个是假币，如果没有差距则没有对比的那一张是假币，一共需要两次称重。

[wohenyingyu02]

1. 最少称 2 次。首先拿两个比较，正好有一个是假币，再随便拿一个和其他比，就是最少的情况。
2. 一只。

[mathzhaoliang]

@zhzer 你说的大体意思我懂，但是不是我要的解答。

[Exin]

第一题的最佳解是 三次 ，不是四次。有比二分法更好的解法。
第二题大家都会。

[Exin]

@zhzer 二分如何解出三次的？

[murmur]

第一个题不是一次都不需要么
既然假币和真币的差别只有重量区别 而且是只有天平才能发现的问题
那就是说把这 12 个硬币都花掉不就解决了

[denano]

第一题一开始 3 等分找出重量不一致的那一堆再 2 等分，4 次
第二题就是一开始把 50 瓶药混在一起喂，就是 2 分查找。。

[LadyChunsKite]

https://leetcode.com/problems/poor-pigs/description/

[dingyaguang117]

第一题是 google 埃里克·施密特 面试别人的题，最多 3 次，过程比较复杂

[yukiww233]

2.每瓶药水等分并编号 1-100，用二进制表示占 7 位，7 只老鼠喝对应二进制位为 1 的的药水，死了该位为 1，拼起来就完事

[yukiww233]

1 在面试时候被问过，半天没答上来

[mathzhaoliang]

@SuperNovaSonic
@yukiww233
@Exin
@zhzer

如果是其中两瓶有毒呢？

[ch365]

只要找到假币的话总共称三次，如果还要知道假币轻还是重则要称四次
首先分成三组每组四个，第一次称其中两组。
如果，第一次两组一样重，假币则在第三组的四个中；
这种情况下，第三组的四个中，天平两边各放一个，一样重假币在没称的两个中，不一样重假币在天平上的两个中；
第三次拿一个真币和一个未知币称可以找到假币。
如果，第一次两组不一样重，假设轻的那组标为 0，重的那组标为 1，剩下的真币组标为 2 ；
第二次，天平左右这样放: 001 vs 012 ；
如果一样重，假币在组 0 和组 1 中没放上天平的三个硬币中；
第三次拿组 1 中剩下的两个放上天平；如果一样重，假币是租 0 中剩下的那个，否则假币就是重的那个
如果第二次称，001 的一边较重；那么假币在 001 的 1 或者 012 的 0 之中；两个币第三次称下确定假币。
如果第二次称，012 的一边较重；那么假币在 001 的两个 0 或者 012 的 1 之中；三个币第三次可以确定假币

[mathzhaoliang]

@ch365 如果知道背后的数学的话，就可以设计出正确的方案来。并不很难，三次就知道轻重。光靠自己试的话累死不说还找不到正确的方案。

[SuperNovaSonic]

@denano 第一题是求最好情况，如果一开始三堆上称的那两堆重量一致，直接确认假币在剩下一堆里，所以一共三次就好了，4 次是最差情况下的

[binux]

@mathzhaoliang #29 13 只

[ch365]

@mathzhaoliang 恩，三次就可以知道轻重，假币则在第三组的四个中的情况，后面称重设计有误。

[A3m0n]

我也来补两个，第一题是小白鼠的简单版本：

有一批玻璃杯（产品的优劣程度完全相同），和一幢高 100 层的楼（ 1 层到 100 层，不存在 0 层）。现在要测试这批玻璃杯的耐摔程度，即玻璃杯如果在 n 层下落没碎，在 n+1 层下落碎了，那耐摔程度就是 n。请问：

1：最少牺牲多少个玻璃杯？
2：最少测试几次？
（两个问题相互独立）

还有一题题目比较恶俗，但是解起来还是比较有趣的。我想想有什么不怎么恶俗的表达方式，如果想不到的话，待会上题目。

[MisakaTang]

数学之美番外篇：快排为什么那样快 : http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/
这篇博客我感觉是讲到了背后的数学原理了 可以看一下

[loryyang]

第一题答案是三次，https://gist.github.com/zjucloud/eee320c016e670ddfef111c386ad9b26
直接写的，不确定一定正确：
1：平均分三组,A B C
A vs B
A < B or A > B 看 2.1, A == B 看 2.2

2.1
说明在 A,B 里面，由于 A 和 B 相对等价，我们可以假设 A < B （反过来就把 AB 互换即可）：这样只可能是 A 有一个硬币轻，或者 B 有一个硬币重
A 和 B 都分成 2+1+1，表示为 A1,A3,A4 和 B1,B3,B4
我们从 C 里面取正常的硬币 X，然后 A3 + B1 VS A4 + B4 + X，把 A1 和 B3 留下
三种情况：
<：2.1.3
>：2.1.4
=：2.1.5

2.1.3
A3 + B1 < A4 + B4 + X
说明 A3, B4 有问题，因为之前是 A < B，所以要不是 A 的只可能轻，B 的只可能重, B1, A4 如果有问题，应该是>而不是<
A3 和 B4 都是一个，所以用 3.1.2 解法即可

2.1.4
A3 + B1 > A4 + B4 + X
反转了，说明 B1,A4 可能有问题，B1 是两个，A4 是一个
我们把 B1 拆成 B11 和 B12，然后 B11 + A4 VS X + X:
<:说明 res = A4
>:res=B11
==:res=B12

2.1.5
A3 + B1 == A4 + B4 + X
说明剩下的 A1 和 B3 有问题，和 2.4 类似，拆分 A1 为 A11, A12
然后 A11 + B3 VS X + X
<: res=A11
>: res=B3
==: res=A12

3.1
说明 C 有问题
C 分为 2 + 2：M, N
M 再分 M1, M2，然后 M1 VS M2
如果 M1 != M2 看 3.1.2，否则看 3.1.3

3.1.2 M1 != M2 说明 M1, M2 有一个有问题
取一个正常的 X vs M1，如果不平衡，res=M1 否则 res=M2

3.1.3
说明 N 里面有问题，和 2.3 一样，取一个正常的 X vs N1，如果不平衡，说明 res=N1，否则 res=N2

[mathzhaoliang]

@MisakaTang 那些写数学之美的人 (包括吴军)，都不是数学科班出身的，所以遇到一个好玩的题目和一个好玩一点的解释就大惊小怪一番。其实那篇文章也没写到点子上。

[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 杯子没碎但是出现裂纹怎么办？

[jin5354]

思维方式都不一样，你就直接分享呗，虽然我预料对于绝大多数码农都是屠龙术了。。

[wayne1027]

最少的话。。。不就是纯看脸了吗。
1.随机取一枚 A，与另一枚 B 对比，一样重，则两枚都是真币；
2.取一枚真币 A 或 B，另随机取一枚 C，这时候不一样重了，则刚好 C 就是假币。
所以，运气爆炸的话，最少只用两次……轻喷…

楼上的三分法，就是完全不看运气了。

[Wincer]

第二题是 7 只，2 的 7 次幂大于 100

[summerluqman]

等待李老师视频

[keylor]

第一题有比三分法更优的解--四分法。下面论证。
三分法：也就是分成 3 等分，第一次分成 4,4,4,取两份称重，根据重量相等还是不同来确定假币所在的堆，最终要称三次。
优化的四分法：分成：3，3，3, 3 四份。称重两份,那么，如果两份不相等，则再需要一次三分法就可确定假币，两次就找出假币。如果相等，则称重剩余两份，再三分法，需要三次。
总结：优化的四分法有二分之一的概率只要两次即可确定假币，二分之一概率三次确定假币。期望值是 2.5 次。

还有谁能给出比我次数期望更低的解不？

[Rizio]

@wayne1027 其实看脸的话一次就行了，直接拿一枚说这是假的，比真的轻 /重，蒙对了就行 doge。

[keylor]

@loryyang 看我四分法

[keylor]

@Exin 有比三分法更好的

[Kirscheis]

你的问题太简单了，谈不上烧脑，给大家来个难的

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

我可以给一个信息论的估计，总信息熵是 S = lg C_{1000}^2 = lg 495000，每用一只白鼠，最少可以得到的信息是白鼠死了或者白鼠活着，则得到的信息熵至少为 S = lg 2，故可以估计出最多需要的数量是 ceil( lg 495000 / lg 2 ) = ceil( 18.9 ) = 19。

请只用 19 只白鼠给出一个构造性的办法

[mathzhaoliang]

@keylor
@Rizio

题目是要求一定能确保找出假币最少需要称几次

[hundan]

第一题的问题 就是问在最差情况下的最优解 同学们不要抠字眼拿运气说事啊

[SNOOPY963]

各位，这个上限是用信息论解决的，至于怎么构造是剩下的事情。第一题很小时候就接触过，今年才突然醒明白这是信息量处理的问题。再一看信息论早已有定论了。

[Exin]

@keylor 要不你再想想...

[SNOOPY963]

有 12 个硬币，只有一个重量不同（轻重未知），利用一个无刻度天平，通过 3 次平衡，找出那枚硬币。求解法？ - Jun LI 的回答 - 知乎
https://www.zhihu.com/question/21677131/answer/323179768

人家已经有回答了，我就不多说了。

[frienmo]

第一题背后的数学是信息熵，学熵的时候做题都证明过。

[mathzhaoliang]

@SNOOPY963 不不不，他的表述漏洞太多，似搭不搭边。

[murmur]

@Kirscheis 让小白鼠互相繁殖可以么

[linKnowEasy]

对楼主即将完成的文章很感兴趣.
有博客啥的么？

[mathzhaoliang]

@linKnowEasy 在这里 https://neozhaoliang.github.io/

欢迎顺便去项目上点个赞～ https://github.com/neozhaoliang/pywonderland

[Xs0ul]

@mathzhaoliang #78 现在更新了吗？目录只能看到一个旧的 “称硬币问题与编码理论”

[aheadlead]

@mathzhaoliang 膜拜大佬

[l00t]

@Kirscheis #69 给瓶子编号，然后取 998 瓶混合成一瓶，这样混出 C(1000,998) 瓶，其中一瓶是恰好排除了有毒那两瓶的最终混合物无毒的。然后就回到 C(1000,998)瓶中找一瓶无毒的问题了。

[mathzhaoliang]

@Xs0ul
@aheadlead

已经更新啦，地址在 https://neozhaoliang.github.io/post/coin-and-coding-theory/

欢迎提出批评和改进意见～～

[mathzhaoliang]

@SNOOPY963
@aheadlead
@Xs0ul
@linKnowEasy
@frienmo

目前只完成了第一题的部分，第二题还在写作中。见 83 楼链接。

[lueffy]

@loryyang 也不一定啊 因为如果说这个帖子 楼主直接把答案放出来，我肯定不会细看的；相反，如果只给了问题，没有答案，你才会

[lueffy]

@loryyang 也不一定啊 因为如果说这个帖子 楼主直接把答案放出来，我肯定不会细看的；相反，如果只给了问题，没有答案，你才会有兴趣去思考一下

[linhua]

http://paulbourke.net/fun/counterfeit.html
https://en.wikipedia.org/wiki/Balance_puzzle#Generalizations

[mathzhaoliang]

@linhua 第一个链接里的文章最接近我的叙述，不过我觉得没有我的写的好～
第二个链接表示看不懂。

[ballshapesdsd]

@mathzhaoliang #88 大佬，012 和 021 为啥共线啊？看不懂

[linhua]

@mathzhaoliang
https://en.wikipedia.org/wiki/Balance_puzzle
“ Note that with 3 weighs and 13 coins, it is not always possible to determine the identity of the last coin (whether it is heavier or lighter than the rest), but merely that the coin is different. ”

[mathzhaoliang]

@ballshapesdsd 在有限域 F_3 里面，运算都是模 3 意义下的，1x2=2, 2x2=1。向量 (0, 1, 2) 乘以 2 以后是 (0, 2, 1)，它俩只差一个倍数，当然共线啊。

[mathzhaoliang]

@linhua 这个我在文章中写了原因了。13 枚硬币里面任取 12 枚，在这 12 枚里面要么找出假币且确定出轻重，要么什么也找不到，当然剩下的那个是假币 (但不知道轻重)。

[ballshapesdsd]

@mathzhaoliang #91 学到了

[KellenChou]

@mathzhaoliang 文章中 “如果天平是平衡的，由于两边硬币数目相同，那么两边一定都是真币，假币不出现，即 xi=0，从而 s1=0。”
应该是 yi=0 吧。

[mathzhaoliang]

@KellenChou 是的，笔误了。

[mathzhaoliang]

@KellenChou
@ballshapesdsd
第二个问题也写完啦。

[mathzhaoliang]

@LadyChunsKite 已经增加了对这个问题的解释。

[loryyang]

@lueffy 这个就和做 leetcode 一样啊，你知道你可以去评论区看到各种解法，你提交之后可以看到错误的 test case。但是你依然会选择先自己解决问题

我并不觉得楼主把答案扔出来就会妨碍你去探索问题了

[MisakaTang]

看完了楼主的博客个人感觉用纠错码和三分来解这个问题只是两种不同的方法而已,三分的方法是把问题转换到了程序员熟悉的搜索领域然后用三分来解决,楼主的解法是把问题转换到了数学工具上然后来解决,我感觉这也只是解决一个问题数学和计算机思维的两种不同的表现而已,至于说搜索的解法没有接触到问题的本质这一点我想问本质是什么,楼主的解法我也可以看成是纠错码这个工具正好能套中这类问题罢了

[loryyang]

看了文章，写的很清楚，不过感觉对纠错码的基础可以再展开多说点