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

[mathzhaoliang]

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

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

欢迎 v 友们讨论。

[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 现在更新了吗？目录只能看到一个旧的 “称硬币问题与编码理论”