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 的对应列

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

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

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.

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

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

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