2 replaced http://puzzling.stackexchange.com/ with https://puzzling.stackexchange.com/
source | link

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

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

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

1
source | link

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

    Post Made Community Wiki by Joe Z.