Since there have been quite a few poisoned-bottle problems posted to the site already, I thought I'd post a general formula to cover all future variations of this problem (at least where a single poisoned bottle is concerned).
You have $n \le (m+1)^k$ bottles of wine, one of which is poisoned. The poisoned wine kills any person who drinks it at the stroke of midnight on the day that they drank it. You have $k$ prisoners to test the wine by making them drink it and possibly killing them, and $m$ days to conduct these death trials. How do you plan out the tests so that you can figure out which bottle is poisoned?
Answer
Each prisoner has $m+1$ possible states from the trials — dead in 1 day, dead in 2 days, ..., dead in $m$ days, not dead. This makes for a total of $(m+1)^k$ total possible states.
Since this is an information puzzle, we want to map each bottle to a possible state.
If we assign each bottle a $m+1$-ary number with $k$ digits (or alternatively, an ordered $k$-tuple with integers from $0$ to $m$), we can make this represent the days on which we need to give the prisoners these bottles as testing. Specifically, on the $i$th day, we give the $p$th prisoner any bottle where the $p$th digit is $i$, so that if the prisoner dies on that day, then we know that the poisoned bottle must have the $p$th digit equal to $i$.
In this way, we can narrow the possibilities down to a single bottle. For example, if $m = 3$ and $k = 4$, and the bottle (out of $256$) is labelled $0130$ (out of $0000$, $0001$, $0002$, $0003$, $0010$, $0011$, etc. up until $3333$), then the following will happen:
On the first day, the second prisoner dies. So we know that the second digit on the poisoned bottle's label is $1$.
On the second day, nobody dies, so we know that none of the bottles labelled with a $2$ are poisoned.
On the third day, the third prisoner dies and nobody else does, so we know that the third digit is $3$, and the rest are $0$. Therefore, the poisoned bottle is the one labelled $0130$.
No comments:
Post a Comment