King's Poisonous Wine II
Source: Puzzle Corner, Australian Mathematical Society
Problem: The king has 500 barrels of wine, but one of them is poisoned. Anyone drinking the poisoned wine will die within 12 hours. The king has four prisoners whom he is willing to sacrifice in order to find the poisoned barrel. Can this be done within 48 hours?
Related Problem:
King's Poisonous Wine Puzzle - CSE Blog
Update (16/03/2011):
Solution posted by Tejas Hiremani (IITB EE Alumnus, Goldman Sachs Quant), Siddhant Agarwal (IITB EE Senior Undergraduate), Mehul Tikekar (IITB EE Alumnus, MIT PhD Candidate) and Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) in comments!
Problem: The king has 500 barrels of wine, but one of them is poisoned. Anyone drinking the poisoned wine will die within 12 hours. The king has four prisoners whom he is willing to sacrifice in order to find the poisoned barrel. Can this be done within 48 hours?
Related Problem:
King's Poisonous Wine Puzzle - CSE Blog
Update (16/03/2011):
Solution posted by Tejas Hiremani (IITB EE Alumnus, Goldman Sachs Quant), Siddhant Agarwal (IITB EE Senior Undergraduate), Mehul Tikekar (IITB EE Alumnus, MIT PhD Candidate) and Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service) in comments!
Not possible, the maximum number of barrels from which you can find out one poisonous barrel with four prisoners and four turns is 209.
ReplyDeleteThis is actually a recursion,
f( x, y ) = f(x, y - 1) + x * f(x -1, y - 1);
where f (x , y) is the maximum number of barrels which can be filtered out with x prisoners at disposal, and y turns.
base case being f(x, 0) = f(0, y) = 1
So, if there are 209 prisoners,
I will give all the four prisoners 34, bottles each to drink. If one of them dies, I have to sort out the remaining 34 bottles with 3 prisoners, otherwise, 73 bottles with four prisoners in three turns, and so on...
I have a solution ... too long to explain but I got a general soln as ( 1 + k )^n where k is number of steps and n is number of people so in this case as 500 < 625 it is possible
ReplyDeleteI agree with tejas. But I think it should be (1+k)^n - 1 (Assuming that there are infinite barrels and the null case is not allowed). Let f(n,k) denotes the number of barrels that can be checked by n persons and k time slots. Basically the following recursion holds:
ReplyDeletef(n,k)-f(n,k-1)=nC1*[f(n-1,k-1)+1]+
nC2*[f(n-2,k-1)+1]+
...
nCn*[f(0,k-1)+1]
where
f(0,k) = 0 for all k, and
f(n,1) = 2^n - 1 for all n.
Hence the answer.
can we not think this way:
ReplyDeletethere are k turns and n persons.
each person has k+1 possibilities , as he will either survive or die after one of the k turns.
so, total number ways in which the n person die is (k+1)^n.
corresponding to each of these possibilities, we can associate a one to one wine mapping.
You split each barrel into how many ever prisoners you have. Now you carry out the tests on each prisoner independently.
ReplyDeleteFor one prisoner case, prisoner has to try one barrel at a time. So each barrel gets a tag "k" which means it is going to be tried in the k'th trial. So you can have a total of K+1 tags (K = total number of trials, tag=0 means barrel not tried at all).
Now, each barrel is going to get independently tagged by N prisoners. Hence, you can have (K+1)^N unique tags.
Thanks for your solutions. Needless to say, all except Pratyush are correct :)
ReplyDeleteWe can also view it this way, any number from 1 to 500 (actually 1-625, or 0-624 doesn't matter) can be written down in base 5, with numbers 0,1,2,3,4. if a bottle number x is written as abcd, where a,b,c,d are between 0-4(natural numbers) then the bottle x will be given to prisoner 1 at ath trial prisoner 2 at bth trial and so on. Seeing the deaths of the prisoners, we can find a,b,c,d of the poisoned bottle and thus x, and thus we can find the poisoned bottle.
ReplyDeleteWe can also view it this way, any number from 1 to 500 (actually 1-625 or 0-624 doesn't matter) can be written in base 5. If bottle number is x, it is written as abcd, where a,b,c,d are natural numbers from 0-4. Seeing the deaths of prisoners at various stages, we can find a,b,c,d of poisoned bottle and thus find x, ie the number of poisoned bottle.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteRemoved my last comment because of typo:
ReplyDelete@Siddhartha..Well just another way of saying that the number of n bit (k+1)-ary numbers are (1+k)^n - 1
What if say two bottles were poisoned, what is the minimum number of prisoners required then?
ReplyDeleteWhat is the min number of prisoners required if two bottles were poisoned rest remaining the same?
ReplyDeleteInteresting problem Vivek.
ReplyDeleteLets say the first person dies in the ith turn,
then till ith turn, we would have evaluated i^n bottles, and after that (k-i+1)^(n-1) bottles.
So, total number of bottles that can be evaluated | first prisoner dies in ith turn = (k-i+1)^(n-1) + i^n
Here, k = 4 (Number of turns of time)
Number of bottles to be evaluated = 500
So, find n (number of prisoners) such that (500 < (5-i)^(n-1) + i^n) for all 1 <= i <= 4
Find minimum n such that
500 < 4^(n-1) + 1
500 < 3^(n-1) + 2^n
500 < 2^(n-1) + 3^n
500 < 4^n + 1
So,
Find minimum n such that
500 < 4^(n-1) + 1 and
500 < 3^(n-1) + 2^n
Minimum n satisfying the two inequalities is n = 7
Hope that solves your problem. Cheers! :)
I have a variation of this puzzle that I'm really struggling with, any ideas ?
ReplyDeleteKing Petras is the ruler of a medieval empire. Tomorrow he will celebrate the marriage of his eldest daughter Ailín. One problem - the evil count Pierre Foutou has poisoned one of the barrels holding the wine that will accompany the feast. King Petras however has an unlimited supply of political prisoners who can "taste test" the wine for him.
The poison exhibits no symptoms until death. Death occurs within twenty four hours after consuming even the minutest amount of poison - there will be no chance for any prisoner to be "used" more than once.
What is the smallest number of prisoners required to drink from the barrels to be absolutely sure to find the poisoned barrel, for the following number of barrels?:
i) 1500 , answer =
ii) 58 , answer =
iii) 450 , answer =
1500, answer = 11
Delete58, answer = 6
450, answer = 9
Detailed answer at King's Poisonous Wine Puzzle - CSE Blog
DeleteI have a variation of the problem I would like to have solved.
ReplyDeleteProblem: The king has 500 barrels of wine, but one of them is poisoned. Anyone drinking the poisoned wine will die between 23 and 24 hours. The king has 2 prisoners whom he is willing to sacrifice in order to find the poisoned barrel. All testing of the barrels must be complete within 12 hours of testing because you only have access to the barrel room for 12 hours. Can the poison be located at the end of a 48 hours?