The poison testers
There is a king who wants to throw a party in 48 hours and he wants to serve a total of 500 barrels of wine at the party. Unfortunately, he knows that one of the barrels has been poisoned and he does not know which one. When consumed, the poison takes between 23 and 24 hours to kill.
In order to determine which barrel the poison is in, the king wants to use his prisoners as taste testers. What is the fewest number of prisoners that he needs to test the barrels in 48 hours?
Note: The king doesn't care about the number of prisoners that die. He just wants to minimize the number of prisoners used.
The answer is 2.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
I came across this on fb, and had the same solution, but explaining it as a grid rather that with algebraic coordinates made it easier to understand, I.e. lay the barrels out in 24 by 24 grid (only need 23) and have one person drink every barrel from row one at begining of hour one, row 2 at begining of hour 2 and so on, and do the same with another person for the columns, and the hour they each die in minus 23 gives the row and column containing the poison
Log in to reply
I drew this grid and it was so easy to explain. Thank you. I wish I could post a photo of it.
Log in to reply
On desktop, when posting a solution, you will get a formatting toolbar that allows you to upload photos by clicking on the image icon (third from the left)
Alternatively, you can also "click and drag an image into the solution", which causes the toolbar to change to
If you're still having difficulty, you can email the image to me (Calvin at Brilliant.org), and I can upload it for you.
Great! That's exactly the same idea. I agree that having the pictorial explanation would make it easier to grasp. Let me see what I can do about it.
It's clever, but it relies on the assumption that diluting the poison 624-fold doesn't minimise its effect...and indeed that you can get that much wine into the prisoners. It would have been helpful if you'd mentioned this in the question! (infinitely large prisoners...homeopathic poison...) :-)
Log in to reply
well if diluting was a solution then there won't be need for any prisoners. just mix all the wine of all the barrels firmly so the poison is diluted into all 500 and fails to work.
it depends on the concentration of the poison. if the prisoner needs to drink half a glass from each barrel, he'll certainly die from alcoholic coma before the poison effect to kick in. so the solution is strictly narrowed one and as a king's most trusty lip i will certainly not agree with. the safest number of prisoners is 250, cause safety comes always first, even in the dark ages.
Log in to reply
250 will correct answer because identifying the poisoned barrel is also important as drink has to served according to question.....so i and j thing won't work here...
Log in to reply
The i and j thing does identify the barrel. That's the whole point.
So two people drink 500 glasses of wine? They both would be dead.
Log in to reply
Lol right?
The king would want to minimize waste and only giving them a few drops to test lol
What if i say two prisoners are enough for even 2 6 × 2 6 = 6 7 6 barrels, as we could have i = 0 and j = 0 for possible values of i and j . This would mean, the first prisoner doesn't drink wine from that barrel at all if it's labeled with i = 0 , and the second prisoner won't drink from the barrel at all if it has j = 0 . For example, if the first prisoner doesn't die and the second prisoner dies during the second hour of day 2, that would mean the barrel ( 0 , 3 ) is poisoned.
Nice. Very out of the box.
If you're really wanting to be anal about precision, make the time between tastings 1 hour 4 minutes. With how loosely the question is worded, without the buffer, there would be a one minute overlap and therefore uncertainty as to whether it was the barrel before or after the decided barrel.
That much wine would kill a person, not regarding the status of the poison.
no of barrels is not given😕
And now I'd like to know which barrel is the infected one!!!
Log in to reply
suppose the first prisoner die the second day between 7H00 and 8H00. this means one of the barrels in the 8th group is poisoned. now if for example the second prisoner dies between 16H00 and 17H00 this means that exactly the 17th barrel in the 8th group is poisoned.
This is a really interesting problem.
I've edited the solution for clarity and explicitly stated which barrel is poisoned.
I figured it would be 42. Each one tests a different wine barrel every two hours until they've each tested 12(except for one guy who only tests 8). They record the times that the prisoners drink from each barrel and determine the poisoned barrel by seeing which wine the prisoner drank 23-24 hours prior to his death.
2 (using the 1 hour method). We're not talking about the prisoners drinking a full glass, since it is unknown just exactly how much poison needs to be consumed for it to be deadly, we can assume that 1 drop of the wine will be enough to kill you. Therefore, they wouldn't need a full glass, perhaps just a drop, or thimbleful. Reducing the risk of alcohol poisoning.
The only problem I have with your answer is in the ambiguity of the time for the poison to kill. The problem states that the poison takes between 23 and 24 hours to kill. Thus the length L is 23:00:00 <L<24:00:00. Lets say that in this instance the poison killed at 23 hours, 59 minutes, and 59 seconds (23:59:59) which is within the confines of the stated problem. That means that in order for the solution to work, all 24 samples of any set (i,.) MUST have been consumed by the prisoner in less than 1 second. And even then it would not be able to differentiate from the next sample in case the time frame needed to kill was only 23:00:01 I am not saying that your solution in general is faulty, just that the original problem is stated in such a way that we simply cannot use the number 23 as a finite component.
Log in to reply
We do have enough leeway. E.g. If we reduce to just 23 sets (since 2 3 2 > 5 0 0 , that gives them 2+ minutes to drink it.
But yes, in general for such problems, physical limitations are often ignored.
Log in to reply
I agree with you 100% and draw your attention that we have 25 periods of 1 hour length 23 to 24, 24 to 25 , .. ,47 to 48. So the physical limitation can be respected by 2.5+ minutes for 576 glasses. And in the case of 23*23 glasses we have more than 5 minutes between the intervals.
Excellent solution. Here's a different problem, if anyone's interested: Same setup as before except the poison can kill any time within 24 hours of ingestion. Now how many prisoners are required?
I accidentally treated the original problem this way and found a clever approach, and I want to see if anyone else finds it too.
In both the original and my variation you can assume 1 drop of poison is enough to kill, so no need to worry about the prisoners dying of alcohol effects of drinking large numbers of samples.
Log in to reply
Great! Could you publish that as a separate problem?
Log in to reply
I'd like to see first if I actually have the best answer. I have an approach that uses 7 prisoners, and my approach can use no fewer. But Mr. X says he can do it with 6. See my response to Mr. X, above.
I say 22 prisoners. Each prisoner starts with 22 barrels that they drink from. So at zero hour, 484 barrels are sampled.
If someone dies at 24 hours, you have 21 people to each drink from 1 of his 22 barrels. If one of them dies, you have your poison. If nobody dies, the remaining barrel is poisoned.
If at 24 hours nobody died, then you only have 16 barrels left to taste. 16 prisoners each grab one. Whoever does has the poison.
Log in to reply
The idea is good but not the best. Notice that only 6 prisoners will be enough to solve your problem if you use the same approach of the solution of 23 to 24 hours.
Log in to reply
@Mr X – I'm not following you. A sip of poison may kill in 1 minute or it may kill in 23 hours 59 minutes -- any time within 24 hours of ingestion. I see this as only allowing you to give a prisoner two distinct batches in 48 hours, and I don't see how 6 prisoners can zero in on the poison in only two batches each.
A simple version of my solution can identify the poison in 24 hours using 9 prisoners. Note that a 9-bit binary number has 512 unique values, slightly more than we need. Give each barrel an ID number from 0 to 499, in binary (0000000 to 111110011). Prisoner 1 sips from every barrel whose ID has a 1 in the first bit, Prisoner 2 sips from every barrel whose ID has a 1 in the 2nd bit, etc., up to Prisoner 9 is 9th bit. Wait 24 hours. See who's dead. To reconstruct the poisoned barrel's ID number put ones in the bits whose prisoners died, and zeros in the bits whose prisoners lived.
With 48 hours I can split up the job to work with only 7 prisoners, but it's hard to explain. No point explaining it if you can do it with 6 prisoners some other way.
Log in to reply
@Bill Hees – Just consider that each prisoner reduces the possibilities to the third. He may die on the first day or the second day or he may survive.
@Bill Hees
–
I think if I understand correctly all or at least most of those 9 people will have to drink from 250 barrels each in order for this solution to work.
Also I would be anxious to know how you can split it and work it out with 7 people.
@Bill Hees – If the job is split and the prisoners have to drink from 250 barrels on each day(assuming that nobody dies on the first day and the same prisoners drink from the remaining 250), then wouldn't the total number of prisoners be 8 since the 8-bit binary number has 256 unique values while 7-bit binary number has only 128 unique values?
Log in to reply
@Praveen Kumar – Yes, that approach does require 8 prisoners. I forget exactly how I did it two years ago with only 7, but it doesn't matter -- because @Mr X pointed out it can be done with 6 prisoners. Here's how I'd do that based on his tips:
Assign each barrel with an ID consisting of a six-digit number in base 3.
Assign each prisoner a number 1 through 6, corresponding to the six digits in these barrel IDs.
On Day 1, the 6 prisoners each drink from every barrel that has a 1 in their digit. On Day 2 the surviving prisoners each drink from every barrel that has a 2 in their digit. By the end, each prisoner will have either survived, died on Day 1, or died on Day 2. We label these 0, 1, and 2 respectively.
Assemble these digits in order of the prisoners they represent, to construct a six digit number. That is the barrel ID of the poisoned barrel.
Log in to reply
@Bill Hees – So, by this logic, if the king has 72 hours and the poison kills anytime within 24 hours, 5 prisoners will do the trick. Can you confirm if my approach is correct?
Assign each barrel with an ID consisting of a five-digit number in base 4.
Assign each prisoner a number 1 through 5, corresponding to the five digits in these barrel IDs.
On Day 1, the 5 prisoners each drink from every barrel that has a 1 in their respective digit. On Day 2 the surviving prisoners each drink from every barrel that has a 2 in their digit. On Day 3 the surviving prisoners each drink from every barrel that has a 3 in their digit. By the end, each prisoner will have either survived, died on Day 1, or died on Day 2 or died on Day 3. We label these 0, 1, 2 and 3 respectively.
Assemble these digits in order of the prisoners they represent, to construct a five digit number. That is the barrel ID of the poisoned barrel.
Log in to reply
@Praveen Kumar – Generalization of this results in:
If the king has N days and Y barrels and the poison kills anytime within n days (where N,n ∈ R+ and (N/n) results in a natural number), then let's say X prisoners suffice.
(N/n + 1)^k <= Y for the maximum value of k ; then X= k+1
@Praveen Kumar – Yes. The 72 hour case is correct. The generalization is almost correct; the (N/n +1)^k <= Y should be (N/n +1)^k < Y. That's because we can label the barrels from 0 to Y-1.
Great!
(My usual rant about minimum) To show that something is a minimum, we have to do 2 things.
1. Show that it can be achieved. (IE this is a proper bound)
2. Show that no lower number can be achieved. (IE this is the least/greatest bound)
You have done 1, by giving a construction that works for 22 people. However, you still have to explain 2, IE Why can't this work with 21 people using some approach that could be different from yours?
The real problem here is that this is a math problem that's being dressed up with a supposed real life example. But in real life there are many questions and ambiguities.
At the top of my list is this question: what's a fatal dose of the poison? We're told more or less that one barrel's worth will do it, but what if we mix all 500 barrels together? Will that still be a fatal dose? If not, then there's no need for any prisoners to die.
Log in to reply
My take on it is the bad barrel has several galllons of highly concentrated poison mixed into the wine, and one drop out of this barrel is a fatal dose. If you mixed this barrel with all the good barrels, diluting it 500 to 1, now 500 drops is a fatal dose. But that means a glass of wine from this mix is still fatal.
Clever! But we would have to further assume that the poison is so strong that 1/24 of a glass would kill a person (combining 1/24 of a glass from each of the 24 barrels that each prisoner has to sample every hour). Even just drinking 1 glass of wine per hour for 24 hours would seriously impair the prisoners' health. Much more would kill them. And the test is certain to fail if the prisoners die of alcohol poisoning!
What if one or more of the prisoners die from some other cause during the test?
It was told that poison takes 23 to 24 hours to kill a person... Then how you can consider a fixed time in this solution. . You have considered the time required in between 23rd and 24th hour is according to the time the person took the sample.
Make your question correct.
There is a ambiguity , how do you assume , a prisoner will die exactly after 23 Hours !!. It is clearly mentioned it takes between 23 and 24 hours . So it is very likely that first prisoner die after say 23 hours 11 min of consumption and second prisoner can take 23 Hours 53 Mins to die . On that case ? We don't know exact time to die .
2 prisoner (i,j) based grid solution works if we know exact time to die . We don't know that prisoner will die after 23 Hours !! Its very likely that first prisoner will die after 23 hours 11 mins ..and 2nd prisoner will die after 23 hours 58 min . In this case we need 5 prisoner to test . First 512 barrels ( lets take 512 instead of 500) are divided into 16 group ..each group consist of 32 different barrel . Now in hour 1st ( starting point) 5 prisoner will drink distinctly one spoon from barrel group1 ...32 different barrels in yes no Boolean combination ( like 00001 , 00010 , .....11111) . Then same 5 prisoner again test same way from barrel group2 at hour 1.5 ( in every 1.5 hours interval ...as 24 hours is divided in 16 group ..we have 1.5 hours slot) in same Boolean combination ( 00001 , 00010 , ....11111) . Same test will keep on going in each 1.5 hours of interval 16 times..test will end by 24th hours . then depending on the death combination and timing we can conclude which barrel had poison . Now if same poison can take 23:01 hours to kill one and 23:46 hours kill another prisoner , till we can easily conclude as we have 1.5 hours (90 mins) gap between two test .
Anybody have solution if two barrels are poisoned?
Cool solution...
This solution makes sense if we assume that the time the poison takes to kill is an open interval between 23 and 24 hours. If it's a closed interval, then dying in hour 23+I can very well be caused by row I-1... or am I igonring something?
This really is a bollox problem! Only one prisoner will die, so why not use 500? The other 499 may well compose odes in favour of their benevolent tyrant (if managed correctly!). If the king wants to be stingy but has a sense for science he could introduce 21 prisoners to a barrel each on the hour and hope one dies before too many have fun, but if the king has any sense of science he would operate on a strict one prisoner : one barrel ratio, otherwise too many variables are introduced. In fact, for the sake of thoroughness, I would commit to testing all 500 anyway - what if one or more prisoners is allergic to grapes? Better err on the side of caution . . . . and have a plan for magnificent spin if everyone at the feast dies! Machiavelli goes beyond math!
i think the text of the puzzle should contain smth like "STRICTLY between 23 and 24 hours"!! that would help a lot!
Yeah, but you would have no way of knowing that they actually died of poisonning... It could be an heart attack or simply an overdose of alcohol!
The first day you could order 23 prisoners to drink a jug of a mix consisting of 22 different wine samples each. Then after 24 hours one prisoner would die and the surviving 22 prisoners would then each drink a glass from one unique barrel of the suspected batch. After another 24 hours , just before the king's well deserved party starts, one more prisoner will surely die of poisoning and hence reveal the barrel containing the malicious content. No alcoholic coma, two casulties, such fun!
this makes no sense the poison kills whomever drinks it, it does not say it is diluted so this answer is incorrect. if the prisoner tries more than one barrel who's to say which barrel the poison came from? also it doesn'task: how many prisoners will die from this said test just that they need to test all the barrels
Log in to reply
Well, it can be determined which barrel the poison came from. It depends on what happens to the other prisoner. Each barrel is given a unique tag, eg. (1,3). (1,3) would mean the first prisoner drinks from that barrel on the first hour, and will die between 23 and 24 hours of time passed if it is the poisoned barrel. And the second prisoner will drink from the same barrel on hour 3, and will die between 26 and 27 hours of time passed if the barrel is poisoned.
If the prisoners die on the times described above, there is only one barrel with the matching tag (although there are multiple barrels the first prisoner drank from on the same hour, for example) and we can confirm (1,3) to be the poisoned barrel, as there is no other barrel able to kill the prisoners, both death times being the same.
I think using 2 prisoner is a bit small... and you will be wasting 250 barrels of wine with that... but nevertheless the quantity of poison intake is still need to be consider... the lesser concentration of the poison the longer its effect.
The answer is 1 the is no stipulation that the poison is tasteless or order less therefore one man would need to taste each barrel and identify the poisoned one. If the poison is odorless and tasteless and the taster dies then the king only needs to acquire 500 more barrels of pure wine and figure out the mess later he does have a banquet to host after all and wine does not spoil. Truly the answer could be 0 because again he is a king so scrap all 500 barrels of wine and just get 500 more, there are perks to being royalty and rich.
what if prisoner drinks too much that he cant drink more...
What if the poison is nullified by the other non poisoned wines? And non of the two prisoners die.
We will show that it is sufficient to use 2 prisoners to test 576 barrels (instead of just 500).
Given each barrel the distinct label ( i , j ) where 1 ≤ i , j ≤ 2 4 .
During the first day, at the beginning of the i th hour, we give the first prisoner wine from each of the barrels marked ( i , ⋅ ) .
During the first day, at the beginning of the j th hour, we give the second prisoner wine from each of the barrels marked ( ⋅ , j ) .
Then, if the first prisoner dies in the 2 3 + I hour, and the second prisoner dies in the 2 3 + J hour, we can conclude that the barrel ( I , J ) is poisoned.
Since it's clear that 1 prisoner isn't sufficient, hence the minimum is 2.
Note: Since we can start in the 0th hour, this approach works for 2 5 2 = 6 2 5 barrels using only 2 prisoners.