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

[eroko]

这题应该怎么算？

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

[cslive]

8 瓶水 6 个老鼠，2 瓶有毒，还要算法？？？？，直接试简单粗暴，试到老鼠死

[chrisouta]

输入 pattern
[[1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0]
[0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0]
[0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 1]
[0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1]]
#85 矩阵得到的老鼠死亡 pattern
[[0 1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1]
[1 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 0 0 1 0 0 1 1 0]
[0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1 0 1]
[1 1 1 1 1 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 1]
[0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0]
[1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0]]
死亡 pattern 是没有重复列的，需要验证的情况可以查看输入 pattern 的对应列

[Jealee]

123 234 345 456 567 678
这样不知道行不行

[shyrock]

@Xs0ul #85 这个测试矩阵怎么构造的？

[j717273419]

@touchwithe 不对吧，全死了 a 是有毒的，但是怎么确定另外一个是哪瓶有毒呢？你已经把 a 污染了所有的样本了。

[mxT52CRuqR6o5]

信息论的题目，本质就是设计一种编码

[liprais]

这个问题一楼就解答完了你们到底在吵啥

[lff0305]

#85 正解，写个程序验证下是正确的

[qaz168000]

@hm20062006ok 这个单次校验应该是指每只老鼠只能用 1 次吧？要没有这个限制，就直接两只一瓶一瓶来，试到死就有结果了...

[idyu]

@Xs0ul 抱歉回错人了，你的是对的

[NEVERCODE]

很简单：

1. 假设，平均下来，4 瓶水，3 只鼠，那么我们可以用红框里的解法，A 小鼠喝 12 水，B 小鼠和 13 水，C 小鼠喝 4 水，死的是一只 A 小鼠，则 2 号有毒；一只 B 小鼠则 3 号有毒； A 小鼠和 B 小鼠同时死亡，则 1 水有毒； 4 小鼠死亡则 4 号有毒
2. 但实际上，是两瓶未知的水，用同样的方法，可以得出红框外的结论，A 小鼠喝 12 水，B 小鼠喝 13 水，C 小鼠喝 45 水，D 小鼠喝 56 水，剩下的 EF 小鼠各一杯，用上面的方法可以推断

i.loli.net/2021/04/21/AdZLxobNhHjJenB.png

然后就可以得出哪杯水有毒了！

[NEVERCODE]

@NEVERCODE 上面第 2 写错了一点：

2. 但实际上，是两瓶未知的水，用同样的方法，可以得出红框外的结论，A 小鼠喝 12 水，B 小鼠喝 13 水，C 小鼠喝 45 水，D 小鼠喝 46 水，剩下的两杯水 EF 小鼠各一杯，用 1 的方法可以推断

[idyu]

只要死亡组的二进制或运算之后的值在所有组或运算里是唯一的就可以了，PHP 代码：

$r = []; //分配方案
$s = []; //所有可能发生的死亡组合数组
for($i=0b00000001;$i<=0b11111111;$i++){
if(in_array($i,$s)) continue;
$isok = true;
$ts = [$i]; //当前组可能发生的死亡组合数组
foreach($r as $n){ //遍历已有分配方案，是否有重复的死亡组合
$t = $n|$i; //死亡或运算
$ts[] = $t; //死亡放到当前数组
if(in_array($t,$s)) { //如果死亡组合已经存在 s 里，无效
$isok = false;
break;
}
}
if($isok){
$s = array_unique(array_merge($s,$ts)); //如果当前组有效，当前组的死亡数组放到总数组
$r[] = $i;
}
}
var_dump($r);
试了下应该是可以的

[idyu]

@idyu

可行的结果之一：
00100000
00101010
00110100
00111111
10000000
11000001

[zhyl]

@elfive 这样两瓶有毒的话可能会死 4 只。。

[lff0305]

受 85 楼启发写了个程序，其实远不止一组解，比如
六只老鼠
m0=00000111
m1=00011001
m2=00101010
m3=00110100
m4=01001100
m5=01010010

毒药在
01 的时候，0125 死
02 的时候 0134 死，等等等，0<=i<j<=7, 每种(i,j)的组合死法都是不同的，就可以知道那两瓶是毒药，

类似的还有

00000111
00011001
00101010
00110100
01001100
10100001

00000111
00011001
00101010
00110100
01010010
10100001

[lafree317]

循环一次....死了就有毒 两只耗子就够了 把剩下的放了吧

[jiorix]

想问一下为什么一只老鼠怼一瓶水不行？每瓶水和每只老鼠都是只参与一次啊～～

[jiorix]

@jiorix 哦哦，死一只老鼠剩下的 2 瓶水就……

[err1y]

感觉跟汉明码有点像，水按数字编号，12345678，老鼠用 abcdef 编号


a 喝 12 混合水，b 喝 34 混合，c 喝 56，d 喝 78 。
如果 abcd 中只有一个死，则死的那个喝的两个水就都是毒。
如果 abcd 中有两个死了，用 ef 两只老鼠分别去喝死的那两只老鼠喝的其中一杯，如果中了，则喝的是毒，否则没喝的那瓶是毒

[hahaayaoyaoyao]


[hahaayaoyaoyao]

@hahaayaoyaoyao 两两组合, 组成 6 瓶水

[evilStart]

一楼就解答完了为什么能够这么多层楼？

[Godykc]

谁能解释下题干强调的单次是啥意思？

按照一楼思路，总共 64 种水的组合，6 只鼠怎么实现“单次”喝完？

[looooooong]

@Godykc 可以理解为 1 小时毒发死亡，你也只有 1 小时时间

[tianxia]

@err1y 单次出结果

[snw]

@NEVERCODE
你这种方法区分不出(1,2)有毒和(1,3)有毒这两种情况，因为都是 AB 鼠死。

[snw]

@liprais
@evilStart
因为一楼的答案是错的啊。

@lafree317
要求单次出结果。

@hahaayaoyaoyao
喝 AB 的老鼠和喝 CD 的老鼠死了，请问哪两瓶是毒药？

[snw]

@Jealee
看起来没问题，而且是这楼目前最优美的解答（和 85 楼是等价的）。

[GTim]

@touchwithe lihai

[Xs0ul]

@snw #129 这个 24 和 34 的结果一样的。建议大家代码验证，自己想很容易漏


@shyrock #104 我是单纯随机然后验证的，其他人可能有更好的办法

[snw]

@Jealee
不对，这种排列方法无法区分(1,3)和(2,3)两种情况。

[GTim]

@touchwithe 你的答案挺好的呀 ，在于启发

1. 8 瓶中先拿三两瓶 比如 A，B, C
2. 将 C 往剩余的 5 瓶中都倒入，拿给老鼠喝
3. 如果全死，那么说明 C 有毒，A，B 中有一瓶有毒，剩下一只老鼠，嘿嘿，随便喂一瓶就知道结果了
4. 如果死一只，那么，C 没毒，哪瓶对应的老鼠死了就是哪瓶，A，B 中有一瓶有毒，剩下一只老鼠，嘿嘿，随便喂一瓶就知道结果了
5. 死两只，那么就是哪瓶死了是哪瓶
6. 什么，一只都没死，不可能的事。

[GTim]

@GTim 的确错了，我的逻辑也错了

[Xs0ul]

@idyu #114 你这组解好像有点问题，比如区分不了 23 和 38 的情况，都是只有第 5 只老鼠不会死

[dangyuluo]

没说多少个杯子

[NEVERCODE]

@snw 确实，当时没想到。那就组成 12，13，34，35，四杯水，然后 6 7 各一杯，正好六只老鼠，然后根据死亡情况再去排除 8 的水

[JustLookBy]

1 楼就是说了个理论，结果是行不通的。

@lff0305 #116
@Xs0ul #85
俩楼给出了正确解，至于怎么有逻辑的推出这个解 感觉还没答案。。
我写了个在线验证答案的简单页面，同学们有需要可以来验证下自己答案先。。。一堆给了错误答案的

https://abiudoit.github.io/algorithmTest/checkPoison.html

[lff0305]

@JustLookBy
没那么复杂，穷举+验证就行了

本来最开始用的是 6 个循环每个循环 1~255 发现时间不可接受（ 255^6)
后来看 85 楼的结果行 1 的个数是相同的（也就是老鼠喝相同数目的瓶子）

所以就做了个假设：老鼠喝的瓶子的数目是相同的
这样循环的次数就少多了

每个老鼠喝一瓶 无解
每个老鼠喝两瓶 无解
每个老鼠喝三瓶 很多解

至于每个老鼠喝不同的数目的瓶子，没实验，也无法证明一定不存在解

[Xs0ul]

@lff0305 #139 有一点，很多解实际是等价的，交换行列实际上相当于交换瓶子或者老鼠的顺序，本质上没有差别。所以我比较好奇除了全是 3 瓶以外的解

[yucongo]

@JustLookBy 大佬这个程序 https://abiudoit.github.io/algorithmTest/checkPoison.html 给的反馈啥意思？
例如（第 5 号老鼠不想喝药啦:)），
10000000
01000000
00100000
00010000
00001000
00000000

反馈说：失败,毒药 0,1 和 0,2 存在相同死亡情况: 000000
毒药是 5,6,7 中的两瓶时，所有老鼠都安全吧

[JustLookBy]

@yucongo 这个意思是，当毒药是 0 号 1 号 或者毒药是 0 号，2 号的时候，老鼠的死亡都是 000000，既都没有老鼠死亡。
老鼠死亡结果必须和毒药结果 是 [多对一] 或 [一对一] 的关系，否则不能通过老鼠死亡情况推出哪俩瓶有毒

[JustLookBy]

@yucongo 你说的没错。。对你们来说应该是 5 6 和 5 7， 不是 0 1 和 0 2 。 消息提示的有点问题

[snw]

@NEVERCODE
依然不行。现在(12)

[snw]

@NEVERCODE
依然不行。现在喝(12)和(13)的两只老鼠死了，你无法判断是(1,8)有毒还是(1,2)有毒。

[hahaayaoyaoyao]

https://github.com/ZTFtrue/My-note/blob/main/%E8%80%81%E9%BC%A0%E8%AF%95%E6%AF%92%E9%97%AE%E9%A2%98.md