Q - 老鼠喝药水

数学

题目

你面前有 100 瓶药水,标号 1 ~ 100. 其中有且仅有一瓶毒药,其余都是无毒药水.

这瓶毒药比较特殊,喝了它并不会立即死掉,而是会在第二天立刻同时显现药性(就是死掉),也就是说,第二天喝过毒药的老鼠都会死去,而第一天和正常老鼠没有区别.

你有 7 只老鼠,编号 1 ~ 7,每只老鼠可以喝下无限量的药水,每瓶药水无限供应.

假定你有无限的计算能力,只要信息足够,你可以在一瞬间计算出是哪一瓶药水有毒.

问:如何仅通过这 7 只老鼠,在第二天到来后,根据它们的死活找出那一瓶毒药

提示

没有头绪时,再依次单击展开提示

HINT 1每只老鼠有两种状态:生和死
HINT 2每瓶药水有两种状态:有毒或没毒
HINT 3$2^7 = 128 \approx 100$,且$128 > 100$
HINT 4考虑二进制
HINT 5死为1,生为0;有毒为1,没毒为0
HINT 6类似状态压缩
HINT 7$1 = 1_{(2)}, 2 = 10_{(2)}, 3 = 11_{(2)}, 4 = 100_{(2)} , \dots , 100 = 1100100‬_{(2)}$
HINT 8$100 = 1100100‬_{(2)}$,恰好7位,可以对应每一只老鼠
HINT 9一只老鼠对应一个数位

答案

ANSWER把 1 ~ 100 的每一个数改写成二进制,让第 1 只老鼠喝二进制下第 1 位为 1 的药水,第 2 只老鼠喝第 7 位为 1 的药水,以此类推,第 7 只老鼠喝第 7 位为 1 的药水. 到了第二天,枚举 i 从 7 到 1,统计第 i 只老鼠死了与否,若死去,把第 i 位标记为 1 ,反之为 0 . 这样得到一个 0-1 串. 把这个 0-1 串转换为十进制,即为毒药的编号.
EXAMPLE实施 ANSWER 的做法,假设只有 1、3、7 号老鼠死掉,得到的 0-1 串就是:1000101. 对应十进制 69,即第 69 瓶药水为毒药.
EXPLANATION如上例,1、3、7 死去,说明二进制表示下 1、3、7 位为 1 的药水有嫌疑,而其他喝了药水的老鼠安然无恙,说明二进制下 2、4、5、6 位为 1 的药水没有嫌疑,这样就可以写出药水的二进制表达式.

本文作者:Xecades

本文链接:https://blog.xecades.xyz/articles/Question1/

文章默认使用 CC BY-NC-SA 4.0 协议进行许可,使用时请注意遵守协议。

评论