Poison and Prisoner
10000桶酒,其中1桶是毒酒;48小时后要举行酒会;毒酒喝下去会在之后的第23-24小时内毒死人。
国王决定用囚犯来试酒,不介意囚犯死多少,只要求用最少的囚犯来测试出哪一桶是毒酒。
问最少需要多少囚犯才能保证找出毒酒?
然后大概可以这样操作,假设有 $t$ 个时间点可以喝酒。
给这 $n$ 瓶酒用一个 $m$ 维的向量编号,每一维的取值范围是 $(0, 1, …, t)$,这里 $m = \lceil log_{t+1}(n) \rceil$。
这样每一维对应一个人吧,然后在 $t_1$ 时让 $m_1$ 这个人喝下所有编号在第 $m_1$ 维的分量是 $t_1$ 的酒。
根据每一维对应的人的死亡时间确定这一维的分量(如果没死就是 0,如果在 $t_1$ 对应的时间死亡就是 $t_1$)。
综合所有人的死亡时间确定所有维的分量。
再把这个向量换算回原来的编号。