2 replaced http://puzzling.stackexchange.com/ with https://puzzling.stackexchange.com/ edited Apr 13 '17 at 12:50 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: 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$$. 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$$. 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$$. 1 answered Apr 29 '15 at 16:34 Joe Z. 21.8k77 gold badges7878 silver badges152152 bronze badges 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$$. Post Made Community Wiki by Joe Z. occurred Apr 29 '15 at 16:34