micromass said:
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
