题有毒，还是智力有问题——瓶水有毒[智力题？！](智力唤醒、简单代码、公平性)数据结构与算法weixin45221012的博客-

一、智力题？？！

有1000瓶水，其中有一瓶有毒，小白鼠只要尝一点带毒的水24小时内就会死亡，至少要多少只小白鼠才能在24小时内鉴别出哪瓶水有毒？【题目肯定经不起吃瓜大众的推敲，我们还是按出题人的思路来！】

二、思路

返回顶部
对不起，刚开始跑偏了。
自诩数学基础好、生活经验丰富的我，思绪飘过二叉树、布隆过滤器，在奥卡姆剃刀指引下，最终回归最基础的二进制(如果是1024瓶水，保证不跑偏！)。
实际的心路历程是这样的：

1. 我的智商可能有问题？
2. 我的智商难道有问题？？？
3. 我的智商真的有问题！
   好吧，承认智商有问题后，路就好走了！笨人文化——枚举！！！
4. 总共一瓶水，其中一瓶水有毒，不用抓小白鼠。
5. 总共两瓶水，其中一瓶水有毒，抓一只小白鼠，试喝其中任一瓶，24小时后牺牲了，该瓶水有毒，另一瓶无毒；反之，该瓶水无毒，另一瓶水有毒。【最多牺牲1只小白鼠】
6. 总共三瓶水(编号1、2、3)，需要抓两只小白鼠，第一只小白鼠喝瓶1水；第二只小白鼠喝瓶2水；24小时后，如果有小白鼠牺牲，对应的瓶水有毒；如果都活着，瓶3水有毒。【最多牺牲1只小白鼠】
7. 总共四瓶水(编号1、2、3、4)，需要抓两只小白鼠，第一只小白鼠喝瓶1、3水各1滴；第二只小白鼠喝瓶2、3水各1滴；24小时后，如果只有第一只小白鼠牺牲了，瓶1水有毒；如果只有第二只小白鼠牺牲了，瓶2水有毒；如果两只小白鼠都牺牲了，瓶3水有毒；如果都活着，瓶4水有毒。【最多牺牲2只小白鼠】
   ……
   简而言之：不同瓶号的水，让不同小白鼠组合来喝；根据牺牲的小白鼠组合，可反推出哪瓶水有毒。
   终于回忆起二进制这个熟悉的陌生人了！

三、二进制表示

【小白鼠从右往左编号】
第一瓶水，取一滴只给第一只小白鼠喝，二进制表示0000000001；
第二瓶水，取一滴只给第二只小白鼠喝，二进制表示0000000010；
第三瓶水，取两滴，分别给第一只、第二只小白鼠喝，二进制表示0000000011；
第四瓶水，取一滴只给第三只小白鼠喝，二进制表示0000000100；
第五瓶水，取两滴，分别给第一只、第三只小白鼠喝，二进制表示0000000101；
第六瓶水，取两滴，分别给第二只、第三只小白鼠喝，二进制表示0000000110；
第七瓶水，取三滴，分别给第一只、第二只、第三只小白鼠喝，二进制表示0000000111；
……
第511瓶水，二进制表示0111111111；
……
第767瓶水，二进制表示1011111111；
……
第999瓶水，二进制表示1111100111；
第1000瓶水，二进制表示1111101000。
【因10个二进制位最多可以表示0～1023共1024种状态，1024＞1000，因此可以将任意一瓶的二进制表示替换成0000000000(所有小白鼠都不喝)，其它瓶仍然按照编号对应的二进制】

四、简单python代码实现

4.1 假设有毒水瓶号，断言牺牲的小白鼠编号

返回顶部

def mouse(n):     mouse_die = []     i = 1 while n:         n, m = divmod(n, 2) if m:             mouse_die.append(i)         i += 1 return mouse_die  print('第5瓶水有毒时，牺牲的小白鼠编号：', mouse(5)) print('第21瓶水有毒时，牺牲的小白鼠编号：', mouse(21)) print('第511瓶水有毒时，牺牲的小白鼠编号：', mouse(511)) print('第767瓶水有毒时，牺牲的小白鼠编号：', mouse(767)) print('第999瓶水有毒时，牺牲的小白鼠编号：', mouse(999)) print('第1000瓶水有毒时，牺牲的小白鼠编号：', mouse(1000)) 

运行结果：

第5瓶水有毒时，牺牲的小白鼠编号： [1, 3] 第21瓶水有毒时，牺牲的小白鼠编号： [1, 3, 5] 第511瓶水有毒时，牺牲的小白鼠编号： [1, 2, 3, 4, 5, 6, 7, 8, 9] 第767瓶水有毒时，牺牲的小白鼠编号： [1, 2, 3, 4, 5, 6, 7, 8, 10] 第999瓶水有毒时，牺牲的小白鼠编号： [1, 2, 3, 6, 7, 8, 9, 10] 第1000瓶水有毒时，牺牲的小白鼠编号： [4, 6, 7, 8, 9, 10] 

4.2 根据牺牲的小白鼠编号组合，反推有毒水瓶号

def water(lt):     water_num = 0 for i in lt:         water_num += 2 ** (i - 1) return water_num      print('牺牲的小白鼠编号为:[1, 3]时，有毒的水瓶号是：', water([1, 3])) print('牺牲的小白鼠编号为:[1, 3, 5]时，有毒的水瓶号是：', water([1, 3, 5])) print('牺牲的小白鼠编号为:[1, 3, 6, 7, 8]时，有毒的水瓶号是：', water([1, 3, 6, 7, 8])) 

运行结果：

牺牲的小白鼠编号为:[1, 3]时，有毒的水瓶号是： 5 牺牲的小白鼠编号为:[1, 3, 5]时，有毒的水瓶号是： 21 牺牲的小白鼠编号为:[1, 3, 6, 7, 8]时，有毒的水瓶号是： 229 

五、公平性说明

返回顶部
善良的小伙伴，不必像我一样担心第一只小白鼠喝太多撑着(或牺牲概率太大)，每只小白鼠喝的基本一样多(赌中死亡轮盘的概率是一样的)。
第一只小白鼠(试喝1、3、5、……)，隔1瓶(号)试喝1瓶(号)里的一滴水。
第二只小白鼠(试喝2、3、6、7、10、11、……），隔2瓶(号)试喝2瓶(号)里的一滴水。
第三只小白鼠(试喝4、5、6、7、12、13、14、15、……），隔4瓶(号)试喝4瓶(号)里的一滴水。
……
第十只小白鼠(前面511瓶不用试喝，后面都试喝)。
如果是1024瓶水，每只小白鼠都喝512瓶(所有小白鼠都不喝第1024瓶)，第十只小白鼠(试喝512、513、514、……、1023)。

5.1 排列组合角度看公平性

十只小白鼠都牺牲或都活着的组合：
$C_{10}^0 = C_{10}^{10} = frac{10!}{0! × (10-0)!} = 1$

C100​=C1010​=0!×(10−0)!10!​=1
十只小白鼠牺牲一只或幸存一只的组合：
$C_{10}^1 = C_{10}^9 = frac{10!}{1! × (10-1)!} = 10$

C101​=C109​=1!×(10−1)!10!​=10
十只小白鼠牺牲二只或幸存二只的组合：
$C_{10}^2 = C_{10}^8 = frac{10!}{2! × (10-2)!} = 45$

C102​=C108​=2!×(10−2)!10!​=45
十只小白鼠牺牲三只或幸存三只的组合：
$C_{10}^3 = C_{10}^7 = frac{10!}{3! × (10-3)!} = 120$

C103​=C107​=3!×(10−3)!10!​=120
十只小白鼠牺牲四只或幸存四只的组合：
$C_{10}^4 = C_{10}^6 = frac{10!}{4! × (10-4)!} = 210$

C104​=C106​=4!×(10−4)!10!​=210
十只小白鼠牺牲五只或幸存五只的组合：
$C_{10}^5 = frac{10!}{5! × (10-5)!} = 252$

C105​=5!×(10−5)!10!​=252
可以发现：
$2^{10} = 1024 = displaystyle sum_{i = 0} ^{10} C_{10} ^i$

210=1024=i=0∑10​C10i​
组合是没有顺序的，机会均等，因此每只小白鼠牺牲的概率是一样的。

六、结论：

1. 需要10只小白鼠，来实现任务目标；
2. 每只小白鼠的使命和壮烈概率基本相同；
3. 最幸运的情形，所有小白鼠都幸存；
   【比如将1000的二进制表示替换成0000000000，即第1000瓶不给小白鼠喝】
4. 最不幸的情形，只有一只小白鼠幸存。

向献身医学的小白鼠致敬！！！
欢迎关注，敬请！
返回顶部