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. Pratyush Rathore5:58 PM, March 13, 2011

    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. tejasvph7:37 PM, March 13, 2011

    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. sid10:08 PM, March 13, 2011

    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. chera12:14 AM, March 14, 2011

    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. Mehul8:04 PM, March 14, 2011

    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. Pratik Poddar1:01 AM, March 16, 2011

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

    ReplyDelete
  7. Siddhartha8:49 AM, July 05, 2011

    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. Siddhartha8:52 AM, July 05, 2011

    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. Pratik Poddar1:41 PM, July 06, 2011

    This comment has been removed by the author.

    ReplyDelete
  10. Pratik Poddar1:48 PM, July 06, 2011

    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. Vivek Jha10:15 AM, March 07, 2012

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

    ReplyDelete
  12. Vivek Jha10:16 AM, March 07, 2012

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

    ReplyDelete
  13. Pratik Poddar5:15 AM, May 25, 2012

    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. DianeG10:21 AM, February 01, 2014

    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
  15. MathMack2:36 AM, March 28, 2017

    I have a variation of the problem I would like to have solved.

    Problem: 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?

    ReplyDelete

Post a Comment

Popular posts from this blog

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially)
Read more