V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
eroko
V2EX  ›  问与答

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

  •  
  •   eroko · 2021-04-20 18:58:15 +08:00 · 11437 次点击
    这是一个创建于 1291 天前的主题,其中的信息可能已经有所发展或是发生改变。
    这题应该怎么算?
    第 1 条附言  ·  2021-04-20 19:45:16 +08:00

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

    146 条回复    2021-04-24 22:36:57 +08:00
    1  2  
    noe132
        1
    noe132  
       2021-04-20 19:12:13 +08:00   ❤️ 26
    将 2 瓶水两两组合混合一共 8x8=64 种状态,编码为 0-63,每种状态代表任意 2 瓶水的 combo,6 只耗子=6bit,每只耗子毒死 /存货代表 1bit,6bit 一共 2^6 = 64 种状态,将上面组合的 64 种状态再根据每一种状态对应二进制位混合出 6 瓶水,给 6 只耗子喝,根据最后结果就可以推算出来 8 瓶水哪 2 瓶有毒了。
    Samuelcc
        2
    Samuelcc  
       2021-04-20 19:13:23 +08:00 via Android
    详细说下单次检验是什么意思?是不能看任何前置的检验结果吗?
    感觉思路应该和混合水缩小范围相关
    touchwithe
        3
    touchwithe  
       2021-04-20 19:16:05 +08:00 via iPhone   ❤️ 5
    1. 拿出一瓶水,记为 A,向剩余 7 瓶中都倒入一点。
    2. 7 中拿出 6 瓶,剩余一瓶记为 B 。
    3. 6 瓶水分别喂 6 只耗子。
    可能的结果:
    死一只,对应喝的水有毒,B 有毒。
    死两只,对应喝的水有毒。
    全死了,A 有毒。
    l00t
        4
    l00t  
       2021-04-20 19:18:17 +08:00   ❤️ 3
    一次就检验出来,那就不能等待之前的喝药结果了。

    没仔细验算过,你试试这个思路可行否:

    将 8 按 2 进制拆出来,得到 8 个三位二进制数。看每个位上,是 0 的派一只老鼠,是 1 的派一只老鼠,这样三位三个 01,正好 6 只。喝完后看结果,根据死的老鼠找出毒药。
    LZSZ
        5
    LZSZ  
       2021-04-20 19:22:10 +08:00
    几瓶混在一起试错
    touchwithe
        6
    touchwithe  
       2021-04-20 19:22:20 +08:00 via iPhone
    @touchwithe #3 想错了,不对。还是一楼的方法好!
    eroko
        7
    eroko  
    OP
       2021-04-20 19:22:24 +08:00
    @Samuelcc 单次检验就是喂一次就能得到结果
    zxCoder
        8
    zxCoder  
       2021-04-20 19:36:05 +08:00   ❤️ 1
    @noe132 能再详细解释一下吗大佬

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

    这段读得有点费劲。。。
    xdeng
        9
    xdeng  
       2021-04-20 19:36:09 +08:00   ❤️ 1
    @eroko 单次检验就是喂一次就能得到结果 那不就是 6+2=8 吗。。。拿六瓶喂六只 都没死 那就是剩下的 2 瓶有毒吗?死了对应的那瓶就有毒?是我理解错了吗?
    fisherman0459
        10
    fisherman0459  
       2021-04-20 19:37:42 +08:00   ❤️ 1
    @xdeng 如果六只里面只死了一只呢?
    qsmd42
        11
    qsmd42  
       2021-04-20 19:38:34 +08:00   ❤️ 8
    1 2 3 4 5 6 7 8
    V V V V V V
    A B C D E F

    这样?
    xinh
        12
    xinh  
       2021-04-20 19:42:32 +08:00 via iPhone
    2 楼的那种二进制解法,在李永乐的视频里学的,有一期讲这个数学
    xdeng
        13
    xdeng  
       2021-04-20 19:53:29 +08:00
    @fisherman0459 啊这。。。一楼字多一楼肯定对 哈哈哈
    xdeng
        14
    xdeng  
       2021-04-20 19:54:28 +08:00
    @xinh +1 但好像说的不是耗子毒药
    yigecaiji
        15
    yigecaiji  
       2021-04-20 19:58:55 +08:00 via Android
    @xinh 能给个视频名字或链接吗?有时间一定好好学一下
    yxt
        16
    yxt  
       2021-04-20 20:15:46 +08:00   ❤️ 1
    @noe132 混出 64 瓶水, 现在有 2*8=16 瓶水有毒了, 6 只耗子能找的是 64 瓶水里一瓶有毒吧?
    AngryPanda
        17
    AngryPanda  
       2021-04-20 20:22:07 +08:00 via iPhone
    2 只耗子🐭就检验出来了
    hm20062006ok
        18
    hm20062006ok  
       2021-04-20 20:24:02 +08:00
    @noe132 "将 2 瓶水两两组合混合一共 8x8=64 种状态" 不是只有 28 瓶(两两混合后的)+ 8 瓶(原始的) = 36 种状态吗?
    AndyVerne
        19
    AndyVerne  
       2021-04-20 20:34:26 +08:00
    8 瓶水,分四组(一组两瓶),一只老鼠喝一组如果
    AndyVerne
        20
    AndyVerne  
       2021-04-20 20:37:45 +08:00
    @AndyVerne 8 瓶水,分四组(一组两瓶),一只老鼠喝一组,还有 2 只老鼠多出来,
    如果 3 组没事,没事,那么有毒的一组就包括那两瓶有毒的水
    如果 2 组出事,拿出两组的其中各一瓶,用多出的两只老鼠,根据情况对应排除,就能得到结果
    dethan
        21
    dethan  
       2021-04-20 20:56:41 +08:00 via Android
    好残忍,鼠鼠那么可爱。。
    xdeng
        22
    xdeng  
       2021-04-20 20:58:16 +08:00   ❤️ 1
    @yigecaiji
    @xinh 我说错了讲的就是老鼠毒药
    AndyVerne
        23
    AndyVerne  
       2021-04-20 21:01:26 +08:00
    @noe132 你这个混合方法有问题,因为一瓶水,被混合后不能重置为初始状态(相当于被污染了)
    suisetai
        24
    suisetai  
       2021-04-20 21:07:18 +08:00 via iPhone   ❤️ 10
    拿一只老鼠一瓶瓶喂 死了就换下一只... 顶多用两只 当然 撑死不算
    ro2020
        25
    ro2020  
       2021-04-20 21:33:39 +08:00
    4 楼方法是正确的
    Vegetable
        26
    Vegetable  
       2021-04-20 21:47:48 +08:00
    @suisetai 真他妈是个天才
    akira
        27
    akira  
       2021-04-20 21:50:48 +08:00
    遇到这种问题 一律用 2 进制的思路去考虑 肯定对的
    looooooong
        28
    looooooong  
       2021-04-20 22:06:21 +08:00 via iPhone
    @ro2020
    @l00t 按照我对 4 楼方法的理解 假如六只全死了,到底是 001,110 还是 100,011 呢 当然类似的还有 101,010 这种的
    ro2020
        29
    ro2020  
       2021-04-20 22:20:58 +08:00
    @looooooong 是的,我刚才在算的时候也发现了问题,这个方法不对
    xinh
        30
    xinh  
       2021-04-20 23:42:08 +08:00 via iPhone
    chrisouta
        31
    chrisouta  
       2021-04-20 23:42:21 +08:00
    可以把所有毒药可能的组合写到一个二进制矩阵 S 中,每行代表一种组合,一共有 C(8,2)行,8 列。相应的老鼠编码二进制矩阵记为 M(8,k), 每一列代表一只老鼠的喝药方案, 六只老鼠 k=6 。有 Binary(SM) = X,这里 X 也是二进制矩阵(大于零的元素视为 1),可以为一个二进制 BCD 矩阵(类似上面李永乐老师的 100 瓶毒药编码矩阵)。只要解出来 M 矩阵就可以找出编码方式。上面李永乐老师的例子里 S 为单位矩阵,所以老鼠编码矩阵就等于 BCD 矩阵,不需要解,这个可能要稍微麻烦点了。
    Tumblr
        32
    Tumblr  
       2021-04-21 00:12:38 +08:00
    @xdeng #22 我看到题目也是第一时间想到了李永乐老师的这个视频!
    hm20062006ok
        33
    hm20062006ok  
       2021-04-21 00:25:05 +08:00
    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
        34
    noe132  
       2021-04-21 00:38:11 +08:00
    @hm20062006ok 一开始我也是这么想的。但是毒药是或运算,2 瓶只要有 1 瓶是毒药,混合出来就都是毒药了。实际上按照这个逻辑,应该检验 8 瓶里面哪 6 瓶不是毒药
    hm20062006ok
        35
    hm20062006ok  
       2021-04-21 00:50:45 +08:00
    @noe132 是的, 想错了
    Elethom
        36
    Elethom  
       2021-04-21 01:00:07 +08:00 via iPhone
    其实五只就够了,这个问题一分钟答不上来的建议转行,这智商不适合做技术。

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

    再进阶一步:m 维空间的一个西瓜切 n 刀可以分成多少块?( m > 3,n > m )求通解。
    chrisouta
        37
    chrisouta  
       2021-04-21 01:06:33 +08:00
    @Elethom 几只当然简单,复杂的是怎么设计哪只老鼠喝哪几瓶
    snw
        38
    snw  
       2021-04-21 02:49:15 +08:00 via Android   ❤️ 1
    @Elethom
    两两混合成 28 瓶是吧?我现在告诉你你的 5 只老鼠全死了,请问你找出来哪两瓶有毒了吗?

    不要把 1 瓶毒药的解法想当然地拓展到 2 瓶毒药。
    snw
        39
    snw  
       2021-04-21 03:49:33 +08:00 via Android
    顺带一提,这个链接提出的解法也是不对的。
    blog.csdn.net/kingoverthecloud/article/details/4068[去掉此方括号]6129

    反例:无法区分(000, 110)为毒药与(010, 100)为毒药这两种情况。
    Elethom
        40
    Elethom  
       2021-04-21 06:04:06 +08:00 via iPhone
    @snw
    一瓶毒只要 log2(n) 也就是三个就够了,当然没那么简单。
    Elethom
        41
    Elethom  
       2021-04-21 06:43:37 +08:00 via iPhone
    @snw
    两瓶毒的情况,应该是对半分的。ABCD 、EFGH 、ABEF 、CDGH 、ACEG 、BDFH 这样子,可以理解为一个西瓜切三刀(就是我上面那个比喻),扩展到无限维度就可以解决更多瓶子的问题。上面我说五瓶确实是草率了,我道歉。

    写了一段代码验证:
    ( Swift 的编译检查不怎么待见 bitwise calculation 的样子,所以写成 Int 了,见谅)
    https://gist.github.com/Elethom/e31af1a9f576d150aa691c5468bed379
    tianxia
        42
    tianxia  
       2021-04-21 06:44:30 +08:00 via Android   ❤️ 10
    不需要什么算法,直接给 6 只耗子分别喂 6 瓶水,就保证单次检验出结果,不信可以尝试
    Mutoo
        43
    Mutoo  
       2021-04-21 06:54:43 +08:00
    @tianxia 是呀
    6 只都没事,剩下两瓶有毒
    5 只没事,1 只喝的是毒,剩下一瓶有毒
    4 只没事,2 只喝的是毒。
    根本不需要什么算法。
    tianxia
        44
    tianxia  
       2021-04-21 06:54:59 +08:00 via Android
    @Elethom 会导致毒药剂量不够,毒不死
    Elethom
        45
    Elethom  
       2021-04-21 06:55:51 +08:00 via iPhone
    @Mutoo
    剩下的是两瓶。
    tianxia
        46
    tianxia  
       2021-04-21 07:00:02 +08:00 via Android
    @Elethom 实际给你操作,保证一次出结果
    Mutoo
        47
    Mutoo  
       2021-04-21 07:00:12 +08:00
    @Elethom 对哦,走神了
    chrisouta
        48
    chrisouta  
       2021-04-21 07:05:06 +08:00   ❤️ 3
    https://en.wikipedia.org/wiki/Group_testing
    果然深似海,学到了很多,感谢楼主的问题。
    现有的理论还没有保证最优的算法,问题确实需要对矩阵进行搜索,wiki 里提到了几种搜索方法可以参考。
    甚至还有老鼠有概率死有概率不死的扩展,更复杂了🐶
    Elethom
        49
    Elethom  
       2021-04-21 07:17:46 +08:00
    #41 是我傻逼了。下界是 5 没错但是重新算了下上界还要再高一点。
    Elethom
        50
    Elethom  
       2021-04-21 07:19:01 +08:00
    @Elethom 大概在 log(2, n) * 2 * log(2, n/2)
    chrisouta
        51
    chrisouta  
       2021-04-21 07:33:40 +08:00
    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
        52
    Elethom  
       2021-04-21 07:34:23 +08:00 via iPhone
    @chrisouta
    的确比看起来更复杂。 😭
    elfive
        53
    elfive  
       2021-04-21 07:38:17 +08:00 via iPhone   ❤️ 5
    8 瓶水放到 9 宫格里,每行每列取样混在一起,正好 3 行 3 列,6 只耗子一次性喝混出来的一瓶,就可以了。

    这就是二维的奇偶校验。
    chrisouta
        54
    chrisouta  
       2021-04-21 07:55:48 +08:00
    #53 两瓶毒在对角上无法区分在主对角还是次对角吧。这里的加法运算毕竟不是模二加,是直接或运算,跟奇偶校验应该不同。
    popil1987
        55
    popil1987  
       2021-04-21 08:40:48 +08:00
    按照一楼的解法:8 瓶里 2 瓶有毒共 28 种组合(状态),那么 5 只老鼠可以表示 32 种状态就可以了吧,是不是能让一只老鼠去做电击实验?
    SlipStupig
        56
    SlipStupig  
       2021-04-21 10:48:36 +08:00
    @suisetai 万一老鼠都变异了毒不死怎么办呢。。
    palfortime
        57
    palfortime  
       2021-04-21 11:18:28 +08:00 via Android
    @noe132 #1 这种二进制编码的方案只能找 64 瓶里只有 1 瓶有毒的情况吧,混合出来的 64 瓶远远不只 1 瓶有毒。多瓶叠加在一起,无法用 6 只老鼠来找出吧。
    没有想到单次校验的。
    我的想法是 8 瓶分成 2 批,再用这种位编码的方式来找出每组里有毒的。具体会产生两种情况:
    2 批都有死或者都没有死,这样用位编码方式来算,用 4 只来试就可以。
    另外一种情况就是只有 1 批有死。这种情况有分为两种子情况:1. 没死的那批,00 是有毒的。2. 2 瓶有毒都在 1 批。
    针对子情况 1,找没有死的去喝 00,挂了就出结果。没有挂的话,那么现在还活着的还有 4 只,4 只对应有毒的那批的 4 瓶。那么结果也可以出来。
    dicc
        58
    dicc  
       2021-04-21 11:22:32 +08:00   ❤️ 4
    @Elethom #45 剩下两瓶,一有一无毒,你再喝一瓶
    nieyujiang
        59
    nieyujiang  
       2021-04-21 11:27:52 +08:00   ❤️ 3
    六个老鼠一只一瓶,面试官再喝一瓶.最后一瓶自己的.
    man9820
        60
    man9820  
       2021-04-21 11:34:24 +08:00 via iPhone
    @suisetai 他要一次性,大概意思是同时进行,要不方式太多了
    tinytoadd
        61
    tinytoadd  
       2021-04-21 11:37:59 +08:00 via Android
    @tianxia #42 这个有点问题,6 瓶里有一瓶有毒,那么无法 判断剩下的两瓶里哪一瓶有毒
    sujin190
        62
    sujin190  
       2021-04-21 11:42:49 +08:00
    这不就是二分法查找么,不很简单么,也需要讨论的这么复杂么。。。
    bk201
        63
    bk201  
       2021-04-21 11:50:23 +08:00
    @nieyujiang 你自己不用喝,结果就出来了呀
    cking
        64
    cking  
       2021-04-21 11:52:37 +08:00
    随便拿一瓶 给老鼠喝 然后把老鼠弄死 告知实验结果 这瓶有毒 然后这题结束 因为还有一瓶有毒的 肯定不会尝试 所以这题一次就结果了
    snw
        65
    snw  
       2021-04-21 12:21:48 +08:00 via Android
    @sujin190
    你试试?
    iwasthere
        66
    iwasthere  
       2021-04-21 12:30:18 +08:00 via iPhone
    数学渣,评论看的懵逼
    sujin190
        67
    sujin190  
       2021-04-21 12:42:04 +08:00
    @snw #65 8 瓶水分成 4 瓶两堆,给两只老鼠喝

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

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

    这不简单么,有啥好讨论的
    Dvel
        68
    Dvel  
       2021-04-21 12:42:58 +08:00
    这题目出错了,8-2=6,这题不用算法,直接怼就行,应该是更多的瓶子或更少的老鼠。
    Dvel
        69
    Dvel  
       2021-04-21 12:44:55 +08:00
    @Dvel #68 说错了,死一只的话就检测不出来了。
    tiramice
        70
    tiramice  
       2021-04-21 12:45:38 +08:00
    @sujin190 要求单次检验出结果,你这检验几次了?
    sujin190
        71
    sujin190  
       2021-04-21 12:47:34 +08:00
    @tiramice #70 好吧,单次检测时这个意思啊。。我错了
    cyrbuzz
        72
    cyrbuzz  
       2021-04-21 13:28:09 +08:00
    分成两组 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
        73
    Samuelcc  
       2021-04-21 13:33:33 +08:00   ❤️ 1
    搜了一下,感觉应该是找到正解了。这道题目是 group testing 问题中的 non-adaptive 情况,应该是这类型题目最难的一种变体。解法是构建 t-separable 的矩阵进行测试,测试后将结果还原。
    这篇文章有比较详细的论述,有兴趣的可以看看 https://people.cs.umass.edu/~arya/courses/690T/lecture14.pdf
    rationa1cuzz
        74
    rationa1cuzz  
       2021-04-21 13:41:43 +08:00
    @cyrbuzz 两组 X 、Y 假设都在 X 组 A 鼠(13) B 鼠(23) C 鼠(12) 假设 12 都是毒药 ABC 都死 假设 13 都是毒药 ABC 都死
    Ritr
        75
    Ritr  
       2021-04-21 13:47:09 +08:00
    @suisetai 绝了
    ElmerZhang
        76
    ElmerZhang  
       2021-04-21 14:12:56 +08:00
    假设 8 瓶水为 1-8,第一轮先给一只老鼠喝 1+2+3,另一只老鼠喝 4+5+6 。
    假如某一只老鼠死掉,最多再用两只老鼠即可找出其中有毒的水。剩下的 7 、8 再用一只就可以找出有毒的水。
    假如第一轮都没死,就是 7 、8 有毒。
    ElmerZhang
        77
    ElmerZhang  
       2021-04-21 14:13:49 +08:00
    看错题目,要求单次,我再想想
    cyrbuzz
        78
    cyrbuzz  
       2021-04-21 14:17:35 +08:00
    @rationa1cuzz 额,说的是= =,少一组验证。
    ElmerZhang
        79
    ElmerZhang  
       2021-04-21 14:21:59 +08:00
    仍然编号 1-8,6 只老鼠分别喝 1+2 2+3 3+4 5+6 6+7 7+8 。
    想了一些用例,应该是可解的。
    wuxinling
        80
    wuxinling  
       2021-04-21 14:32:25 +08:00
    如果水多一些还需要好好考虑,
    Xs0ul
        81
    Xs0ul  
       2021-04-21 14:44:23 +08:00
    @ElmerZhang #79 13 和 23 是一样的,都是前三只都死
    Otho
        82
    Otho  
       2021-04-21 14:52:52 +08:00
    @ElmerZhang #79 1+2 2+3 3+4 喝完都死了 5+6 6+7 7+8 没事 ,确定不了吧
    igwen6w
        83
    igwen6w  
       2021-04-21 14:55:58 +08:00
    @ElmerZhang 看 11 楼
    tegusi
        84
    tegusi  
       2021-04-21 15:10:30 +08:00
    1 楼的编码没看懂…一个编码矩阵有一行一列共有 15 个元素结果都是死亡,6 个小白鼠怎么能推断出最后的信息?
    Xs0ul
        85
    Xs0ul  
       2021-04-21 15:15:01 +08:00   ❤️ 4
    @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
        86
    alan7  
       2021-04-21 15:20:59 +08:00
    直接编号 1—6 的老鼠 喝 编号 1-6 的的水
    alan7
        87
    alan7  
       2021-04-21 15:22:22 +08:00
    @alan7 都没死,就是 7 8 的水有毒,如果老鼠死了,那就是对应编号的水有毒啊。。简单的事情,想那么复杂
    vermouth1995
        88
    vermouth1995  
       2021-04-21 15:25:20 +08:00
    @alan7 死一只的时候呢
    MyouiSouth
        89
    MyouiSouth  
       2021-04-21 15:37:37 +08:00
    @vermouth1995 自己再痛饮一杯 (
    sujin190
        90
    sujin190  
       2021-04-21 15:41:43 +08:00
    把瓶子编号 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
        91
    MyouiSouth  
       2021-04-21 15:43:49 +08:00
    @chrisouta 但是是 8 瓶水 如果可以确保九宫格的其中一角不放水 应该是可以的吧..?
    foreverstandbyu
        92
    foreverstandbyu  
       2021-04-21 15:49:54 +08:00
    10 人一组核酸检测的原理??
    MyouiSouth
        93
    MyouiSouth  
       2021-04-21 15:52:32 +08:00
    @chrisouta 我傻了,如果是小对角好像也不行🧐
    joyhub2140
        94
    joyhub2140  
       2021-04-21 15:56:54 +08:00
    11 楼最简单了,两两组合,8 个瓶子总共 4 组,花掉 4 只老鼠,可以确定哪两组是有毒的,用剩下 2 只老鼠,可以用排除法(划重点)确定哪两瓶有毒。

    这个版本最理想的情况下,可以只花 4 只老鼠,就可以确定有毒的瓶子了。
    chrisouta
        95
    chrisouta  
       2021-04-21 16:03:50 +08:00
    @Xs0ul #85
    验证通过,恭喜发现第一个解,没想到行重都是 3,五只老鼠不知道能搜索到吗?
    aureole999
        96
    aureole999  
       2021-04-21 16:16:23 +08:00
    @joyhub2140 要求单次
    idyu
        97
    idyu  
       2021-04-21 16:21:07 +08:00
    @Xs0ul #85
    不行,很多组合会导致六个全死,6 和 124578,5 和 123678,4 和 123678,3 和 124578
    sujin190
        98
    sujin190  
       2021-04-21 16:21:48 +08:00
    @chrisouta #95 似乎 A1 的 4 没死的条件不满足,如果第一组的 13 和 23 都没死,第二组 13 和 23 死掉,4 没死,这种情况下似乎不能确定是第二组的 1 2 有毒,还是第二组的 3 和第一组的 4 有毒
    qaz168000
        99
    qaz168000  
       2021-04-21 16:26:42 +08:00
    AB,CD,EF,GH 4 只老鼠
    死一只,那结果已经有了,就是对应的 2 瓶水
    如果死两只,则拿出对应的两只老鼠的那 4 瓶水,比如 CD GH,还有 2 只老鼠
    一只给 C,一只给 G,都死那就是 C 和 G 有毒,
    C 死,G 活,有毒的是 CH
    C 活,G 死,有毒的是 DG
    hm20062006ok
        100
    hm20062006ok  
       2021-04-21 16:27:47 +08:00
    @qaz168000 单次检验
    1  2  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2522 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 10:22 · PVG 18:22 · LAX 03:22 · JFK 06:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.