题目
你面前有 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/drafts/Question1.html
文章默认使用 CC BY-NC-SA 4.0 协议进行许可,使用时请注意遵守协议。
评论