毒酒桶 III

Poisoned Kegs III

专题: Brainteaser / 脑筋急转弯
难度: L4
来源: QuantQuestion

题目详情

国王有 10 名仆人试酒， $n$ 桶酒中恰好 1 桶有毒。若喝到毒酒，1 个月后死亡；否则存活。

仆人只同意参与 1 个月。

问：最大 $n$ 是多少，能保证国王至少有 10% 的概率确定毒桶是哪一桶？

A king has $10$ servants that bravely risk their lives to test whether or not the wine in $n$ kegs is poisonous. It is known that exactly one of the $n$ kegs is poisonous. If someone drinks any amount of liquor from the poisoned keg, they will die in exactly $1$ month. Otherwise, the servant will be fine. The servants only agree to participate in the wine tasting for $1$ month. What is the maximum value of $n$ such that the king is guaranteed to have at least a $10\%$ chance to determine which keg among the $n$ is poisoned?

解析

10 名仆人可产生 $2^{10}$ 种死亡模式。

若希望“至少 10% 概率完全定位”，可以把每一种死亡模式对应到 10 桶不同的酒（让该模式对应的那一组仆人去尝这 10 桶）。

若最终出现某死亡模式，则国王只能确定毒桶在那 10 桶里，随机落在其中任意一桶的概率为 1/10。

因此可覆盖的桶数最多为

2^{10}\times 10=10240.

Original Explanation

Using the same idea as Poisoned Kegs II, we can let each of the $10$ servants represent a binary indicator for the first $2^{10}$ kegs. Thus, in the first $2^{10}$ kegs, we will know exactly which keg is poisoned. However, now we just need to narrow it down to $10$ kegs per possible death sequence. The easiest way to do this is to have each of the $2^{10}$ subsets of servants test $10$ different kegs. Then, if some subset of servants die, the king will know that one of those $10$ kegs that the subset of servants died to has the poison. Therefore, the king can test $10$ times as many kegs if he only wants at least a $10\%$ chance of identifying it. Therefore, the king can test up to $n = 2^{10} \cdot 10 = 10240$ kegs.