【趣题分享】等价命题转换与策略的优化——魔法毒药解析

这个问题的原版早年在网络上被称为老鼠验毒或者囚犯毒酒问题，为了避免解答者利用验毒的时间差，本题改为老鼠固定在当天夜晚0点死亡。

本题经过少量改编后，它的难度与复杂程度是初始问题所不能比拟的。但是在解答三个问题前，首先还是需要理解初始问题的答案。

二进制并不是因为方便而使用的工具，而是根据实验结果等价转化得到的形式。

理解上述以后，我们可以尝试解决正式问题。

第一题显然最为复杂，所以可以先分析后面两题。

第二题是在8瓶水中找2瓶毒，我们先从实验结果入手。显然实验结果还是一串二进制编码，然后尝试寻找它的数学本质。因为有两瓶毒药使喝到的老鼠死亡，所以最终所能观察到的结果是两瓶毒药对应的死亡老鼠的并集，也就是两个二进制编码的并集形式。所以为了将这个混合的二进制编码还原为两瓶毒药的二进制编码。我们需要让

所有二进制编码中任意两两的并集都不同，这也是这个问题的等价形式。

理解这点后，如果使用编程方法，就可以很容易得到这个问题的解。

此题的最优解是用6只老鼠，我们这里提供一种构造方法：

将老鼠分为ABC共3类，每类两只，即A1A2,B1B2,C1C2。

接下来三类老鼠各取一只进行组合，但要求是每只老鼠不能和已组合过的老鼠再次组合。同时每只老鼠都要与其他类的所有老鼠都进行过组合。

那么很容易得到四个组合A1B1C1，A1B2C2，A2B1C2，A2B2C1。

现在用这三个类加上四个组合的老鼠分别对应上7瓶水，而第8瓶不让任何老鼠喝即可。

这样的话，任意两个组合的并集都是不同的。

假设只用5只老鼠就可以在8瓶水中找到2瓶毒药。那问题可以等价为有8个5位的2进制串，并且这些二进制编码任意两两的并都不同。

如果有两个2进制编码相同，那么其他任意一个二进制编码与它们的并都是相同的。所以任意2个2进制编码都是不同的。

而C(2,8)=28，2^5=32，意味着所有5位2进制编码中我们最多只能剔除4个。

考虑以下并集为11111的二进制编码组合。

11111∪任意二进制编码=11111，

11110∪00001=11111，

11101∪00010=11111，

11011∪00100=11111，

10111∪01000=11111，

01111∪10000=11111。

显然11111本身必须剔除，而剩下5组二进制串中，最多保留一组，其余四组每组至少剔除一个。此时剔除的数量已经超过了极限，因此原命题无法成立。

第三题是在5瓶水中找到毒药和解药，此时老鼠死亡代表着老鼠喝了毒药而没喝解药，如果毒药的二进制编码为p，解药的二进制编码为q，那么观测结果为p且非q的二进制编码。

所以为了将这个混合的二进制编码还原为毒药和解药。我们需要让任意两个二进制编码进行上述运算后的结果都是不同的。设bij=ai∩!aj(0≤i,j≤5,i≠j),所有bij的集合{B}的元素个数应该为C(2,5)*2 = 20个。

此题的最优解是用6只老鼠，考虑对称性不难获得一组结果：

000011，010110，001101，111000，100111。

假设只用5只老鼠就可以在5瓶水中找到1瓶毒药和1瓶解药。那问题可以等价为有5个5位的2进制串，并且这些二进制编码任意两两进行a∩!b后的运算结果都是不同的。

如果有两个2进制编码相同，假设它们是a和b，那么a∩!b = b∩!a，这是命题所不允许的，所以任意2个2进制编码都是不同的。

如果有一个编码中存在5位是相同的，那么它作为解药时无法检测出任意一瓶毒药。

如果有一个编码中存在4位是相同的，那么它作为解药时检测毒药只有剩余1位有效，那么它最多只能检测2个编码。

如果有一个编码中存在3位是相同的，那么它作为解药时可区分开来的毒药编码只有剩余2位有效，那么它最多只能检测4个编码。

显然，我们一共需要5个编码，所以每个编码都必须存在3位是相同的。并且剩余2位在其他编码的位置都必须不相同。

不妨设其中一个编码是11100，那么必然存在一个编码是xxx00，不妨设其是11000（因为此时它和10100，01100等价，而且它不可能是11100），

11100

11000

xxx01

xxx10

xxx11

那么xxx11只有三种可能，10011（和01011等价）或00011或00111，

其中00011和00111都会使得前两个编码11100和11000重复，所以都不可能。

那么此时只剩下两种可能，

均不成立。

因此5位编码是无法使命题成立的。

在解决第一题前，首先考虑第一题和第二题的等价关系。从观测结果考虑，第一题结果是毒药二进制编码的交集，第二题结果是毒药二进制编码的并集。而有a∩b=!(!a∪!b)，即只要求得第二题的方案，然后让老鼠喝下方案中水的补集，便是第一题的方案。为了简化说理，以下关于第一题的解法都采用第二题两瓶水有毒的机制。

考虑10x10的正方形方阵，一共100个格子，每个格子放置一瓶水，然后在每行每列都布置1只老鼠，每只老鼠喝它所对应的行或列中的所有水。

列上的10只老鼠记为ai(0≤i≤9,i为整数)，行上的10只老鼠记为bj(0≤j≤9,j为整数)，方阵里的水记为Xij(0≤i,j≤9,i,j为整数)

两瓶毒药记为Xmn和Xpq。

每瓶水都会被这一行的和这一列的两只老鼠喝到，所以Xmn会被bm和an喝到，Xpq会被bp和aq喝到。因此bm，an，bp，aq会死亡，而死亡老鼠所在的那一行或列必然存在毒药，因此毒药的位置会被大致锁定。

毒药有两瓶，Xmn≠Xpq，所以m=p和n=q不会同时成立。假如有一组成立，不妨设m=p,此时毒药必然在bm行，又在an列和aq列。那么毒药只可能是Xmn和Xpq，这样就找出了两瓶毒药。

而当m≠p且n≠q时，毒药的位置就有两组可能。Xmn和Xpq或者Xpn和Xmq。这两种可能所造成老鼠死亡的情况是完全等同的。

此时就需要额外的老鼠来检验这两种可能。因为m+n≠m+q≠p+q，所以要区检验Xmn和Xmq哪瓶有毒，我们只需要让一只老鼠喝所有满足i+j=m+n（模10意义下）的水，让另一只老鼠喝所有i+j=m+q（模10意义下）的水，那么就可以根据老鼠的死亡情况判断哪瓶有毒。

（若喝了绿色格子的老鼠死亡则Xmn有毒，若喝了蓝色格子的老鼠死亡则Xmq有毒）

另外，因为我们无法预先知道哪两组情况需要我们区分，而实际上任意两瓶不在同一行且不在同一列的毒造成的后果都等效于对称的两瓶是毒所造成的后果。

因此我们可以对所有对角线都放置一只老鼠以检验所有可能性。那么这里需要10只老鼠。

而很自然的是，我们可以省去一条对角线不放置老鼠，这样若在对角线检验时没有老鼠死亡，便是该条对角线上存在毒药。

所以该方案一共使用10+10+9=29只老鼠。

对角线检验的本质是为了区分开任意一个矩形的两组对角。

那么实际上不需要让每只老鼠走一条对角线，只需要构造出一种检验方案，使得任意一个矩形框的两组对角所使用的老鼠的集合不同。

最少用5只老鼠就可以解决这个问题。

因此上述方案可以优化至20+5=25只老鼠。

在上面的方案中，我们让10只老鼠喝10行，10只老鼠喝10列。以此确定毒药在哪些行哪些列。但我们知道，如果是在10瓶水中找2瓶毒药，并不需要10只老鼠，实际只需要7只。同样的，我们要在10行中找到毒药在哪一行，也不需要10只老鼠。但是因为两瓶毒药有可能在同一行，这样的话相当于10行中只有一行有毒药。因此这个问题等价于在10瓶水中找到一瓶或者两瓶毒药。

而这又可以进一步等价转换为在11瓶水中找到2瓶毒药。

证明如下：如果要在n+1瓶水中找到2瓶毒药，那么我们可以取走一瓶，在剩下n瓶水中找到1或2瓶毒药。在剩下n瓶水中若是找到1瓶毒药，那么取走的那一瓶就是毒药。因此在n瓶水中找1或2瓶毒药就等价于在n+1瓶水中找2瓶毒药。

而要在11瓶水中找到2瓶毒药，最优解为使用8只老鼠，实际上，8只老鼠最多能在13瓶水中找到2瓶毒药。

下面展示一种使用8只老鼠在13瓶水中找2瓶毒药的方法：

将老鼠分为ABCD共4类，每类两只，即A1A2,B1B2,C1C2,D1D2。

接下来四类老鼠每任意三类各取一只进行组合，但要求是每只老鼠不能和已组合过的老鼠再次组合，同时每只老鼠都要与其他类的所有老鼠都进行过组合。

首先先考虑A1，A1需要参与的组合按大类分有A1BC，A1BD，A1CD三种。

按要求简单列出一种具体的可能：

A1B1C1，A1B2D1，A1C2D2。

然后考虑A2，A2的组合只需要考虑上述对称的部分：A2B2C2，A2B1D2，A2C1D1。

此时考虑B1和B2还没组合到的老鼠，得到B1C2D1，B2C1D2。

而C1，C2，D1，D2此时已经和所有需要组合的老鼠组合过了。

因此一共列出了8个组合：A1B1C1，A1B2D1，A1C2D2，A2B2C2，A2B1D2，A2C1D1，B1C2D1，B2C1D2。

加上四个大类：A1A2，B1B2，C1C2，D1D2。

一共十二种组合，让每瓶水对应一种组合，并且让一瓶水不对应任何老鼠组合。

这样8只老鼠便可以对应上8+4+1=13瓶水。

每瓶水让对应的组合的老鼠喝即可。

有了该方案后，我们只需要去掉2瓶水/2种组合，便是8只老鼠喝11瓶水的方案了。

因此只需要8只老鼠就可以找到毒药在哪些行，同理也只需要8只老鼠就可以知道毒药在哪些列。而对角线验证不变。此时一共需要8+8+5=21只老鼠。

在上述方案的基础上做进一步优化。考虑到8只老鼠在上一个方案中只能在11瓶水中找2瓶毒药，而实际上7只老鼠可以做到在10瓶水中找到2瓶毒药。即在9行/列中找到一或两行有毒药。所以为了增大老鼠的利用率。将方阵从10x10结构改为9x11结构。

根据前面的构造可知8只老鼠可以在13瓶水中找2瓶毒药，所以自然可以在11列中找到一或两行有毒药。另外9行我们使用7只老鼠。这样便可以省去一只老鼠。

下面展示只用7只老鼠在10瓶水中找到2瓶毒药的方案：

即大方案的简化，行使用3只，列使用3只，对角线使用1只。而实际上这种方法即使毒药只有1瓶也可以找到（毒药只有1瓶时只有一行一列存在有毒可能，因此唯一的交点就是毒药）。因此第10瓶水不需要任何老鼠喝，当只找到1瓶毒药时，剩下的1瓶就也是毒药。

同理，在9x11方阵结构中，一共只有99个格子，放置99瓶水，而剩下的一瓶并不需要有老鼠喝。

9x11方阵一样使用5只老鼠便可以进行对角线校验。

此时一共使用7+8+5=20只老鼠。

不妨尝试将结构扩展一下，100=5*5*4，考虑5*5*4的长方体结构，在每一个小立方体内放置一瓶水，那么每瓶水都有一个空间坐标（x，y，z）（x=0,1,2,3,4; y=0,1,2,3,4; z=0,1,2,3)，

在xyz的每个平面都放置一只老鼠，喝遍这个平面内所有的水。一共放置5+5+4=14只老鼠。

那么假设毒药的坐标为(a,b,c)和(p,q,r)。则a,p; b,q; c,r层的老鼠都会死亡。

当其中有重合老鼠的时候，情况显然只会变得简单，这里不再过多赘述。考虑a≠p;b≠q;c≠r，

这个时候每对位都有2种可能，那么毒药一共有四种可能。

(a,b,c),(p,q,r);

(a,b,r),(p,q,c);

(a,q,c),(p,b,r);

(a,q,r),(p,b,c);

为了将其区分开，还是可以效仿平面结构时的对角线校验。

考虑平面xy，上面混淆的只有(a,b),(p,q)和(a,q),(p,b)，

因此，只需要在这个平面上进行对角线校验，

而5*5平面的对角线校验只需要2只老鼠，

因此，只需要分配2只老鼠，一只喝遍所有z上每一层红色格子的水（z=0，1，2，3）；一只喝遍所有z上每一层蓝色格子的水（z=0，1，2，3）即可

另外两组平面yz和xz同理，其中4*5平面的校验采用5*5的方法删去一行即可。

所以一共使用14+2+2+2=20只老鼠。

如果继续升维，使用4位对100瓶水进行编码，那我们需要检验的平面有3*3；3*3；3*4；3*3；3*4；3*4，共六组。

其中3*3检验只需要1只，3*4需要2只。

所以一共使用3+3+3+4+1+1+2+1+2+2=22只老鼠。

由以上分析讨论，我们可以得到一个结论：

对于n瓶水中，若有2瓶水有毒，那么可以

设函数a(n)表示所需要使用的老鼠数量的最小值(n≥2且为正整数)，

函数b(x)(y)表示x*y方阵中进行对角线校验所需要的老鼠数量的最小值(x,y≥2且为正整数)。

那么对于t1*t2*……*tm瓶水(t1*t2*……*tm+1瓶水也可以），

可以解决问题的老鼠数量为：

本题将100拆为9*11+1或5*5*4都可以用20只老鼠解决，是目前该构造方式中所已知的最优解。

本方案采用9*11方阵法

下面展示这种方法下构造出来的具体编码：

实际上，目前已知的理论最优解为17只（OEIS-A054961），数学爱好者Zhao Hui Du于2018年通过计算机计算出了27只老鼠及以内能识别的水瓶数量下界。其中a(17)>=112，意味着在2瓶水有毒的情况下，17只老鼠至少能识别112瓶水。但因为计算量过于庞大，无法穷尽可能，所以16只老鼠是否足够尚且还是未知之谜。此外，17只老鼠的解由计算机得到，目前也没有便于人类理解的构造方法。若你发现了20以内的纯构造方法，可以发送至我们邮箱；若你对这个问题本身有了更大的突破，建议考虑发表期刊。

本题目邮件解答前三名分别是：

【第一名】布丁

【第二名】yyao

【第三名】御坂14491号

第一名奖励23.33元红包；

第二、三名每人奖励6.66元红包；

所有发送过答案的小伙伴，每人奖励2.33元红包！

后台回复【魔法毒药+提交答案用的昵称】查询得分，如【魔法毒药布丁】。