8 瓶水 2 瓶有毒 6 个耗子 要求单次检验出结果

[eroko]

这题应该怎么算？

[dethan]

好残忍，鼠鼠那么可爱。。

[xdeng]

@yigecaiji <amp-youtube data-videoid="jYQEkkwUBxQ" layout="responsive" width="480" height="270"></amp-youtube>@xinh 我说错了讲的就是老鼠毒药

[AndyVerne]

@noe132 你这个混合方法有问题，因为一瓶水，被混合后不能重置为初始状态（相当于被污染了）

[suisetai]

拿一只老鼠一瓶瓶喂 死了就换下一只... 顶多用两只 当然 撑死不算

[ro2020]

4 楼方法是正确的

[Vegetable]

@suisetai 真他妈是个天才

[akira]

遇到这种问题 一律用 2 进制的思路去考虑 肯定对的

[looooooong]

@ro2020
@l00t 按照我对 4 楼方法的理解 假如六只全死了，到底是 001，110 还是 100，011 呢 当然类似的还有 101，010 这种的

[ro2020]

@looooooong 是的，我刚才在算的时候也发现了问题，这个方法不对

[xinh]

@yigecaiji <amp-youtube data-videoid="jYQEkkwUBxQ" layout="responsive" width="480" height="270"></amp-youtube>

[chrisouta]

可以把所有毒药可能的组合写到一个二进制矩阵 S 中，每行代表一种组合，一共有 C(8,2)行，8 列。相应的老鼠编码二进制矩阵记为 M(8,k), 每一列代表一只老鼠的喝药方案, 六只老鼠 k=6 。有 Binary(SM) = X，这里 X 也是二进制矩阵(大于零的元素视为 1)，可以为一个二进制 BCD 矩阵(类似上面李永乐老师的 100 瓶毒药编码矩阵)。只要解出来 M 矩阵就可以找出编码方式。上面李永乐老师的例子里 S 为单位矩阵，所以老鼠编码矩阵就等于 BCD 矩阵，不需要解，这个可能要稍微麻烦点了。

[Tumblr]

@xdeng #22 我看到题目也是第一时间想到了李永乐老师的这个视频！

[hm20062006ok]

8 瓶毒药两两混合一次得到:1+2,1+3...1+8,2+3,2+4,...2+8,3+4,3+5...3+8......7+8. 一共 28 瓶混合物，编号为 1-28， 转换为 5 位数的二进制（ 00001.....11100),按照上面回答种视频说的，小鼠 1 喝所有二进制第一位为 1 的混合物，小鼠 2 喝所有二进制第二位为 1 的混合物..... 需要 5 只小鼠可以检验出结果。

[noe132]

@hm20062006ok 一开始我也是这么想的。但是毒药是或运算，2 瓶只要有 1 瓶是毒药，混合出来就都是毒药了。实际上按照这个逻辑，应该检验 8 瓶里面哪 6 瓶不是毒药

[hm20062006ok]

@noe132 是的， 想错了

[Elethom]

其实五只就够了，这个问题一分钟答不上来的建议转行，这智商不适合做技术。

送一个拓展问题：四维空间的一个西瓜切五刀可以分成多少块？切六刀呢？

再进阶一步：m 维空间的一个西瓜切 n 刀可以分成多少块？（ m > 3，n > m ）求通解。

[chrisouta]

@Elethom 几只当然简单，复杂的是怎么设计哪只老鼠喝哪几瓶

[snw]

@Elethom
两两混合成 28 瓶是吧？我现在告诉你你的 5 只老鼠全死了，请问你找出来哪两瓶有毒了吗？

不要把 1 瓶毒药的解法想当然地拓展到 2 瓶毒药。

[snw]

顺带一提，这个链接提出的解法也是不对的。
blog.csdn.net/kingoverthecloud/article/details/4068[去掉此方括号]6129

反例：无法区分(000, 110)为毒药与(010, 100)为毒药这两种情况。

[Elethom]

@snw
一瓶毒只要 log2(n) 也就是三个就够了，当然没那么简单。