Logic puzzle : Smallest number of prisoners required?

In summary, in order to find the poisoned bottle of wine within 24 hours, the ruler of the medieval empire would need 10 prisoners to drink from the bottles and determine which one is poisoned. However, if there is also a disease affecting the prisoners, the ruler would need to use 70 prisoners to be 99% certain of identifying the poisoned bottle. This is due to the use of a virtual prisoner system and the probability of error in decoding the correct bottle.
  • #1
atom jana
13
1
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?
 
Physics news on Phys.org
  • #2
Since ##\log_2(1000) = 9.96##, you'll need ##10## prisoners.
 
  • #3
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...
 
  • #4
10

You assign each of the 10 prisoners a power of 2, from 20 = 1 to 29 = 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.
 
  • #6
Are we really going to feed 500 glasses of wine to each prisoner? If the poison doesn't kill them, that will!
 
  • #7
The other answers came in as I was typing. Now I look like an idiot for using spoiler tags :oops:
 
  • Like
Likes ProfuselyQuarky
  • #8
micromass said:
Are we really going to feed 500 glasses of wine to each prisoner? If the poison doesn't kill them, that will!
atom jana said:
after consuming even the minutest amount of poison
I guess a drop of each bottle will suffice.
 
  • #9
atom jana said:
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.
 
  • Like
Likes Pepper Mint and jedishrfu
  • #10
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?
 
  • Like
Likes jedishrfu and DrClaude
  • #11
DrClaude said:
I guess a drop of each bottle will suffice.

Hard to tell, it is the dose that makes the poison.
 
  • Like
Likes jedishrfu and DrClaude
  • #12
And now the Princess Bride:

 
  • Like
Likes Evo, Pepper Mint and DrClaude
  • #13
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
[tex]1-\xi = \sqrt[10]{0.99} = 0.9989955[/tex]
By using a normal distribution table, we find that this is true iff
[tex]\sqrt{n\cdot 0.1\cdot 0.9}\frac{n}{2} +n\cdot 0.1 > 3.088899[/tex]
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
 
  • Like
Likes jedishrfu and Choppy
  • #14
Can you dilute the poisoned bottle with the other 999 and serve all 1000 without killing anyone?
 
  • #15
tobyr65 said:
Can you dilute the poisoned bottle with the other 999 and serve all 1000 without killing anyone?

You must be an engineer...
 
  • Like
Likes jedishrfu and jackwhirl

Related to Logic puzzle : Smallest number of prisoners required?

1. What is a logic puzzle?

A logic puzzle is a type of brain teaser or game that requires critical thinking and problem-solving skills to reach a solution. It typically involves using clues and deduction to solve a complex problem or scenario.

2. What is the "smallest number of prisoners required" logic puzzle?

The "smallest number of prisoners required" logic puzzle is a popular mathematical riddle that involves determining the minimum number of prisoners needed to guarantee a correct guess of their own hat color. It is often used to test logical reasoning and strategic thinking abilities.

3. How does the "smallest number of prisoners required" puzzle work?

In this puzzle, a group of prisoners are given a challenge where they must guess the color of their own hat. The prisoners are only able to see the hats of the other prisoners, and not their own. The catch is that they must all guess simultaneously, and if even one prisoner guesses incorrectly, they will all be executed. The goal is to find the minimum number of prisoners needed to guarantee a correct guess for all prisoners.

4. What is the solution to the "smallest number of prisoners required" puzzle?

The solution to this puzzle is that the minimum number of prisoners required is equal to the number of different hat colors available. For example, if there are four different hat colors, then a minimum of four prisoners are needed to guarantee a correct guess for all prisoners. This can be achieved through a strategic system of counting and signaling between prisoners.

5. Why is the "smallest number of prisoners required" puzzle important?

This puzzle is important because it challenges individuals to think critically and use logical reasoning to find a solution. It also demonstrates the power of collaboration and strategic thinking in problem-solving. Additionally, it has practical applications in fields such as mathematics, computer science, and game theory.

Similar threads

  • Sci-Fi Writing and World Building
Replies
6
Views
2K
  • Math Proof Training and Practice
2
Replies
67
Views
10K
  • General Discussion
3
Replies
90
Views
70K
  • General Discussion
3
Replies
78
Views
10K
  • General Discussion
Replies
2
Views
3K
  • Precalculus Mathematics Homework Help
Replies
28
Views
9K
  • General Engineering
Replies
21
Views
5K
Replies
33
Views
7K
  • General Discussion
Replies
4
Views
7K
Back
Top