More poison testers
There is a king who wants to throw a party in 48 hours and he wants to serve a total of 700 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 up to 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.
Assumption : The time it takes for the poison to kill is unknown, and may differ from prisoner to prisoner, from case to case. We only know that it always kills a person within 24 hours after consumption.
Almost, but not quite the same, as this problem .
The answer is 6.
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
How do we know that 5 prisoners isn't sufficient?
Log in to reply
More generally, if the poison kills between t 0 and t 0 + Δ t hours, and we have a total of T hours available, and the number of poisoned barrels is N , we need precisely p = ⌈ lo g ⌊ 1 + ( T − t 0 ) / Δ t ⌋ lo g N ⌉ prisoners.
In this problem, p = ⌈ lo g ⌊ 1 + ( 4 8 − 0 ) / 2 4 ⌋ lo g 7 0 0 ⌉ = ⌈ lo g 3 lo g 7 0 0 ⌉ = 6 ; in the original poison testers problem , p = ⌈ lo g ⌊ 1 + ( 4 8 − 2 3 ) / 1 ⌋ lo g 5 0 0 ⌉ = ⌈ lo g 2 6 lo g 5 0 0 ⌉ = 2 .
Log in to reply
Please explain me how you got this. I mean what's the prove of this.
Ah yes, I was waiting for you to ask this :D
Any prisoner can yield information only once in 12 hours. Dead prisoners yield information only once. Therefore each prisoner can give only the information worth one ternary bit, i.e. differentiate between three possible outcomes.
The number of possible outcomes is 700, which requires information in the amount of lo g 3 7 0 0 ≈ 5 . 9 6 ternary bits , showing that we need at least six prisoners.
What a great problem... I love the elegance of the solution!
Any idea about what the answer would be if, say, instead of 2 days they had 3 days or 4 days? i.e. For p prisoners and d days, will the number of barrels you can accommodate be something like ( d + 1 ) p ?
Log in to reply
I just posted the generalized formula under Calvin Lin's comment... Yes, you generalization is valid.
Log in to reply
Very cool... I was fascinated with this problem for the last couple of days... Couldn't put my pen down trying to persuade myself that that generalization held for all (d,p). Thanks for posting! :^)
If we use similar logic to the one used by Mr. X here https://brilliant.org/problems/the-poison-testers/, then wouldn't the answer be 3? Label each of the barrels in a 9x9x9 (x,y,z) matrix. Starting each ith hour prisoner 1 will taste every barrel marked i in the x column. Each jth hour prisoner 2 will taste every barrel marked j in the y column and so on. The following day if, Prisoner 1 dies in the Ith hour, 2 in the Jth hour and 3 in the Kth hour then (I,J,K) must give the poisoned barrel.
Log in to reply
We don't know how fast the poison kills, except that it is less than 24 hours.
This is an elegant solution, Bravo! Although, as a chemist I feel obligated to point out that the poison is being diluted by a factor of approx. 243 times with this method. Also, they should all hope it's not in barrel N = 0 ... (or 728 if you are actually testing the full 729 barrels possible).
I'm missing something, Does the king only have 701 barrels of wine, or does he have an unlimited cellar with a poison barrel? It makes a difference if you only have to identify 700 unpoisoned barrels vs distinctly identifying the poisoned barrel.
Let's work this in simple terms. 720 has HCF's 24 and 30. Set out the barrels in a 24x30 grid. (20 will be empty but that doesn't matter) Each of six testers drinks from each barrel in 5 rows and 4 columns. One will die in the first 24 hours identifying the 20 barrels (or fewer) containing the poisoned one. It takes 5 testers to do a row and a column each from a 4x5 grid (one will only need to drink from a row or a column, but that doesn't matter). The prisoner who dies in the second 24 hours identifies the poisoned barrel. So six prisoners are sufficient.. (it's more complicated if more than one prisoner dies in each or either 24 hours) Hope this helps less mathematical folk at least get the gist of a partial solution!
Log in to reply
That won't work. Given a 4x5 grid, suppose tester A drinks from column 1 and row 1, and tester B drinks from column 2 and row 2. If A dies, then the poison is at (1,1); if B dies, it is at (2,2). But if they both die, we cannot tell the difference between (1,2) and (2,1).
There are ways around this, but they quickly lose elegance and simplicity :D
Log in to reply
Yes, it doesn't work in the worst case scenarios as to test the ambigous possibilities three might die in the first 24 hours only leaving three for the second testing, which would only narrow it down to 5 barrels not one. Seems this way would need 8 prisoners, so there are guaranteed 5 testers for the second testings, with one tester (as in the first 24 hours) drinking from one only of each pair of ambiguous possibilities. Still not bad for a much simpler method! And the King wouldn't need a maths degree to work it out!
What do you mean here "mixture of all barrels"? Can you specify which barrels the prisoners will drink?
Log in to reply
I wrote: "mixture of all barrels with n i = 0 ".
For instance, at t = 0 prisoner #4 drinks a mixture taken from all barrels where n 4 = 0 in the ternary representation. Specifically, this includes barrels 0 through 80, 243 through 321, and 486 through 566. If at t = 2 4 he is not dead yet, he gets a mixture from barres 81 through 161, 322 through 402, and 567 through 647.
The solution requires only one prisoner consecutively testing a sample of each of the 700 barrels at one or two minute intervals as such
Bi ... Ti = 0 ... Td ≥ 24hrs. + Ti
Bn ... Tn = Ti + 1min. ... Tdn = Td + Tn for a OneMinute-Interval of SampleTesting
OR Bn, Tn = Ti + 2min. ... Tdn = Td + Tn for a TwoMinute-Interval of Sample
At 1Minute-Intervals the Minimum Time for a Prisoner to Die is 24hrs( = 24:00:00 = 24hr00min.) representing the SampleTesting of Bi( = Initial Barrel, Barrel One[ 1]). The Maximum Time of Death would be 35hr39min. for the SampleTesting of Bn( = Final Barrel, Barrel SevenHundred[ 700]).
At 2Minute-Intervals the Minimum 'DeathTime' would still be 24hrs for Barrel#001 but 47hr18 min. for Barrel#700
Any SamplingInterval Over Two Minutes is NOt Viable Due To the King's 48hr-TimeConstraint
Log in to reply
This won't work because the prisoner will die within 24 hours, but we don't know when.
Log in to reply
Theoretically this Soln holds but In 'RealWorld'-Conditions the Answer of 27-699 Prisoners is the Best Answer. For IF the Poison were to take As LiTtle As ONe SEcond To Kill Then a PUrely Mathmatical Formula is NEgated by 'RealWorld' Trial&Error Testing: IF AFter ONe Second Testing 699 Barrels with 699 Prisoners and NoOne Dies THen Barrel #700 is the PoisonedBarrel and the "KNowing BEfore 48hrs-TimeConstraint" is NOooo Longer so 'Constraining.' Using my FiRst Soln of 700Barrels / 27Batches and a OneCup-Blend of 25Barrels yields the LEast Number of Prisoners using a Mixture of Mathematics and Intuition
With YOur Formula, IF a Prisoner Dies AFter 24hr00min05SEconds from the Beginning of the TestingPeriod THen Can You Tell WHich Barrel Is Responsible ANd WHich Prisoner Dies?
Log in to reply
Yes. The prisoner drank a mixture at t = 0 , but if that had been poisonous he would have died sooner. At t = 2 4 he drank the poison-- otherwise, he'd still be alive.
I agree with the FaceBookReply of " Ismail Asci : 27 " at 13:03 on 2017,01,15Sun
Take the 700 Barrels and Divide EVenly Into 28 Batches of 25 Barrels each
Next Take 27 Prisoners To Test 27 of the Batches by Blending the 25 Barrels into One Cup
In the First Round of Testing you will have 27 Prisoners Testing The EQuivalent Total of 675 Barrels with One 25-Batch( of Barrels) LeftOver for a Potential 2nd Round of Testing
AFter the First 24hrs IF One of the 27 Batches in the FirstRound Test Kills a Prisoner THen a)the "LeftOver Batch" Needs NOt Be Tested and b)You NOw have 26 Prisoners to Test ONe of the FirstRound Batches( COntaining One Poisoned Barrel In a Set of 25).
IF No Prisoners Die in the FirstRound Test THen You NOw have 27 Prisoners Testing the "LeftOver Batch" of 25 Barrels in the Second 24hr-Period
Log in to reply
That would require 27 prisoners for testing. The solution I posted requires only 6.
Log in to reply
With YOur Formula, IF a Prisoner Dies AFter 24hr00min05SEconds from the Beginning of the TestingPeriod THen Can You Tell WHich Barrel Is Responsible ANd WHich Prisoner Dies?
The following solution allows for checking up to 729 barrels.
Label the barrels N = 0 … 7 2 8 . Write N in ternary notation, i.e. N = 2 4 3 n 5 + 8 1 n 4 + 2 7 n 3 + 9 n 2 + 3 n 1 + n 0 with n i = 0 , 1 , 2 .
Take six prisoners, numbered 0 … 5 .
At t = 0 hours, feed each prisoner i a mixture of wine from all barrels where n i = 0 .
At t = 2 4 hours, feed each surviving prisoner i a mixture of wine from all barrels where n i = 1 .
Now let p i = ⎩ ⎪ ⎨ ⎪ ⎧ 0 1 2 if prisoner i died in the first 24 hours ; if prisoner i died in the last 24 hours ; if prisoner i survives . Interpret the p i as ternary representation of an integer P ; that is, let P = 2 4 3 p 5 + 8 1 p 4 + 2 7 p 3 + 9 p 2 + 3 p 1 + p 0 . Then P is the label of the poisoned barrel.