[Math]老鼠,毒药和酒

如果你有9瓶酒,其中一瓶有毒但你不知道究竟是哪一瓶.幸运的是你有两只老鼠可以拿来测试--老鼠碰到毒酒立刻就被毒死了.给定这两只老鼠,如果测试两轮(一轮指你可以对部分或者全部老鼠喂一次酒),如何能够测试出哪瓶是毒酒? 进一步,如果给你5只老鼠,如何在两轮内找出243瓶酒中哪一瓶是毒酒.

Sol:
part1
给酒编号,编号为1 2 3的酒喂老鼠A, 编号为3 4 5的酒喂老鼠B.
case1 A alive, B alive -> poised in 6, 7, 8, 9.
case2 A dead, B alive -> poised in 1, 2
case3 A alive, B dead -> poised in 4, 5
case4 A dead, B dead -> poised is 3, done

case1的情况下, 使用A测试6,7, 使用B测试7,8就可以得到最后结果
case2和case3的情况下, 让活着的一只老鼠喝一瓶酒,也可以得到结果.

part2
让我们用N(k,1)指代给定k只老鼠,只能测试一轮的情况下,最多能找出多少瓶酒中的一瓶毒酒.不难发现N(k,1)=2^k (特别的N(0,1)=1 也就是说一只老鼠都不给,只能断定:只有1瓶的时候这瓶一定是毒酒)

N(k,2)=N(k,1)*C(0,k) + N(k-1,1)*C(1,k) + N(k-2,1)*C(2,k) + ... + N(0,1)*C(k,k)
= 3^k
=> N(5,2)=243