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

[eroko]

这题应该怎么算？

这道题不一定有解，这个只是别人问我的，但是我自己又不会……

[noe132]

将 2 瓶水两两组合混合一共 8x8=64 种状态，编码为 0-63，每种状态代表任意 2 瓶水的 combo，6 只耗子=6bit，每只耗子毒死 /存货代表 1bit，6bit 一共 2^6 = 64 种状态，将上面组合的 64 种状态再根据每一种状态对应二进制位混合出 6 瓶水，给 6 只耗子喝，根据最后结果就可以推算出来 8 瓶水哪 2 瓶有毒了。

[Samuelcc]

详细说下单次检验是什么意思？是不能看任何前置的检验结果吗？
感觉思路应该和混合水缩小范围相关

[touchwithe]

1. 拿出一瓶水，记为 A，向剩余 7 瓶中都倒入一点。
2. 7 中拿出 6 瓶，剩余一瓶记为 B 。
3. 6 瓶水分别喂 6 只耗子。
可能的结果：
死一只，对应喝的水有毒，B 有毒。
死两只，对应喝的水有毒。
全死了，A 有毒。

[l00t]

一次就检验出来，那就不能等待之前的喝药结果了。

没仔细验算过，你试试这个思路可行否：

将 8 按 2 进制拆出来，得到 8 个三位二进制数。看每个位上，是 0 的派一只老鼠，是 1 的派一只老鼠，这样三位三个 01，正好 6 只。喝完后看结果，根据死的老鼠找出毒药。

[LZSZ]

几瓶混在一起试错

[touchwithe]

@touchwithe #3 想错了，不对。还是一楼的方法好！

[eroko]

@Samuelcc 单次检验就是喂一次就能得到结果

[zxCoder]

@noe132 能再详细解释一下吗大佬

将上面组合的 64 种状态再根据每一种状态对应二进制位混合出 6 瓶水，给 6 只耗子喝，根据最后结果就可以推算出来 8 瓶水哪 2 瓶有毒了。

这段读得有点费劲。。。

[46fo]

@eroko 单次检验就是喂一次就能得到结果 那不就是 6+2=8 吗。。。拿六瓶喂六只 都没死 那就是剩下的 2 瓶有毒吗？死了对应的那瓶就有毒？是我理解错了吗？

[fisherman0459]

@xdeng 如果六只里面只死了一只呢？

[qsmd42]

1 2 3 4 5 6 7 8
V V V V V V
A B C D E F

这样?

[xinh]

2 楼的那种二进制解法，在李永乐的视频里学的，有一期讲这个数学

[46fo]

@fisherman0459 啊这。。。一楼字多一楼肯定对 哈哈哈

[46fo]

@xinh +1 但好像说的不是耗子毒药

[yigecaiji]

@xinh 能给个视频名字或链接吗？有时间一定好好学一下

[yxt]

@noe132 混出 64 瓶水, 现在有 2*8=16 瓶水有毒了, 6 只耗子能找的是 64 瓶水里一瓶有毒吧?

[AngryPanda]

2 只耗子🐭就检验出来了

[hm20062006ok]

@noe132 "将 2 瓶水两两组合混合一共 8x8=64 种状态" 不是只有 28 瓶(两两混合后的)+ 8 瓶(原始的) = 36 种状态吗？

[AndyVerne]

8 瓶水，分四组（一组两瓶），一只老鼠喝一组如果

[AndyVerne]

@AndyVerne 8 瓶水，分四组（一组两瓶），一只老鼠喝一组，还有 2 只老鼠多出来，
如果 3 组没事，没事，那么有毒的一组就包括那两瓶有毒的水
如果 2 组出事，拿出两组的其中各一瓶，用多出的两只老鼠，根据情况对应排除，就能得到结果

[dethan]

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

[46fo]

@yigecaiji

@xinh 我说错了讲的就是老鼠毒药

[AndyVerne]

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

[suisetai]

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

[ro2020]

4 楼方法是正确的

[Vegetable]

@suisetai 真他妈是个天才

[akira]

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

[looooooong]

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

[ro2020]

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

[xinh]

@yigecaiji

[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) 也就是三个就够了，当然没那么简单。

[Elethom]

@snw
两瓶毒的情况，应该是对半分的。ABCD 、EFGH 、ABEF 、CDGH 、ACEG 、BDFH 这样子，可以理解为一个西瓜切三刀（就是我上面那个比喻），扩展到无限维度就可以解决更多瓶子的问题。上面我说五瓶确实是草率了，我道歉。

写了一段代码验证：
（ Swift 的编译检查不怎么待见 bitwise calculation 的样子，所以写成 Int 了，见谅）
https://gist.github.com/Elethom/e31af1a9f576d150aa691c5468bed379

[tianxia]

不需要什么算法，直接给 6 只耗子分别喂 6 瓶水，就保证单次检验出结果，不信可以尝试

[Mutoo]

@tianxia 是呀
6 只都没事，剩下两瓶有毒
5 只没事，1 只喝的是毒，剩下一瓶有毒
4 只没事，2 只喝的是毒。
根本不需要什么算法。

[tianxia]

@Elethom 会导致毒药剂量不够，毒不死

[Elethom]

@Mutoo
剩下的是两瓶。

[tianxia]

@Elethom 实际给你操作，保证一次出结果

[Mutoo]

@Elethom 对哦，走神了

[chrisouta]

https://en.wikipedia.org/wiki/Group_testing
果然深似海，学到了很多，感谢楼主的问题。
现有的理论还没有保证最优的算法，问题确实需要对矩阵进行搜索，wiki 里提到了几种搜索方法可以参考。
甚至还有老鼠有概率死有概率不死的扩展，更复杂了🐶

[Elethom]

#41 是我傻逼了。下界是 5 没错但是重新算了下上界还要再高一点。

[Elethom]

@Elethom 大概在 log(2, n) * 2 * log(2, n/2)

[chrisouta]

2 瓶毒，上界应该是下界加 1，六只老鼠，所以问题一定有解，看来 6 只老鼠不是随随便便选的。
In scenarios where there are two or more defectives, the generalised binary-splitting algorithm still produces near-optimal results, requiring at most d-1 tests above the information lower bound where d is the number of defectives.

[Elethom]

@chrisouta
的确比看起来更复杂。 😭

[elfive]

8 瓶水放到 9 宫格里，每行每列取样混在一起，正好 3 行 3 列，6 只耗子一次性喝混出来的一瓶，就可以了。

这就是二维的奇偶校验。

[chrisouta]

#53 两瓶毒在对角上无法区分在主对角还是次对角吧。这里的加法运算毕竟不是模二加，是直接或运算，跟奇偶校验应该不同。

[popil1987]

按照一楼的解法：8 瓶里 2 瓶有毒共 28 种组合（状态），那么 5 只老鼠可以表示 32 种状态就可以了吧，是不是能让一只老鼠去做电击实验？

[SlipStupig]

@suisetai 万一老鼠都变异了毒不死怎么办呢。。

[palfortime]

@noe132 #1 这种二进制编码的方案只能找 64 瓶里只有 1 瓶有毒的情况吧，混合出来的 64 瓶远远不只 1 瓶有毒。多瓶叠加在一起，无法用 6 只老鼠来找出吧。
没有想到单次校验的。
我的想法是 8 瓶分成 2 批，再用这种位编码的方式来找出每组里有毒的。具体会产生两种情况：
2 批都有死或者都没有死，这样用位编码方式来算，用 4 只来试就可以。
另外一种情况就是只有 1 批有死。这种情况有分为两种子情况：1. 没死的那批，00 是有毒的。2. 2 瓶有毒都在 1 批。
针对子情况 1，找没有死的去喝 00，挂了就出结果。没有挂的话，那么现在还活着的还有 4 只，4 只对应有毒的那批的 4 瓶。那么结果也可以出来。

[45HXlKzal6W56zUJ]

@Elethom #45 剩下两瓶，一有一无毒，你再喝一瓶

[ZeoKarl]

六个老鼠一只一瓶,面试官再喝一瓶.最后一瓶自己的.

[man9820]

@suisetai 他要一次性，大概意思是同时进行，要不方式太多了

[0d]

@tianxia #42 这个有点问题，6 瓶里有一瓶有毒，那么无法 判断剩下的两瓶里哪一瓶有毒

[sujin190]

这不就是二分法查找么，不很简单么，也需要讨论的这么复杂么。。。

[bk201]

@nieyujiang 你自己不用喝，结果就出来了呀

[cking]

随便拿一瓶 给老鼠喝 然后把老鼠弄死 告知实验结果 这瓶有毒 然后这题结束 因为还有一瓶有毒的 肯定不会尝试 所以这题一次就结果了

[snw]

@sujin190
你试试？

[iwasthere]

数学渣，评论看的懵逼

[sujin190]

@snw #65 8 瓶水分成 4 瓶两堆，给两只老鼠喝

如果都死，那就是两个 4 瓶里各 1 瓶有毒，然后每个 4 瓶再分成 2 瓶每堆，然后没边再各取 2 瓶一堆给两只老鼠喝，就能确定有毒的在哪 2 瓶里，最后两只老鼠在试剩下分成两堆的 4 瓶就能确定哪瓶有毒了啊

如果只有一边死，那就确定两瓶有毒的都在一边的四瓶里，另外 4 瓶就可以扔了，然后再把有毒的 4 瓶分成 2 瓶两堆，给两只老鼠喝，重复刚才的流程就是了啊

这不简单么，有啥好讨论的

[Dvel]

这题目出错了，8-2=6，这题不用算法，直接怼就行，应该是更多的瓶子或更少的老鼠。

[Dvel]

@Dvel #68 说错了，死一只的话就检测不出来了。

[tiramice]

@sujin190 要求单次检验出结果，你这检验几次了？

[sujin190]

@tiramice #70 好吧，单次检测时这个意思啊。。我错了

[cyrbuzz]

分成两组 1-4 。

每组 4 瓶编号 1-4 。

用三只，

一只喝 1,3，一只喝 2,3，一只喝 1,2 。

另外一组分别喝，1,3 2,3 和 4 。

A: 13 和 23 死掉的情况，看另一只喝 1,2，死了，1 和 2 都有毒。没死，3 确定有毒，4 可能有毒看下一组情况。
B: 13 死了，23 没死，1 有毒，4 可能有毒看下一组情况。
C: 13 没死，23 死了，2 有毒，4 可能有毒看下一组情况。
D: 13 和 23 都没死，4 可能有毒看下一组情况。

此时看另一组：

A1: 13 和 23 死掉的情况，4 死了，3 和 4 有毒，4 没死，3 和上一组 4 有毒。
B1: 13 死掉了，23 没死，4 死了，14 有毒，4 没死，1 和上一组 4 有毒。
C1: 13 没死，23 死了，24 或者 2 和上一组 4 。
D1: 13 和 23 都没死，4 死了，4 和上组死掉的那个没死就是上组 4，4 没死，把上组的`可能`换成`肯定`。

[Samuelcc]

搜了一下，感觉应该是找到正解了。这道题目是 group testing 问题中的 non-adaptive 情况，应该是这类型题目最难的一种变体。解法是构建 t-separable 的矩阵进行测试，测试后将结果还原。
这篇文章有比较详细的论述，有兴趣的可以看看 https://people.cs.umass.edu/~arya/courses/690T/lecture14.pdf

[rationa1cuzz]

@cyrbuzz 两组 X 、Y 假设都在 X 组 A 鼠(13) B 鼠(23) C 鼠(12) 假设 12 都是毒药 ABC 都死 假设 13 都是毒药 ABC 都死

[Ritr]

@suisetai 绝了

[ElmerZhang]

假设 8 瓶水为 1-8，第一轮先给一只老鼠喝 1+2+3，另一只老鼠喝 4+5+6 。
假如某一只老鼠死掉，最多再用两只老鼠即可找出其中有毒的水。剩下的 7 、8 再用一只就可以找出有毒的水。
假如第一轮都没死，就是 7 、8 有毒。

[ElmerZhang]

看错题目，要求单次，我再想想

[cyrbuzz]

@rationa1cuzz 额，说的是= =，少一组验证。

[ElmerZhang]

仍然编号 1-8，6 只老鼠分别喝 1+2 2+3 3+4 5+6 6+7 7+8 。
想了一些用例，应该是可解的。

[wuxinling]

如果水多一些还需要好好考虑，

[Xs0ul]

@ElmerZhang #79 13 和 23 是一样的，都是前三只都死

[Otho]

@ElmerZhang #79 1+2 2+3 3+4 喝完都死了 5+6 6+7 7+8 没事 ，确定不了吧

[igwen6w]

@ElmerZhang 看 11 楼

[tegusi]

1 楼的编码没看懂…一个编码矩阵有一行一列共有 15 个元素结果都是死亡，6 个小白鼠怎么能推断出最后的信息？

[Xs0ul]

@Samuelcc #73
按这个介绍，随机出了一个可行的解：
[[0, 0, 1, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 1, 0, 0],
[0, 0, 1, 0, 1, 0, 1, 0],
[1, 0, 0, 1, 0, 0, 1, 0],
[0, 0, 0, 1, 1, 1, 0, 0],
[1, 1, 0, 0, 1, 0, 0, 0]])

[alan7]

直接编号 1—6 的老鼠 喝 编号 1-6 的的水

[alan7]

@alan7 都没死，就是 7 8 的水有毒，如果老鼠死了，那就是对应编号的水有毒啊。。简单的事情，想那么复杂

[vermouth1995]

@alan7 死一只的时候呢

[MyouiSouth]

@vermouth1995 自己再痛饮一杯 （

[sujin190]

把瓶子编号 1 到 8，8 个瓶子 2 个有毒 2 只老鼠的话，应该每组应该用 6 只瓶子的水，可以用下边这种组合

A 1 2 3 4 5 6
B 3 4 5 6 7 8
C 1 2 3 6 7 8
D 2 3 4 5 6 7
E 1 2 4 5 7 8
F 1 3 4 5 6 8

经过测试，发下只有其中 5 组都死的情况下才能满足两只瓶子有毒的条件，组合方式分别为

A B C D E 组死 {2, 7}有毒
A B C D F 组死 {3, 6}有毒
A B C E F 组死 {8, 1}有毒
A B D E F 组死 {4, 5}有毒
A C D E F 组死 {1, 2}有毒
B C D E F 组死 {8, 7}有毒

不知道有没有覆盖到所有情况了，看条件测试时满足的

[MyouiSouth]

@chrisouta 但是是 8 瓶水 如果可以确保九宫格的其中一角不放水 应该是可以的吧..?

[foreverstandbyu]

10 人一组核酸检测的原理？？

[MyouiSouth]

@chrisouta 我傻了，如果是小对角好像也不行🧐

[nxforce]

11 楼最简单了，两两组合，8 个瓶子总共 4 组，花掉 4 只老鼠，可以确定哪两组是有毒的，用剩下 2 只老鼠，可以用排除法（划重点）确定哪两瓶有毒。

这个版本最理想的情况下，可以只花 4 只老鼠，就可以确定有毒的瓶子了。

[chrisouta]

@Xs0ul #85
验证通过，恭喜发现第一个解，没想到行重都是 3，五只老鼠不知道能搜索到吗？

[aureole999]

@joyhub2140 要求单次

[idyu]

@Xs0ul #85
不行，很多组合会导致六个全死，6 和 124578，5 和 123678，4 和 123678，3 和 124578

[sujin190]

@chrisouta #95 似乎 A1 的 4 没死的条件不满足，如果第一组的 13 和 23 都没死，第二组 13 和 23 死掉，4 没死，这种情况下似乎不能确定是第二组的 1 2 有毒，还是第二组的 3 和第一组的 4 有毒

[qaz168000]

AB,CD,EF,GH 4 只老鼠
死一只，那结果已经有了，就是对应的 2 瓶水
如果死两只，则拿出对应的两只老鼠的那 4 瓶水，比如 CD GH，还有 2 只老鼠
一只给 C，一只给 G，都死那就是 C 和 G 有毒，
C 死，G 活，有毒的是 CH
C 活，G 死，有毒的是 DG

[hm20062006ok]

@qaz168000 单次检验