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!

Comments

  1. Not possible, the maximum number of barrels from which you can find out one poisonous barrel with four prisoners and four turns is 209.

    This 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...

    ReplyDelete
  2. 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

    ReplyDelete
  3. I 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:

    f(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.

    ReplyDelete
  4. can we not think this way:

    there 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.

    ReplyDelete
  5. You split each barrel into how many ever prisoners you have. Now you carry out the tests on each prisoner independently.
    For 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.

    ReplyDelete
  6. Thanks for your solutions. Needless to say, all except Pratyush are correct :)

    ReplyDelete
  7. We 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.

    ReplyDelete
  8. We 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.

    ReplyDelete
  9. This comment has been removed by the author.

    ReplyDelete
  10. Removed my last comment because of typo:

    @Siddhartha..Well just another way of saying that the number of n bit (k+1)-ary numbers are (1+k)^n - 1

    ReplyDelete
  11. What if say two bottles were poisoned, what is the minimum number of prisoners required then?

    ReplyDelete
  12. What is the min number of prisoners required if two bottles were poisoned rest remaining the same?

    ReplyDelete
  13. Interesting problem Vivek.

    Lets 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! :)

    ReplyDelete
  14. I have a variation of this puzzle that I'm really struggling with, any ideas ?

    King 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 =

    ReplyDelete

Post a Comment