tag:blogger.com,1999:blog-4115025577315673827.post7757185472919893050..comments2020-05-20T14:21:54.596+05:30Comments on CSE Blog - quant, math, computer science puzzles: King's Poisonous Wine IIPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger17125tag:blogger.com,1999:blog-4115025577315673827.post-12761180230723253552017-03-28T02:36:33.998+05:302017-03-28T02:36:33.998+05:30I have a variation of the problem I would like to ...I have a variation of the problem I would like to have solved.<br /><br />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? <br /><br />MathMackhttps://www.blogger.com/profile/14024070307233881201noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-11584589985497196582014-06-22T22:49:30.342+05:302014-06-22T22:49:30.342+05:30Detailed answer at King's Poisonous Wine Puzzl...Detailed answer at <a href="http://www.cseblog.com/2009/10/kings-poisonous-wine.html" rel="nofollow">King's Poisonous Wine Puzzle - CSE Blog</a>Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-60562721020122868312014-06-22T22:48:22.136+05:302014-06-22T22:48:22.136+05:301500, answer = 11
58, answer = 6
450, answer = 9
1500, answer = 11<br />58, answer = 6<br />450, answer = 9<br />Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-49783390759797238172014-02-01T10:21:56.097+05:302014-02-01T10:21:56.097+05:30I have a variation of this puzzle that I'm rea...I have a variation of this puzzle that I'm really struggling with, any ideas ?<br /><br />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.<br /><br />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.<br /><br />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?:<br /><br />i) 1500 , answer = <br />ii) 58 , answer = <br />iii) 450 , answer =DianeGhttps://www.blogger.com/profile/10530101217706780443noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-88863119873823323822012-05-25T05:15:50.821+05:302012-05-25T05:15:50.821+05:30Interesting problem Vivek.
Lets say the first pe...Interesting problem Vivek. <br /><br />Lets say the first person dies in the ith turn,<br />then till ith turn, we would have evaluated i^n bottles, and after that (k-i+1)^(n-1) bottles.<br /><br />So, total number of bottles that can be evaluated | first prisoner dies in ith turn = (k-i+1)^(n-1) + i^n<br /><br />Here, k = 4 (Number of turns of time)<br />Number of bottles to be evaluated = 500<br /><br />So, find n (number of prisoners) such that (500 < (5-i)^(n-1) + i^n) for all 1 <= i <= 4<br /><br />Find minimum n such that <br />500 < 4^(n-1) + 1<br />500 < 3^(n-1) + 2^n<br />500 < 2^(n-1) + 3^n<br />500 < 4^n + 1<br /><br />So, <br />Find minimum n such that <br />500 < 4^(n-1) + 1 and<br />500 < 3^(n-1) + 2^n<br /><br />Minimum n satisfying the two inequalities is n = 7<br /><br />Hope that solves your problem. Cheers! :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-27785281691388138762012-03-07T10:16:30.355+05:302012-03-07T10:16:30.355+05:30What is the min number of prisoners required if tw...What is the min number of prisoners required if two bottles were poisoned rest remaining the same?Vivek Jhahttps://www.blogger.com/profile/00394691204629747462noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-31513246942212394922012-03-07T10:15:33.247+05:302012-03-07T10:15:33.247+05:30What if say two bottles were poisoned, what is the...What if say two bottles were poisoned, what is the minimum number of prisoners required then?Vivek Jhahttps://www.blogger.com/profile/00394691204629747462noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-36822362567130282402011-07-06T13:48:41.189+05:302011-07-06T13:48:41.189+05:30Removed my last comment because of typo:
@Siddhar...Removed my last comment because of typo:<br /><br />@Siddhartha..Well just another way of saying that the number of n bit (k+1)-ary numbers are (1+k)^n - 1Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-38166447703655800902011-07-06T13:41:40.159+05:302011-07-06T13:41:40.159+05:30This comment has been removed by the author.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-6669091071591075872011-07-05T08:52:04.519+05:302011-07-05T08:52:04.519+05:30We can also view it this way, any number from 1 to...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.Siddharthahttps://www.blogger.com/profile/05472231919937474215noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-18429989258204422052011-07-05T08:49:13.654+05:302011-07-05T08:49:13.654+05:30We can also view it this way, any number from 1 to...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.Siddharthahttps://www.blogger.com/profile/05472231919937474215noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-76125991579397307612011-03-16T01:01:37.263+05:302011-03-16T01:01:37.263+05:30Thanks for your solutions. Needless to say, all ex...Thanks for your solutions. Needless to say, all except Pratyush are correct :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-38041887871326850942011-03-14T20:04:31.823+05:302011-03-14T20:04:31.823+05:30You split each barrel into how many ever prisoners...You split each barrel into how many ever prisoners you have. Now you carry out the tests on each prisoner independently.<br />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).<br />Now, each barrel is going to get independently tagged by N prisoners. Hence, you can have (K+1)^N unique tags.Mehulhttps://www.blogger.com/profile/11244771890702756407noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-8463146938713638582011-03-14T00:14:48.324+05:302011-03-14T00:14:48.324+05:30can we not think this way:
there are k turns and ...can we not think this way:<br /><br />there are k turns and n persons.<br /><br />each person has k+1 possibilities , as he will either survive or die after one of the k turns.<br /><br />so, total number ways in which the n person die is (k+1)^n. <br /><br />corresponding to each of these possibilities, we can associate a one to one wine mapping.cherahttps://www.blogger.com/profile/15883972329291461469noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-67303922122872609362011-03-13T22:08:39.894+05:302011-03-13T22:08:39.894+05:30I agree with tejas. But I think it should be (1+k)...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:<br /><br />f(n,k)-f(n,k-1)=nC1*[f(n-1,k-1)+1]+<br /> nC2*[f(n-2,k-1)+1]+<br /> ...<br /> nCn*[f(0,k-1)+1]<br />where <br />f(0,k) = 0 for all k, and<br />f(n,1) = 2^n - 1 for all n.<br />Hence the answer.sidhttps://www.blogger.com/profile/04179126136399818676noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-77753099768058907102011-03-13T19:37:46.827+05:302011-03-13T19:37:46.827+05:30I have a solution ... too long to explain but I go...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 possibletejasvphhttps://www.blogger.com/profile/14026392904050871300noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-60548522954547762942011-03-13T17:58:57.178+05:302011-03-13T17:58:57.178+05:30Not possible, the maximum number of barrels from w...Not possible, the maximum number of barrels from which you can find out one poisonous barrel with four prisoners and four turns is 209.<br /><br />This is actually a recursion, <br />f( x, y ) = f(x, y - 1) + x * f(x -1, y - 1);<br />where f (x , y) is the maximum number of barrels which can be filtered out with x prisoners at disposal, and y turns.<br /><br />base case being f(x, 0) = f(0, y) = 1<br />So, if there are 209 prisoners, <br />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...Pratyush Rathorehttps://www.blogger.com/profile/14085124243567744668noreply@blogger.com