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

[mathzhaoliang]

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

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

欢迎 v 友们讨论。

[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]

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