11
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ The question may not be clear enough to someone who hasn't already come across such a puzzle. $\endgroup$ – ghosts_in_the_code Apr 29 '15 at 16:41
  • $\begingroup$ How do you figure? $\endgroup$ – Joe Z. Apr 29 '15 at 16:42
7
$\begingroup$

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:

  1. On the first day, the second prisoner dies. So we know that the second digit on the poisoned bottle's label is $1$.

  2. On the second day, nobody dies, so we know that none of the bottles labelled with a $2$ are poisoned.

  3. 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$.

$\endgroup$
  • $\begingroup$ This does not account for the fact that dead prisoners can't take the poison. $\endgroup$ – PStag Mar 8 '16 at 3:07
  • $\begingroup$ It does. In the cases where prisoners are dead, there are just enough prisoners left to cover all the cases that still need to be considered. $\endgroup$ – Joe Z. Mar 8 '16 at 3:17
  • $\begingroup$ No, if I run it with 1 prisoner, and one thousand years, I can test two bottles of wine. Your formula gives 365251 bottles of wine. $\endgroup$ – PStag Mar 8 '16 at 3:26
  • 2
    $\begingroup$ You can test for 356243 different bottles of wine by giving the prisoner a different bottle to drink every day; once he dies, the bottle he drank last is the poisoned bottle, and every bottle after that you no longer need to test because you found the one with poison in it. $\endgroup$ – Joe Z. Mar 8 '16 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.