Logic puzzle : Smallest number of prisoners required?

[atom jana]

You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned.

The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison.

You have over a thousand slaves at your disposal and just under 24 hours to determine which single bottle is poisoned.

You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed.

What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?

 

[micromass]

Since $\log_2(1000) = 9.96$, you'll need $10$ prisoners.

 

[jedishrfu]

So I'd say 10 prisoners are needed where you'd number the bottles in binary and associate a each bit position with a prisoner.

They drink multiple bottles based on whether their bit is a 1 in the bottles number and after 24 hours the prisoners who died are used set the 1 bits of the bottle in question.

Now you can sing the song:

999 bottle of wine on the shelf, 999 bottles of wine... take one down and pass it around ... 998 bottles of wine on the shelf...

 

[DrClaude]

Spoiler

10

You assign each of the 10 prisoners a power of 2, from 2⁰ = 1 to 2⁹ = 512. You label each bottle by a number from 1 to 1000 in binary. Then you make the 10 prisoners drink from each bottle for which they would represent a one in the binary number. Once they have died, you read off the bottle number from who died.

 

[jedishrfu]

Shades of the Princess Bride movie.

 

[micromass]

Are we really going to feed 500 glasses of wine to each prisoner? If the poison doesn't kill them, that will!

 

[DrClaude]

The other answers came in as I was typing. Now I look like an idiot for using spoiler tags

 

[DrClaude]

Are we really going to feed 500 glasses of wine to each prisoner? If the poison doesn't kill them, that will!

after consuming even the minutest amount of poison

I guess a drop of each bottle will suffice.

 

[DrClaude]

What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?

Actually, you have to be careful about false positives: what if a prisoner dies, but for a reason unrelated to the poison? To be absolutely sure, you would need 1000 prisoners, each assigned to a bottle, and eliminate all bottles for which a prisoner dies in case of multiple deaths.

 

[micromass]

So, since this puzzle is clearly too easy for PF:
There is also a disease at the prisons and all prisoners are affected. The probability of any prisoner dying withint 24 hours is $0.1$. How many prisoners do you need now so that you are $99\%$ certain that you identify the correct wine?

 

[Borek]

I guess a drop of each bottle will suffice.

Hard to tell, it is the dose that makes the poison.

 

[jedishrfu]

And now the Princess Bride:

 

[micromass]

So, since this puzzle is clearly too easy for PF:
There is also a disease at the prisons and all prisoners are affected. The probability of any prisoner dying withint 24 hours is $0.1$. How many prisoners do you need now so that you are $99\%$ certain that you identify the correct wine?

Let me try to solve this in a few ways. We again need to use 10 persons to test the wines are previously specified. But now, a person can also die of the disease and not only of the wine. An obvious but naive solution would be to duplicate the number of prisoners. So instead of using 10 prisoners, we will use $10n$ prisoners for $n\geq 1$ an odd natural number. We arrange the prisoners as follows, the first set of $10$ is $(a_1, b_1, c_1, d_1, e_1, f_1, g_1, h_1, i_1, j_1)$ and the last set of $10$ prisoners is $(a_n, b_n, c_n, d_n, e_n, f_n, g_n, h_n, i_n, j_n)$.

So we get $10n$ prisoners for $n$ odd and we wait for $24$ hours. Then we will look at the $a$-prisoners: $a_1$, ..., $a_n$. If the majority lives, then we will say that the $a$ prisoners live. We do the same with the $b$ prisoners, the $c$ prisoners, etc. In this way, we form a virtual prisoner $(a,b,c,d,e,f,g,h,i,j)$ which is the average of the $10n$ prisoners. This prisoner is then used to find the poisoned wine.

So let's find out how big $n$ should be. The wrong wine is picked if $a$ is decoded incorrectly or if $b$ is decoded incorrectly, etc. Let's find the probability for $a$ being decoded incorrectly:

Let's say the correct value of $a$ is dead. Then there is no way that there could be an error.
Let's say the correct value for $a$ is living. There could be an error if more than $n/2$ people die. The probability of one person dying is $0.1$. The probability of more than $n/2$ people dying can be found by $\mathbb{P}\{X>n/2\}$, where $X$ is a binomially distributed random variable with $n$ trials and with $p=0.1$. We can find this exactly by $\sum_{n/2<k\leq n} \binom{n}{k} (0.1)^k (0.9)^{n-k}$. We use the central limit theorem however to see that $X\sim \frac{Z - n\cdot 0.1}{\sqrt{n\cdot 0.1\cdot 0.9}}$, to find that the probability is essentially $\xi :=\mathbb{P}\{Z> \sqrt{n\cdot 0.1\cdot 0.9}\frac{n}{2} +n\cdot 0.1\}$, where $Z$ is the standard normal distribution. So this value $\xi$ is the probability for error in the worst possible $a$ case.

Now we need to find the probability of error in the total code. There is no error if all of $a$, $b$, $c$, ... are decoded correctly. This happens with probability $(1-\xi)^{10}$. We wish this probability to be $>0.99$. So we wish to find $n$ such that
$$1-\xi = \sqrt[10]{0.99} = 0.9989955$$
By using a normal distribution table, we find that this is true iff
$$\sqrt{n\cdot 0.1\cdot 0.9}\frac{n}{2} +n\cdot 0.1 > 3.088899$$
Some easy computations gives us $n=7$. So in this case, we need $70$ people.

Of course, other systems are possible of coding this information. This is the research field of error detection and correction. In this field, there is an immense amount of possible codes that might apply to this situation. https://en.wikipedia.org/wiki/Error_detection_and_correction

 

[tobyr65]

Can you dilute the poisoned bottle with the other 999 and serve all 1000 without killing anyone?

 

[micromass]

Can you dilute the poisoned bottle with the other 999 and serve all 1000 without killing anyone?

You must be an engineer...