|
||||
|
Title: Hard: Criminal Cupbearers Post by Cody Batt on Jul 25th, 2002, 12:22am The king forces each of the 1000 prisoners to drink from 10 different wine bottles. He numbers the wine bottles from one to 1000 and records the number corresponding to the wine bottle that the prisoners drink from. He does this in such a way that the set of tested wine bottle numbers is unique for each prisoner. He waits for a month and ten prisoners drop dead. He reviews his records and finds that each of the ten decomposing prisoners drank from the same bottle which therefore contained the poison. Thus he identifies the poisoned wine which, being evil, he uses to poison the liquor supply of the neighboring queen. Here's some code to fill in the details of how the King recorded which bottles the prisoners drank from: int prisoner[1000][10]; for ( int i = 0; i < 1000; i++ ) for ( int j = 0; j < 10; j++ ) prisoner[i][j] = (i + j * 10) % 1000; |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Vineet Kumar on Jul 25th, 2002, 2:41am I wasn't sure about the wording of this question. If he's using 1000 prisoners, he should just have each drink from one bottle. After one month (only 4 weeks...) one prisoner dies. That one had the poisoned bottle. I assumed that since this is trivially easy (and better than 10 deaths in 5 weeks), that the "correct" solution really used only 10 prisoners total rather than killing 10 out of 1000 used. If the timing is accurate (i.e. you die exactly one month after drinking poison) I'd aim for a solution based on giving each prisoner a different cocktail of wines each day and watching for when they die (and they'll all die!). It's a matter of defining the cocktails each day such that watching the order in which the prisoners die allows you to single out the unique "path" that the poisonous bottle traversed through the cocktails. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Viorel Canja on Jul 25th, 2002, 4:09am I too wasn't sure about the wording but I believe the king uses only 10 prisoners. Here is a solution : Let's consider a numbering of the bottles and prisoners .We will solve the problem recursively.If we have a solution for bottles 1..500 and prisoners 1..9 we can construct a solution for the problem in the following way: Prisoner 10 will drink a cocktail from bottles 1..500. If he/she dies then the poisoned bottle is among bottles 1..500 and the problem is solved by the info we have from the other 9 prisoners. If he/she lives after 1 month the bottle is among bottles 501 .. 1000 . In this case the problem can be solved if prisoners 1..9 add to their cocktails wine from coresponding bottles in the set 500 .. 1000 . For example if a certain cocktail contained wine from bottles x y z it will contain wine from bottles x y z and x+500 y+500 z+500. The solution for k prisoners and 2**k bottles : k != 1 reduce to smaller problem k == 1 the prisoner drinks from bottle 1 |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Vineet Kumar on Jul 25th, 2002, 3:26pm Okay, I got this one. I went from the bit I mentioned earlier about watching each bottle's unique path through the prisoners' cocktails and it got me thinking about a method of assigning bottles to prisoners rather than prisoners to bottles. What I mean is instead of saying "the first prisoner drinks from half of them, the next from 1/4 of them ..." or some such similar method I tried to figure out how the bottles could be uniquely identified. Each can be assigned to a unique set of prisoners chosen from the group of 10, because there are 2^10 =1024 possible sets of prisoners. So view each prisoner as a bit and each bottle, numbered 1 to 1000 is tasted by the prisoners whose bit is 1 in the binary representation of the bottle's serial number. So that's the theory. As for just the plain method, without much explanation: Line up the prisoners in order, each representing a bit. Number each bottle 1 to 1000. For each bottle, convert the serial number to binary, and give a sip to each prisoner corresponding to a 1 bit in the bottle number. After a month, see who dies. Each dead prisoner represents a "1" bit in the poisonous bottle's serial number. For example, if prisoners number 2, 5, 7 and 8 die, that looks like this: prisoner # 0 1 2 3 4 5 6 7 8 9 bit # 0 0 1 0 0 1 0 1 1 0 Assuming we're numbering with 0-9 instead of 1-10 and that 0 is the least significant bit, the number of the poisonous wine bottle is the sum of 2^(prisoner number) for each dead prisoner. In the above example, 0110100100 converted to decimal is 420, so bottle number 420 is the poison. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Cody Batt on Jul 25th, 2002, 3:49pm Yeah, I misunderstood the problem, but somehow at 2:30 in the morning, what I was thinking made sense to me. When I thought about it today, I realized how dumb that solution was. The moral: trying to solve hard puzzles + insomnia = bad. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Json921 on Jul 25th, 2002, 4:04pm How about, just make sure that one of the ten prisoners involved in the taste test was the one who poisoned the bottle? :-/ |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Kyalu on Jul 25th, 2002, 8:15pm If the symptoms show up in exactly one month's time. You can take 10 prisoners and have each of them drink 100 bottles 2 hours apart. Watch them closely after 4 weeks. The second one of them shows symptoms you know it was the bottle they drank one month ago at that hour. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Cathy on Jul 25th, 2002, 9:13pm Some of the above answers are correct. But I believe the most systematic solution would be using combination. Since there are 10 prisoners, there would be a total of over 1000 different combination of prisoners, and each one is unique. i.e. 10 choose 1 (10C1) +10 choose 2 (10C1) +10C3+...+10C5 + ...+10C9+10C10 = 10+45+120+210+252+210+120+45+10+1=1032 (I don't have an handy calcultor with me). So, all the king has to do is to assign a different wine to a different combination of those poor suckers. :-/ e.g Prisoner combo 1,6,7 can be assigned to drink wine #345, and after one month, if and only if all 1, 6,7 die, then wine #345 is the piosonous one. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Frothingslosh on Jul 25th, 2002, 9:20pm Unfortunately, this question is extremely poorly worded. Half of the problem seems concerned about using less than 1000 prisoners, but the other half seems to be concerned about killing ten or less. There are many ways to do this - the simplest would be to use 999 prisoners to taste the wine and see who, if anyone, died. If no one died the poison would be in bottle 1000! But what the question is trying to coax you into telling them, particularly by the serious hint of the number 10, is to give the prisoners wine made from a mix of drops from different bottles, based on a binary code (standard binary is what the author is looking for but any binary code, such as the grey code, would work as well). The prisoners represent the binary bits in a number, for each bottle of wine some prisoners get a drop of wine if thier binary value matches a 1 bit in the bottle number. for example, for bottle number 6 the third and second prisoner get a drop from that bottle. For bottle number 123 a drop goes to prisoner 7,6,5,4,2 and 1 (binary 1111011=base 10 123). In a month, the dead prisoners are treated as binary 1 and the live prisoners as binary 0 to computer the poisoned bottle. Unfortunately, it's a bad puzzle for several reasons. The empasis on 10 points too strongly to the desired answer (2 to the power 10 is 1024, just slightly higher than the number of bottles of wine), it's poorly stated since using 1000 (or 999) prisoners would end up killing only 1 prisoners (and using less wine). Most importantly, the intended solution is a bad real world solution because the desired answer provides no redundancy or confirmation of accuracy. If 999 or 1000 prisoners were used and 2 prisoners die, the king would be cautious, and either discard 2 bottles or retest the two bottles in question. With only 10 prisoners, in most cases if a prisoner happens to die "a natural death" when the poisoned prisoners are cashing in, then the king will in most cases get a valid bottle number, but it will be the wrong bottle (for example, if the first prisoner dies from a heart attack on seeing prisoners 2, 3 and 4 die, the king will think the poison was in bottle 15. He will discard that and eventually drink bottle 14 and be poisoned. Knowing this he will likely use 999 or 1000 prisoners and end up poisoning only one, no matter how proud of the binary solution the geek who wrote this is. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Andrew Ooi on Jul 25th, 2002, 10:09pm I disagree with the post about it not very being well worded. It is worded fine. It's rubbish to say that most if the time only 1 die because there is (almost) as many 0s as 1s in the binary solution so on average half will die. Actually my main bone is that the problem statement is not optimised: you can actually do it with at most 9 deaths and in 4 weeks. 9 deaths being because 1000<1024 and using the binary method, it is not possible to have 1111111111 :> |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by tonza on Jul 25th, 2002, 10:53pm If he had only 10 prisoners to be used in testing... first he gives one bottle to every prisoner. next he pairs them and gives one bottle to every pair, does this until every possibly configuration has been used. then he groups them in three and gives one bottle to every group, again does this until every combination is used. next groups of four and so on until every bottle is tested. then he waits for a month and sees how many prisoners die and which ones of them. - tonza |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Frothingslosh on Jul 25th, 2002, 11:17pm Andrew, you post seems to be responding to me. I certainly didn't say that in a binary solution only one would die; on the average about 5 will die. Only in a 999 or 1000 prisoner solution will only 1 die. But if the goal is to limit deaths (with the added benefits of using less wine and getting a warning if someone extra dies of natural causes), then one drop per each of 999 or 1000 prisoners is the way to go. Sure, 1000 is less than 1024 (2^10), but that doesn't mean you can get away with using 9 prisoners: 1 prisoner can test betwen two bottles, asuming he takes a drop from only 1. 2 prisoners can test up to 4 bottles (2^2). 3 prisoners can test up to 8 bottles (2^3) 4 prisoners => 16 bottles (2^4) 5 prisoners => 32 bottles (2^5) 6 prisoners => 64 bottles (2^6) 7 Prisoners => 128 bottles (2^7) 8 prisoners => 256 bottles (2^8) 9 prisoners can test between no more than 512 bottles (2^9) Once you exceed 512 bottles you need that 10th prisoner to do the test the binary way. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Andrew on Jul 26th, 2002, 2:56am Frothingslosh, I guess I skimmed your reply too fast, upon re-reading it, I get what you are saying :> mea culpa Also, perhaps you didn't understand why I insist on 9 prisoners will die. You are right in that 10 prisoners will have to put their lives to the line, but <b>only 9 of the 10 will end up dying</b>. In the question the phrase is "he needs to murder no more than 10 prisoners", I am saying that it should read "he needs to murder no more than 9 prisoners". In fact, he will need to risk 10 prisoners but murder not more than 9. If you accept the binary solution, then you will agree that there that the ones marked 1 in the binary solution will be the one to die right? E.g. if bottle no 1010101011 is poisoned, prisoner no 10,8,6,4,2,1 will die to prove it. What I am saying is that the only way ALL 10 prisoners die is that there is a possible combination of 1111111111, which can be made impossible if there are only 1000 bottles. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Rhaokarr on Jul 26th, 2002, 9:48pm Hell, you're all risking the lives of potential torturees. Using thirty prisoners, I can ensure that three and three only will die. Prisoners 1 through 10 drink a little out of each hundred, so prisoner #1 tastes bottles 1-100, prisoner #2 tastes bottles 101-200, etc. Prisoners 11-20 drink a little out of each decade, so prisoner #11 tastes bottles 1-10, 101-110, 201-210, prisoner #12 tastes bottles 11-20, 111-120, etc Prisoners 21-30, the 'units' prisoners, go one step further down, so prisoner #21 tastes bottles 1, 11, 21, 31, prisoner #22 tastes bottles 2, 12, 22, 32, etc. Basically you set up your prisoners into a 'hundreds', a 'tens' and a 'units' group. Make it even easier - tattoo '100' in big numbers on prisoner #1, '200' on prisoner #2, '10' on prisoner #11, etc Wait the month, see which three show the effects. Add up the numbers on the tattoos. Throw away the referenced bottle, then send the severed heads of the three prisoners to the queen who tried to poison me in the first place. The advantages of this method are that more wine is preserved (every bottle loses three sips, as opposed to losing up to 9 sips in some cases with the binary method, dammit!), and more lives are saved such that I can torture them to my evil whims at a later date, perhaps even walling a few up to satisfy my twisted emotional cravings. Well... with the binary solutions (or Cathy's solution), it's *possible* to have less lives taken, but this solution has a *maximum* of three lives taken. This more than fulfils the requirements outlaid by the problem (murder no more than ten). The disadvantage of this solution is that it requires thirty prisoners rather than ten prisoners. Now, note that the question states that I am an evil KING. Not an evil Marquis, nor an evil Count, not even an evil Baron, let alone an evil sherrif or evil councilman. If I can't wrongfully imprison 30 of my subjects, then obviously my army is against me, and I'd best leave my wine behind, and take as much money with me as I run hiding into exile. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Andrew Ooi on Jul 29th, 2002, 8:48am The point is probably not to use more than 10 prisoners and optimize for the minimum no of deaths, coz if not you can use 1000 prisoners and then only 1 dies :) The question should be rephrased not risk the life of more than 10 prisoners instead of murder not more than 10 prisoners - coz there is a solution that risk 10 prisoners but will only murder 9 at most [ William please take note ;D ] |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by fredh on Jul 29th, 2002, 10:13am I was really intrigued by this riddle and I have an answer that uses only 10 prisoners, and only 1-3 will die. Simply arrange the 1000 bottles in a 10x10x10 cube. each prisoner is assigned the same row on each of the x, y and z axis's. ex: prisoner 1 is assigned to row x1, y1, z1 etc... The poison takes 4 weeks to appear, the king can drink in 5 weeks. Therefore get the X axis to drink first, then 2 days later, get the Y axis to drink, then 2 days later get the z axis to drink. In 4 weeks, someone in the x axis is going to die. In 4 weeks + 2 days, someone on the y axis is going to die. If no one died, then it was the person on the x axis who died 2 days ago that drank the poison. In 4 weeks + 4 days, you will have the z axis. Now you have your x, y, z co-ords which points to the exact bottle. What do you guys think? I hope the explanation was clear enough. Enjoy! |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Alex Harris on Jul 29th, 2002, 1:01pm Thats a cute answer fredh but its slightly off. If different people die on the 4week and 4 week + 2 days then nobody dies on 4 weeks + 4 days you're left with 2 possiblities for the z axis. If we extend that logic about the exact timing of the poison then we will just need 1 prisoner who drinks from each bottle at 1 minute intervals then we know which bottle it is by the time of the day one month later that he dies. The binary solution is the "right" answer despite the miswording but I'd say its so heavily advertised that it really doesn't belong in "hard". |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Rhaokarr on Jul 30th, 2002, 2:44am I want my tattooed prisoners, dammit! Again, I refer to my last paragraph - I am an evil KING! ;) Although I may not have 1000 hale and hearty prisoners in my filthy dungeons, I'm sure I can rustle up 30. And I'm not wasting as much wine as the binary monarchs are... |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Razor_Gaunt on Aug 1st, 2002, 1:25pm I agree with the earlier posts that this question does not explain the king's motives very clearly. I had thought originally that since he was an evil king that the emphasis was on having the fewest prisoners involved and not the fewest prisoners killed. So I came up with the binary solution fairly quickly, possibly 9 dead prisoners, 10 prisoners involved. My other friend thought it was the goal to kill the fewest so he came up with the matrix solution, 100 x 100 matrix. 2 prisoners dead, 200 involved. (We both thought of the 999 prisoner solution and thought that was cheesy. We also assumed that the poison was not precise, that is it killed you in about 4 weeks, not 4 weeks to the minute exactly as some were saying. So I don't believe that time is a usable scale in determining the poisoned bottle.) I guess my question is, is there a consensus that there isn't a right answer? |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Court Jester on Aug 1st, 2002, 2:38pm After developing my own solution and reading through the possible solutions posted I think that one or two were awfully close. Below is what I came up with. This solutions kills a minimum of one prisoner and a maximum of three (if you're a risk taker) or four (if you want there to be no uncertainty left). Each of the 10 prisoners drinks from 100 bottles: i.e. Prisoner one drinks from 1-100, prisoner two drinks from 102-200, etc. Next each prisoner is going to drink 11 bottles from each of the other groups of 100 that he hasn't already sampled from and that haven't yet been sampled by a third prisoner: i.e. Prisoner 1 drinks from 11 of each of the other prisoner's 100, Prisoner 2 drinks from a different 11 of each of the other prisoner's, etc.--this leaves one bottle from each group of 100 that only one prisoner has drunk from (hence, in one month's time should only one prisoner die you know it's the one bottle he alone drank from). Now we have a lot of groups of 11 bottles. For each group of 11 bottles, five prisoners (who haven't had a drink from the group yet) will each drink from 2 different bottles. Once again this leaves one bottle from each group of 100, but in this case only two prisoners have drunk from it. So, if only two prisoners die, the bottle is identified. Now we, have an extremely large number of 2 bottle groups. The last part is easy with two possibilities: Option 1: Let 1 prisoner who hasn't had a drink from either bottle drink from one of them. If after the one month has passed and he hasn't died it's the other bottle, if he has died as well then it's the bottle he drank from. Option 2: Let 2 prisoners who haven't had a drink from either bottle drink from one each. Whichever one dies identifies the tainted bottle. There is no time delay between each group being drunk from. This is all done in one sitting which, allowing for the large number of combinations being produced, could take a week's time. After all the drinking has been completed the King sits back for the next month and waits to see how many prisoners die: One prisoner if it's the bottle that each prisoner alone drank from. One more prisoner if the bottle made it into one of the groups of 11, but was the sole bottle from that group of 11 left after five more prisoners each drank 2 bottles from said group. Should it not end there then, sadly enough, a third prisoner has also died and it's now been narrowed down to 2 bottles. This finally leaves the risk factor should the king choose it. If only one prisoner drank from a single bottle from the group of two and lives that the other bottle should be tainted--if he dies then the bottle is positively identified. Or the less risky path of having two prisoners each sample a different one of the two and whichever one croaks has identified the bottle. Enjoy!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by AlexH on Aug 2nd, 2002, 7:42am Assume the only information we get after our taste testing is whether or not each individual prisoner is poisoned and assuming we can't detect partial poisoning. In other words we're not playing tricks by timing the poison or anything with attempting to detect a partial poisoning. Given this assumption we can't do better than having at most 8 of the 10 prisoners die. In order for us to determine the bottle from which prisoners die, we must be able to give each bottle a unique lable from {not dead, dead}^10, or equivalently {0,1}^10. Since we have 1000 bottles we must have 1000 different labels. There are 1024 lables of which 1013 have at most 8 1s in them, but there are only 968 labels with 7 or fewer 1s which isn't enough. Killing 8 in the worst case is the best we can do. (Average 4.916) Edited to add: Court Jester your solution required a second round of tasting after you narrowed the situation to 2 bottles. This second round will take another month and put us past the deadline. The other problem you have is that your method will confuse certain cases. For example: when prisoner 1 and 2 die, was it because the poison was in big group 1 and small group 2 or big group 2 and small group 1. Given the above analysis, we could get it down to at worst 5 dead (average 3.74) if only the king was willing to lose 1 good bottle of wine along with the poisoned one. No wonder people say he is evil. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Court Jester on Aug 2nd, 2002, 9:03am For AlexH.... Incorrect in a second round of testing.....Once again all the drinking is done in the single sitting which given the number of combinations required could take up to a week. 10 groups of 100 bottles, 90 groups of 11 bottles, etc. Everyone seems to be under some assumption of waiting for symptoms to appear before continuing with the next step and this is wrong....You have a week (really four days assuming a 31 day month) to perform all the steps of drinking in the combinations listed from my previous post and a month left afterward to wait for the slaves to die and identify the poisoned bottle. I cannot emphasize this enough-----THERE IS NO SECOND ROUND OF TESTING IN A TIME SENSE. IT'S ALL DONE WITHIN THE FIRST WEEK (FOUR DAYS) TO ALLOW THE REMAINING MONTH FOR THE SYMPTOMS TO DEVELOP AND SLAVES TO DIE. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by AlexH on Aug 2nd, 2002, 9:22am Without using multiple rounds in the test method you describe you won't be able to overcome the problems of confusion as to which person is dieing for what reason. If a,b,c die, then who had it in his set of 100, who had it in his set of 11, and who had it in his set of 2? You can't tell. Count the dead and the bottles as I did above. In your solution 1-4 prisoners die. There are: 10 ways to have 1 dead prisoner 45 ways to have 2 dead prisoners 120 ways to have 3 dead prisoner 210 ways to have 4 dead prisoners Altogether thats 385 different ways your method could turn out, but there are 1000 different bottles so you can't have uniquely identified the one with the poison. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Court Jester on Aug 2nd, 2002, 9:50am AlexH...the second part of your first post (big group 1, small group 2) did get me thinking though and the solution for that is easy enough. There are essentially four rounds of drinking so it simply done by performing one round per day leaving the remaining month for the symptoms to appear. This eliminates your conundrum of differentiating between the two bottles from the first two rounds. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by AlexH on Aug 2nd, 2002, 10:33am Court Jester: If I understand you then you're relying on being able to tell which day someone drank poison based on which day they died. We're not given any reason to think we can do this, and if we can then its the same logical principle as having one guy drink from all 1000 bottles and timing his death with a stopwatch. Modified Cupbearers Problem: We have 1000 bottles of wine and one is poisoned. Poison is fatal in any dose and the only symptom is death which will occur unpredictably in at most 1 month. The king has 10 prisoners who can be used for taste testing. The king wants as much wine as possible for his ball in 5 weeks, and prisoner's lives mean nothing to him. Wine can not be poured or drunk in increments smaller than 1/1000 of a bottle. This modified problem won't be hard for anyone who's read this thread but I thought it was interesting. There are a few slightly different answers depending on what assumptions you might make but spelling out all the assumptions really makes things too obvious. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Frederik Bonte on Aug 8th, 2002, 5:17am I believe there is a different solution to finding the poisoned bottle. Everybody seems conviced that wine needs to be mixed to find the answer. Let's do it this way: All bottles are placed in a grid of for instance 25x40 bottles. Wine from each row and each column is (SAFELY) mixed into one cup. These cups are given to 25+40=65 prisoners of which two will die. The two prisoners that die dictate the exact coordinate of the poisoned bottle of wine. Or is that a stupid solution? Greetings, Frederik |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Gavin on Aug 9th, 2002, 7:37am Split the bottles into 2 groups of 250. Have one prisoner take a sip of one set. If he lives *or* dies, you know which set the poisoned bottle is in. Then simply split the poisoned set and repeat the process with either the still living prisoner, or prisoner number two. You just have to split as near to half as possible. Assuming a death each time, you get this: 250/250 125/125 63/62 31/31 or 31/32 15/16 or 16/16 7/8 or 8/8 3/4 or 4/4 1/2 or 2/2 1 <- the poison! So, easily achievable with 10 prisoners... |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by AlexH on Aug 9th, 2002, 9:11am Frederik: We've been interpreting the problem to require that you use only 10 prisoners. If, as stated you only have to kill at most 10, then just have 1000 prisoners each sip from a different bottle and throw out the one of the guy who dies. Gavin: Thats the binary idea of the normal solution but you need to have all the drinking done from the start. The poisons effects may not appear for 1 month and we need to know whats safe by 5 weeks. There isn't time to wait and see if one guy dies before you decide to test other bottles. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Jonathan_the_Red on Aug 9th, 2002, 12:48pm I don't think people are giving Rhaokarr nearly enough credit for his solution. It is, as he said, a lot easier to round up 30 prisoners than 999 (or 1000), and a lot better to kill a guaranteed three prisoners than up to 9 with the binary solution. And you get the fun of tattooing the heads, and you get to send the appropriate heads to the queen. Sure, you could do the head thing with the "grid" solution as well, but then the queen finds a couple of heads labeled "Row 17" and "Column 6" in her care package and just thinks, "huh?" |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by AlexH on Aug 10th, 2002, 12:22am It only takes 19 prisoners if you want to limit your losses to 3, and if you are willing to go up to 45 prisoners you can get your max losses down to 2. What you do with the heads afterwards is your own business. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Bigswede on Aug 10th, 2002, 12:24am Use 10 prisoners. Label each prisoner with a digit, 0, 1,......,9 Label the bottles of wine 000, 001, ......., 999 On the first day, have each prisoner drink from all the bottles that have his digit in the 100's place. For example, prisoner labeled 3 would taste wine in bottles 300 to 399. On the second day, same thing, except drink from each bottle with digit in ten's place. e.g. prisoner labeled 3 would drink from bottles 030, 031,..039, 130, ...139, ....930,..939. On the third day, same thing, except drink from each bottle with digit in 1's place. e.g. prisoner labeled 3 would drink from bottle 003, 013, 023, ...093, 103, ......993. Wait 31 days (a month) and see which prisoner dies. That gives the first digit (100's place) of the poisoned bottle. The next day (32), if someone else dies, that gives the 2nd digit, and the third day (33), if someone dies, that gives the 3rd digit. If nobody dies on day 32, the 2nd digit is the same as the first. If nobody dies on both days 32 and 33, all three digits are the same (as the first digit). If a prisoner dies on day 31 and another dies on day 32, but nobody dies on day 33, the bottle could be either of two bottles, with the 3rd digit the same as either the 1st digit or the 2nd digit. Throw both those bottles out. To resolve this last case, we use a different group of 10 prisoners to taste the 1's digit bottles (at the start), so then someone would die on the 33rd day and the bottle would be uniquely identified. This method uses 10 prisoners, with at most 3 dieing, but 20% of the time, two bottles have to be thrown out, or it uses 20 prisoners, with at most 3 dieing, with only the single poisoned bottle having to be thrown out. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Matthew on Aug 23rd, 2002, 4:58am Bigswede, I came up with the same solution as your although: I use a 4th day to to eliminate the 2 bottle ambiguity. (simply ROT-13 the prisoners) - Thus at most 3 prisoners die - An exact solution appears in 1 month and 4 days cheers PS 8) Cathy's combination solution is by far the most elegant IMHO. Doh why didny I think of that? |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by AlexH on Aug 23rd, 2002, 10:36am The assumption that we can time the poison like this is not supported. If we can time it then we only need 1 prisoner who drinks from all 1000 bottles at 1 minute intervals then time his death. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by AlexH on Aug 23rd, 2002, 12:20pm Since solutions taking some advantage of the notion of timing the death of prisoners to determine when they drank the poison seem to be popular, here is a generalized strategy in that case (which I believe is optimal for the given assumptions). Lets say we have k "windows" which represent the uncertainty of how long it takes for the poison to show. For example if we know the poison shows sometime between exactly 30 days and exactly 31 days after the poison is drunk, then if we start poisoning at 12am on day 1 we could have 5 windows,then one each for days 31,32,33,34,35 (assuming the wine is needed during day 36) so k=5 in this case. Now we need to label each bottle in base k+1 and have prisoner i drink from the bottle on day j if the ith digit is j and ff the ith digit is 0 he doesn't drink from the bottle at all. If we want to determine how few prisoners we need the answer is (log n)/(log k+1). If we fix a number m of prisoners and want to limit deaths then we need to get n sequences of m digits of base k+1 with the smallest possible bound on the number of non-zero elements. For example, if n=1000 bottles and k=5 windows then we can either use 4 prisoners with a substantial chance that all will die (6^4=1296>1000), or we can use 10 prisoners and have at most 2 die (there are 1176 10-digit base 6 strings with at least 8 0s). |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by troll314 on Aug 24th, 2002, 7:06am AlexH, you are completely correct. I was a little hasty with my earlier assessment of Cathy's solution. (Posted under the name guest name Matthew). It is in fact not possible to solve this problem given: - max 10 prisoners can be USED - Time delays are not allowed Because this would require us to use Combination (which disregards order) Thus the number of combinations of a group of n objects taken r at a time is: C(n,r) = n! / (r! * (n - r)!) Prisoners (n) 10 group (r) C(n,r) C(10,1) 1 10 C(10,2) 2 45 C(10,3) 3 120 C(10,4) 4 210 C(10,5) 5 252 C(10,6) 6 210 C(10,7) 7 120 C(10,8) 8 45 C(10,9) 9 10 C(10,10) 10 1 As you can check here there are not enough combinations to assign one to each bottle. Using only 13 prisoners we can find a solution Prisoners (n) 13 group (r) C(n,r) C(13,1) 1 13 C(13,2) 2 78 C(13,3) 3 286 C(13,4) 4 715 C(13,5) 5 1287 C(13,6) 6 1716 C(13,7) 7 1716 C(13,8) 8 1287 C(13,9) 9 715 C(13,10) 10 286 We could then choose groups of 5, 6, 7, or 8 prisoners to die. However if represent order by using time then permuation reveal many more possibilites than combination. For example say we used 4 out of prisoners the permutations of a group ABCD would be 10*9*8*7 = 5040. If we use 1 day for each letter. Eg Prisoner A drinks on day one, B on day two etc. Which is the same conclusion I came to using the popular divide and conquer method except that this solution is neater. Summary Solution available for - 13 prisoners used - 5 prisoners die - Kings knows on 1st day (after month) Solution available for - 10 prisoners used - 4 prisoners die - Kings knows on 4th day (after month) Solution available for - 7 prisoners used - 5 prisoners die - Kings knows on 5th day (after month) and of course many more.. depends on what your optimimum contraints are. IS it better to kill fewer prisoners? Does the king want to know earlier? etc These are essentially the same conclusions you would come to if you plugged in the parameters into AlexH's general equation. (i assume - havent checked ;) cheers, matthew |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by AlexH on Aug 24th, 2002, 9:52am The binary labelling scheme works just fine with 10 prisoners and no timing tricks. This is in fact exactly what my generalized system suggests if you plug in k=1 (i.e we can't do any timing tricks). log 1000/log (1+1) < 10. You've got the numbers of combinations correct, but you're mistaken in thinking that we need to assign a fixed number of prisoners to become posioned. The optimum binary labelling uses all of the lables containing 0-7 deaths plus most of the labels containing 8 deaths, all together summing to 1000 labels. Here are some numbers for 1000 bottles, with minimal deaths on 10 prisoners or with minimal prisoners. 1 window: (i.e. no timing possible) 10 prisoners --> at most 8 deaths, avg 4.916 2 windows: 7 prisoners, <=5 deaths, avg 3.567 10 prisoners, <=3 deaths, avg2.777 3 windows: 5 prisoners, <=5 deaths, avg 3.72 10 prisoners, <=3 deaths, avg 2.532 4 windows: 5 prisoners, <=4 deaths, avg 2.976 10 prisoners, <=3 deaths, avg 2.197 5 windows: 4 prisoners, <=4 deaths, avg 3.136 10 prisoners, <=2 deaths, avg 1.948 |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by troll314 on Aug 24th, 2002, 12:14pm Of course thats what I was missing! You can vary the number of prisoners assigned to each bottle. WHOOPS. therefore cathy was in fact right! (Use all the combinations) Because group (r) C(n,r) C(10,1) 1 10 C(10,2) 2 45 C(10,3) 3 120 C(10,4) 4 210 C(10,5) 5 252 C(10,6) 6 210 C(10,7) 7 120 C(10,8) 8 45 C(10,9) 9 10 C(10,10) 10 1 Sums to 1023 possibilites :) Yeah I reckon the problem was meant to be solved without time effects. Cheers, |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Cassie M on Dec 31st, 2002, 9:49am ;D solution: pretty simple -The king has one prisoner drink from the first 500 bottles of wine. If that prisoner dies the poison is in bottles 1-500. If he dosen't die it is in bottles 501-1000. (the rest of the solution is based on if the prisoner dies although it if the same if he dosen't.) -The next prisoner drinks from bottles 1-250. That eliminates another 250 bottles based on whether or not this prisoner dies. -The third prisoner drinks from bottles 1-125 eliminating 125 more bottles. -The fourth prisoner drinks from bottles 1-63 (125 doesn't divide evenly i rounded up, it still eliminates a certian portion) -The fifth prisoner drinks from bottles 1-32 eliminating another set portion if based on whether he lives or dies. -The 6th prisoner drinks from bottles 1-16 -The 7th prisoner drinks from bottles 1-8 -The 8th drinks from bottles 1-4 -The 9th drinks from 1 and 2 -The last prisoner drinks from bottle 1 and if he dies then that is the poisoned bottle if he dosen't then bottle 2 must be poisoned. *This solution is more of a formula. I based it on the drinking prisoner always dieing however it would still eliminate the same number of bottles if the prisoner lived. The poisoned bottle does not have to be bottle 1 or 2 but this process of elimination formula would still eliminate 999 bottles narrowing it down to the poisoned bottle. ;) |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by blurp on Jan 11th, 2004, 4:09am That won't work, because you have to wait for the results to come before another round of drinking can start. This way it takes ten months before the king can drink his precious wine again... |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Marios_Bonmercy on Mar 8th, 2004, 4:27pm well .... first, let's make it easier than that we use 10 prisoner since 1000 give us 10 numbers in binary I have 10 bottles instead of 1000 so I need 4 prisoner prisoner : ABCD Bottle#1: 0001 Bottle#2: 0010 Bottle#3: 0011 Bottle#4: 0100 Bottle#5: 0101 Bottle#6: 0110 Bottle#7: 0111 Bottle#8: 1000 Bottle#9: 1001 Bottle#10:0101 we force each prisoner to take a sip from the bottles which have the value(1) in his column if A die that means the bottle#8 is poisoned if A and D .........................#9 ............... etc .............. that what i think :-[ |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by grimbal on Apr 27th, 2004, 4:54pm Didn't I give this solution already? This one assumes that all bottles look alike. Just get the servant that poisonned the wine and tell him that if he drinks from any one bottle in the cellar, he is free. Also mention casually that you moved every single bottle in the cellar so that none is in its original place. If he refuses, he dies. To avoid risking to poison himself, he has to drink from the bottle located exactly where he put the poison. So you know which bottle is poisonned. And of course, if you save the trouble of actually moving the bottles, you also save the trouble of punishing the servant for what he did. ;D |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Mahmoud on May 19th, 2004, 5:01am I tried to solve the original problem. The limit of 10 prisoners to use is not tight at all. If you have a resolution of one day in determining when the person drank the poisoned wine, you need ONLY 5 prisoners to solve the problem. On average, less than 4 will die. This is because you have 5 extra days, and you need only 4 days to do sort of priority encoding/decoding of two bits of the ten bits many of you mentioned before. You encode them in 4 sips in 4 consecutive days. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Icarus on May 19th, 2004, 3:29pm Quote:
|
||||
|
Title: Re: Hard: Criminal Cupbearers Post by carpao on Jun 9th, 2004, 1:53am on 08/02/02 at 10:33:37, AlexH wrote:
I found an answer of 5.74 bottles if we want to minimize the worst case and 5.728 bottles if we want to minimize the average case someone does better? |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by carpao on Jun 9th, 2004, 3:31am on 06/09/04 at 01:53:07, carpao wrote:
5.476 for the average case... |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Grimbal on Jun 9th, 2004, 1:57pm on 06/09/04 at 03:31:26, carpao wrote:
If what you count is the number of bottles wasted to prisonners, assuming there is only one round possible in the 5 weeks, I don't see how you can do better than 5.916 worst case, 5.911 average. :( |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by carpao on Jun 10th, 2004, 1:27am on 06/09/04 at 13:57:40, Grimbal wrote:
I saw that it is used in this forum the policy to hide the solution and hints... So here there is the hint to find the worst case : [hide]some times is better to drink less and throw away more (sorry for my english)[/hide] and here my best solution for the worst case: [hide]group the bottle in group of two, you need all the combination till 4 prisonners and 114 with 5 prisonners you must consider that each prisonner drinks (each time) from 2 bottles (so 2*1/1000 of bottle each time) at the end you'll thow away 2 bottles ... however if you make the calculation (and if I'm not wrong ;D ) in this case the worst case is that no prisonner died (lucky for them) and so you have to throw away the two untouched bottle [/hide] BTW I discovered a little error in my calculation about the average case... it is a LITTLE BETTER... ;D 5.47078 |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Three Hands on Jun 10th, 2004, 7:31am I thought that the aim was to find out precisely which bottle is poisoned, not just one of two. After all, the King is a tight-fisted tyrant - clearly why there is this attempt to assassinate him ::) Nice thought, though (even if I'm not smart enough to figure out yet exactly how the method works, so I might be completely wrong as to how you are solving this...) |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by carpao on Jun 10th, 2004, 7:43am on 06/10/04 at 07:31:17, Three Hands wrote:
I solved the proposed (and explicitly cited) variant reformulation where the amount of drinked wine is to be considered and the goal is to minimize the amount of wasted (to prisoners or trash) wine... |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by rmsgrey on Jun 11th, 2004, 5:05am Which points to the king being a reasonably intelligent tight-fisted tyrant - willing to throw away an entire bottle of perfectly good wine in order to maximise his supply of wine... |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Three Hands on Jun 11th, 2004, 6:37am OK - I didn't really grasp what you were saying carpao. Time for me to spend a few hours with a headache, probably, while I try and catch up with the rest of you :-/ |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Mattis on Dec 19th, 2004, 5:41pm Well, I'd say there are plenty of solutions to the problem in this thread. But I think there is one intresting twist you could add to the problem. Suppose there is no way of knowing if a prisoner dies from the poisoned whine or from, say, age, torture or the bad food in the prison. As the cautious ruler you are, you want to compensate for the risk that one prisoner who didn't drink a poisoned whine dies a "natural" death. We can assume that there is very little risk that more than one prisoner who didn't drink the poison dies. With that twist, how would you proceed as the evil but cautious king you are? How few prisoners do you need to use to find the poisoned bottle in one month? I don't have a solution better than 20 prisoners but it should be doable with maybe 12-13 with some sort of error-correcting code or something. Or isn't it? Remember that most error-correcting codes assume that a 1 can become a 0 or a 0 can become a 1 through error in transmission. In this case we only have the latter case (a prisoner who didn't dring poison dies anyway is possible, but not that a prisoner who did drink the poison survives). That could be useful maybe. One easy thing you could do is to add an 11:th bit to the numbering of the bottles (in the ordinary "mark each bottle with a binary number"-solution), a checksum-bit set so that there always is an even number of '1':s on each number. Then one prisoner is the checksum-prisoner, set to die if only an odd number of the original prisoners dies (oh how happy he must feel). Now if an odd number of prisoners die anyway, you know that one must have died of natural causes, but you still don't know which bottle of whine is the poisoned one. Still you use only 11 prisoners and I claim that only 8 dies from poison in the worst case But does anyone have a good solution that requires less than 20 prisoners and also points out which bottle is the poisoned one? |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by SwaMpFoX on Jan 30th, 2005, 8:42pm I dont think anyone needs to die why not look for the open bottle. Back in the day wine bottles came with a cork in it then dipped into wax to seal it. 10 prisoners could inspect 100 bottles each the one bottle that has the seal tampered with throw out. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by towr on Jan 31st, 2005, 12:57am You're assuming the bottle was tampered with after it was closed and sealed. Besides, even if that were the case, it might have been resealed by a professional and not look suspicious. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Lance on May 16th, 2005, 8:05pm Take 10 prisoners and divide the 1000 bottles so that each prisoner has 100 bottles. Record which prisoner gets 1-99, 100-199, 200-299, so on. Since that poison is still extremly potent when diluted, mix the 100 bottles together and make each prisoner drink from their batch. By the forth week the King has one dead prisoner and 900 bottles worth of wine to drink by the fifth week. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by ThyGod on Jun 16th, 2005, 1:57pm i think i have it. To simplify, say that the poison takes 4 hours and the king wants to have 999 bottles of wine at 5. u have prizoners 1, 2, 3, 4, 5, 6, 7, 8, 9, and 0, which will be the tenth prisoner. If you assign each bottle to a unique group of prisoners, such as 1st bottle to prisoner 1, 2 to 2 and so on. So, when the four hours are up, you look at which group of prisoners died, and select their bottle as the poisoned one. Now, since u cant repeat numbers or the order in which they apper, i.e. u cant have 123 and 321 or 231, since the same group of prisoners would die, you have to devise a more complex method of counting. But it is relatively easy. for 11, use 12, eventually u might have to use 5 digit numbers for 3 digit ones, but there will be a unique combo for each bottle, which is the solution. ;D |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Obi2Kenobi on Jun 29th, 2005, 9:33pm Well, you see, he's an evil king. It doesn't explicitly state that he has to use those prisoners to discover which bottle is poisoned, only that he is going to make some prisoners drink the wine. So any number will work; if he runs out of prisoners, he's a king, he can just raise an army against the neighboring queen, capture her, and make her and her nobles drink the rest of the wine if the king isn't smart enough to figure out to do it without wasting tons of his precious prisoners (although he still could use a few thousand prisoners to ease the public concern of crime by being able to honestly state that prison crowding is at an all time low). Wow, that was a very convoluted/run-on sentence. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by raj on Nov 6th, 2005, 4:51pm I approached this problem with the assumption that the king can only run a single day of trials. i.e. no testing on day 2 3 4 etc. He then has to wait 4 weeks for the result. I also assumed that it is possible to subset the bottles into groups and mix 1 drop from each of the bottles in such a subset without tainting occuring. I divided the bottles into dimensions. 1 dimension = 1000bottles requires 1000 tasters 2 dimensions = 100X100bottles requires 200 tasters 3 dimensions = 10^3bottles requires 30 tasters etc thereby isolating the poisoned bottle. I reason that the number of subjects (y) and number of dimensions (x) can be graphed as y = x*(x root 1000). The optimum number of subjects is thus 19, where the bottles are divided up into 6 dimensions (x=6). Any help varifying this would be much appreciated. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Grimbal on Nov 7th, 2005, 1:01am on 11/06/05 at 16:51:01, raj wrote:
You probably mean 2 dimensions 1024 ~= 32X32 bottles, requires 64 tasters Anyway, if you know there is a poisonned bottle, you can save one tester per dimension. Just leave one group untested. If nobody dies, the poison is in the untested group. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by raj on Nov 8th, 2005, 12:51am 32X32 Whoops! 2 dimensional post completion explanation glitch. Back to flatland for me. Thanks Grimbal. Your solution goes the extra mile... |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by drilly2000 on Jan 26th, 2006, 8:00am Maybe i'm looking at this wrong but would it not be easier to divide the 1000 bottles into ten groups of 100. One group for each prisoner,have each prisoner sip from each of his 100 bottles. when one dies you now have 9 prisoners alive and only 100 possible bottles then follow the halving method until the offensive bottle is found. May take a while but you'd kill less of the servants. ( 3 less i think) |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by towr on Jan 26th, 2006, 9:07am I think there was a time limit on when you had to find the offensive bottle. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by TheRappingShoe on Apr 25th, 2006, 7:44pm Right,... here you go: This assumes the poison takes exactly a month. It involves 10 prisoners and takes three days over the one month period. The answer is worked out by feeding the prisoners a variety of wines over a three day period. This will cause a three day sequence of deaths beginning exactly one month later. First number all the bottles from 001 -> 999. Bottle 1000 is recorded as 000 just to keep things in a 3 digit system. Next, draw up a three day schedule of drinking for prisoners 1-9! In this sequence the * sign represents all numbers from 1-9, but does not include zero. Code:
So ,for example, on day one Prisoner 1 drinks from all the bottles with their first digit as 1. On day two he drinks from all with the 2nd digit as 1. And day three all with the 3rd digit as one. Prisoner 10 gets wine too, but he's special: Code:
A month to the day later ------------------------------- By recording the sequence of deaths over three days you can use a process of elimination to work out which bottle the poison is in. In the majority of instances we only need to look at the deaths of the first nine prisoners. As long of one of these dies every day then we can identify the poisoned bottle. For example, Day One: Prisoner ONE dies Day Two Prisoner TWO dies Day Three Prisoner THREE dies Then you know the poison is in bottle 123 :) Also, should none of the nine die then we know the poison is in the one bottle that none of them drank from- Day One: NO-ONE Dies Day Two: NO-ONE Dies Day Three: NO-ONE Dies Then you know the poison is in bottle 000 (aka 1000) Why do you need prisoner 10? -------------------------------------- There are eight possible death sequences for the nine prisoners over three days. The first four allow us to identify the poisoned bottle with 100% certainty. D = a death occurs, A = no death occurs http://img274.imageshack.us/img274/5954/table16pr.gif But in the final four sequences we are left with two or more suspect bottles: http://img274.imageshack.us/img274/9276/table22me.gif This is where we look to prisoner 10. By cross referencing the day of his death with the original death sequence this lets us narrow the poisoned bottle down to one. http://img289.imageshack.us/img289/5267/table30hc.gif And that's it! Here's a couple of examples of how to use the system... If the poison was in bottle 747, then the following would happen: Day 1 : Prisoner 7 dies Day 2 : Prisoner 4 dies Day 3 : No-one dies This fits a DDA sequence, meaning the poisoned bottle is one of 744 (xyy), 740 (xy0) or 747 (xyx). We look to prisoner ten and note that he is still alive and kicking. So the poison must be in the one he hasnt drunk from, which is number 747. Alternatively, if we had a death sequence of Day 1 – Prisoner 5 dies Day 2 – No-one Dies Day 3 - Prisoner 3 Dies This is a DAD sequence, so we look and see that Prisoner 10 died on day two. This means that the poison was in a bottle fitting the x0y pattern, which tells us that the poison was in bottle 503. Simple ;) |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by TheRappingShoe on Apr 26th, 2006, 12:46pm By the way, I know it has been suggested to use a binary numbering system, (binary numbers on bottles, and then lining up prisoners in a row). I dont think this would work. I not really very familiar with binary, but any such numbering system, so please correct me if I'm wrong: All numbers have to be represented by ten digits. The binary code for ONE, for example, is '1'. Presumably shown by having prisoner one lying down dead. But the other 9 prisoners would still be there: If they are alive then they would appear as 0's, and if they are dead they appear as 1's. You cant just send them away and pretend they dont count. So you'd actually be seeing 0111111111 , or 1000000000. What I'm saying is that if you use binary then you can only use numbers that take up ten digits. Are there a thousand of these? Anyway, I think my solution (posted above and also at http://www.rhodriwilliams.com/CrimCups.html) is better, and only kills three at most people over a three day period :) |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by towr on Apr 26th, 2006, 2:19pm on 04/26/06 at 12:46:49, TheRappingShoe wrote:
And the advantage of the binary method is it doesn't matter whether the poison work in exactly a month, or somewhere between 1 and 4 weeks (randomly for each individual). As long as death occurs within 4 weeks, you'll have identified the poisoned bottle. Of course, all ten prisoners may die, which might be considered a disadvantage. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by TheRappingShoe on Apr 26th, 2006, 5:02pm Yes, I've been discussing this with my computer programmer mate who has been explaining binary to me. Nice and slowly ;) I still think my method deserves credit for originality :D I cant explain these things very well though - all I've ever written for the past 6 years is politics essays! ;D I've not written about logic since I was 15! Anyway, in terms of likelihood of deaths which is better? The binary method MIGHT cause 10 deaths, but how many on average would it cause? My method causes a maximum of three deaths (and a 1000/1 shot of no deaths), but in the majority of instances 3 people will end up dying. Does the binary method, or any other method, undercut this? I'm sure you could reduce the death average by spreading the testing over seven days. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by towr on Apr 27th, 2006, 12:39am I think binary would cause 5 deaths on average. Well, slightly less since there are 1000 and not 1024 bottles (so if you start counting at 0, e.g. bottle 1023 which would cause 10 deaths doesn't exist) |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by rmsgrey on Apr 27th, 2006, 3:56am Binary can be improved on slightly by skipping certain numbers - for instance 511 would kill 9 prisoners, while 1001 only kills 7, and so on... I'm not convinced by TheRappingShoe's analysis: If the poison is in bottle 220, for example, following his charts gives: day 1: prisoner 2 dies day 3: prisoner 10 dies conclusion: bottle 200 is poisoned... It looks like a simple fix is possible though - if prisoner 10 drinks all xyy and x00 (x and y are different and non-0 throughout) on day 1, x0x and x0y on day 2 and xx0 and xy0 on day 3, then the only change is for DAA, when the patterns for prisoner 10 dying on day 1,2,3, or not at all are: x00, x0x, xx0, and xxx respectively... |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by TheRappingShoe on Apr 27th, 2006, 9:58am Yes I you're quite right. Prisoner 10's schedule needs changing to that. :-[ |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Whiskey Tango Foxtrot on Apr 29th, 2006, 11:29am I still think Alexh's original proposition of creating a series of rows and columns was the most rational and easiest to perform, although it would waste a decent amount of criminals. This is a similar idea. Create a 10 x 10 square of wine jars. Assign a prisoner to drink from each jar in one row. Tell the other 9 to do the same for the other 9 rows. At the same time, assign 9 prisoners to drink from each jar in a column in the same manner that prisoners were assigned to rows. Only nine are needed since the last row can be evaluated by elimination. Repeat this process for the next nine squares. So in the end, 190 prisoners are required (10 x 19), but only two criminals die from the poisoning, making it simple to find the poisoned jar. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Grimbal on May 2nd, 2006, 1:02am @WTF: why don't you extend the method and make a cube of 10x10x10? Assign 9 prisonners to each dimension. You need only 27 of them and max 3 will die. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Whiskey Tango Foxtrot on May 2nd, 2006, 6:14am Why not indeed. It was to be my next post. I kind of assumed that someone would take issue with the idea before elaborating on it. But you proved me wrong Mr. Grimbal. My faith in humanity is restored. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Mattis on May 4th, 2006, 3:30pm Just an interesting thing: The "cube"-solution and the "binary"-solution are really two sides of the same coin, it's just a matter of dimensions. ONE dimension: Put all bottles on a LINE, let 999 prisoners drink from 999 of them. The ONE that dies marks the poison, (if no one dies, the last bottle is the poison). TWO dimensions: Put all bottles in a 32x32 SQUARE. Have 31 prisoners drink from all bottles of one row each, and 31 prisoners drink from all bottles of one column each. The TWO that dies marks the bottle (if no one of the "row-prisoners" dies, it was the last row that contains the poison, and the same goes for the "collumn-prisoners"). THREE dimensions: Put all bottles in a 10x10x10 cube, have 9 drink from all bottles in one cut in the XY-plane each, 9 drink from all bottles in one cut in the YZ-plane each, and 9 drink from all bottles in one cut in the XZ-plane (hmm, hard to explain that one, but I hope you understand.). The (at most) THREE prisoners that dies marks the poison. Now FOUR dimensions: Put all bottles in a 6x6x6x6 hypercube, have 5+5+5+5 prisoners drink all bottles from one... hyperplane (I guess a hyperplane is a cube) each. A bit hard to imagine maybe, but the (at most) FOUR prisoners that dies marks the poison Finally TEN dimensions: Put all bottles in a 2x2x2x2x2x2x2x2x2x2 ten dimensional hypercube. What? You can't imagine a ten dimensional hypercube? Its just like a nine dimensional hypercube where you add another dimension, no problem. Now have 1+1+1+1+1+1+1+1+1+1=10 prisoners drink from all the bottles from one of the... 9-dimensional hypercubes I guess... It gets pretty messed up as we have a hard time imagining hypercubes, but let me assure you that the (at most) TEN prisoners that die mark the poisoned bottle. More dimensions means more prisoners might have to die, but fewer are needed. You can also watch this the other way around. Giving each bottle a coordinate in the 10-dimensional hypercube with side 2 is the same as assigning them each a 10-digit binary number. Giving each bottle a coordinate in the 3-dimensional cube with side 10 is the same as as assigning them a 3-digit decimal number. Giving each bottle a coordinate in the 2-dimensional square with side 32 is the same as assigning them a 2-digit number in base 32. So if we give each bottle a number with n digits in base B, B-1 prisoners is sufficient to find out one of the digits of the poisoned bottle, and n*(B-1) prisoners is sufficient to find out the number of the poisoned bottle. Also, at most one prisoner per digit will die. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by grad on May 8th, 2006, 4:54am I am trying to solve CRIMINAL CUPBEARERS but I think that everyone has given his own meaning to the problem in the forum. The problem does is very poorly presented. Many things need to be clear. 1) The poison takes EXACTLY one month to surface OR AT LEAST one month ??? 2) The king can use up to 1000 prisoners but 10 must die OR the king can use ONLY 10 prisoners ?? 3) The time that passes from the time someone takes the poison until he dies is the same for every person OR these times can be different? Please answer my question and sorry for my poor english. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by towr on May 8th, 2006, 5:23am 1) The effects surface in under 5 weeks, that is sufficient to find a solution 3) The time it takes for any individual to die from the poison may differ, as long as they are guaranteed to die (from the poison) before the party starts. 2) The method he employs kills at most 10. He might use 1000, but I'd assume he goes for efficiency and uses the least number of prisoners. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by DewiMorgan on Jun 2nd, 2006, 10:44pm It would IMHO be better rephrased as "he has only ten cupbearers, but doesn't want to lose more than 8 of them". Though I do also like the rephrasing to make the amount of wine the important thing - the discarding of a while bottle was a pleasant surprise. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Grimbal on Jun 5th, 2006, 3:12pm Another variation: The king gets informed that one of the prisonners has developed a resistance to the poison. He doesn't know which. How many prisonners does he need now? |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by towr on Jun 6th, 2006, 12:43am on 06/05/06 at 15:12:32, Grimbal wrote:
|
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Grimbal on Jun 6th, 2006, 3:39am I know that a classical solution gives that as an upper bound, I was wondering whether it could be improved. After all, no prisonner can die while he is not supposed to... |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Grimbal on Jun 6th, 2006, 5:39am OK, I found the necessary references, I agree with towr. [hide]The Varshamov-Tenengolts code and Sloane's A000016[/hide] |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by Aravis on Jul 14th, 2006, 7:49am I was working this problem, and came up with what people are calling the binary solution (I used the hypercube method actually, because it is easy to generalize from the 4 wine bottles and 8 wine bottles cases), but if I were king, I figure making a list of all the wine bottles in hypercube format would be a bummer. So I made a simple boolean statement that determines whether a prisoner should drink a given bottle of wine. We already know that given B bottles of wine we need at least log2B prisoners (the next integer above it obviously, no fractional prisoners), an let this numper be P, the number of prisoners. Label each bottle of wine W starting from 0 (ranging to B-1) Label each prisoner N staring from 0 (ranging to P-1) If the following statement is true, prisoner N drinks from bottle W. W mod 2P-N < 2P-N-1 |
||||
|
Title: Re: Hard: Criminal Cupbearers -Only 3 needs to die Post by aditrip on Sep 6th, 2006, 11:57pm I have a pretty simple solution , Do you find anything wrong with this solution: 1. number the prisoners from 000, 001..100,101..256,257.....999. 2.Number the prisoners from 0 to 9. 3. Let the prisoner no say, 2, 5 and 6 taste the wine from bottle 256. Likewise, all bottles numberd xyz is tasted by prisoner no x, y and z. 4. If, say prisoners 2, 5 and 6 die, then bottle no 256 is poisoned. Similarly is prisoner no x,y and z die then bottle no xyz is poisoned. 5.Best case, one prisoner die (bottle no 000) 6.Worst case - 3 prisoners die. Aditya Mani Tripathi |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by aditrip on Sep 7th, 2006, 12:19am That's wrong. 256 and 526, can't differentiate. Same approach with binary can find the result. One of my friends Anil Goyal found this out. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by v3ritas on Apr 9th, 2009, 1:11pm i posted this in the other thread, and someone probably has the same solution i have but i don't feel like going through five pages of proposed solutions. here's mine though: get ten prisoners. give them a sip of wine each day, one wine at a time. by the end of the month the prisoners, combined, will have had all of the wine. if on the first day of the fifth week no one shows symptoms, then the wines given on the first week are ok. if on the second day of the fifth week no one shows symptoms, then they're ok too. do this till you see the prisoner who shows symptoms, then trace what wine he drank four weeks earlier. :> |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by towr on Apr 9th, 2009, 1:33pm on 04/09/09 at 13:11:14, v3ritas wrote:
Quote:
Not to mention it depends on the poison killing after exactly one month. Which is rather unlikely. It can be solved without that assumption. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by v3ritas on Apr 9th, 2009, 5:42pm yeah i realized the 300 bit earlier. here's my edit from the other post: Quote:
the riddle says that it takes one month for the effects to surface. it says one month, not a month and a few days. one month. so when you see a prisoner show effects of the poison, track down which wine he drank. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by towr on Apr 9th, 2009, 11:54pm on 04/09/09 at 17:42:14, v3ritas wrote:
At the very least a month can be anything from 28 to 31 days. And I wouldn't bet a poison would take much notice of those bounds. Nor does the solution make a use of it; as long as it kills within 5 weeks it will work. |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by v3ritas on Apr 10th, 2009, 12:26pm that's true. we could take 365.24 days and divide by 12, which is 30.43 days. this could be assumed as the "month". however, 5 weeks multiplied by 7 days is 35 days, so there wouldn't be the full week following the wine sampling, which means the wines tasted in the latter part of the "month" can not take effect within the 5 week period. to make up for this more wines could be tasted throughout the day. later i'll try and figure the math |
||||
|
Title: Re: Hard: Criminal Cupbearers Post by towr on Apr 10th, 2009, 2:03pm Well, I'm fully confident you can work out how often you should give a prisoner a drink if death sets in an exact number of hours or minutes after ingestion (and you'd really only need one prisoner. Every ten minutes for a week works out to 1008; and who cares if the prisoner doesn't get to sleep.) But can you figure out a scheme where you give the ten prisoners a selection of drinks all at one time, and then simply wait 5 weeks to get results? |
||||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |