Author 
Topic: Hard: Criminal Cupbearers (Read 21576 times) 

Cody Batt
Guest

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;


IP Logged 



Vineet Kumar
Guest


Re: Hard: Criminal Cupbearers
« Reply #1 on: Jul 25^{th}, 2002, 2:41am » 
Quote Modify
Remove

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.


IP Logged 



Viorel Canja
Guest


Re: Hard: Criminal Cupbearers
« Reply #2 on: Jul 25^{th}, 2002, 4:09am » 
Quote Modify
Remove

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


IP Logged 



Vineet Kumar
Guest


Re: Hard: Criminal Cupbearers
« Reply #3 on: Jul 25^{th}, 2002, 3:26pm » 
Quote Modify
Remove

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 09 instead of 110 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.


IP Logged 



Cody Batt
Guest


Re: Hard: Criminal Cupbearers
« Reply #4 on: Jul 25^{th}, 2002, 3:49pm » 
Quote Modify
Remove

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.


IP Logged 



Json921
Guest


Re: Hard: Criminal Cupbearers
« Reply #5 on: Jul 25^{th}, 2002, 4:04pm » 
Quote Modify
Remove

How about, just make sure that one of the ten prisoners involved in the taste test was the one who poisoned the bottle?


IP Logged 



Kyalu
Guest


Re: Hard: Criminal Cupbearers
« Reply #6 on: Jul 25^{th}, 2002, 8:15pm » 
Quote Modify
Remove

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.


IP Logged 



Cathy
Guest


Re: Hard: Criminal Cupbearers
« Reply #7 on: Jul 25^{th}, 2002, 9:13pm » 
Quote Modify
Remove

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.


IP Logged 



Frothingslosh
Guest


Re: Hard: Criminal Cupbearers
« Reply #8 on: Jul 25^{th}, 2002, 9:20pm » 
Quote Modify
Remove

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.


IP Logged 



Andrew Ooi
Guest


Re: Hard: Criminal Cupbearers
« Reply #9 on: Jul 25^{th}, 2002, 10:09pm » 
Quote Modify
Remove

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


IP Logged 



tonza
Guest


Re: Hard: Criminal Cupbearers
« Reply #10 on: Jul 25^{th}, 2002, 10:53pm » 
Quote Modify
Remove

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


IP Logged 



Frothingslosh
Guest


Re: Hard: Criminal Cupbearers
« Reply #11 on: Jul 25^{th}, 2002, 11:17pm » 
Quote Modify
Remove

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.


IP Logged 



Andrew
Guest


Re: Hard: Criminal Cupbearers
« Reply #12 on: Jul 26^{th}, 2002, 2:56am » 
Quote Modify
Remove

Frothingslosh, I guess I skimmed your reply too fast, upon rereading 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.


IP Logged 



Rhaokarr
Guest


Re: Hard: Criminal Cupbearers
« Reply #13 on: Jul 26^{th}, 2002, 9:48pm » 
Quote Modify
Remove

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 1100, prisoner #2 tastes bottles 101200, etc. Prisoners 1120 drink a little out of each decade, so prisoner #11 tastes bottles 110, 101110, 201210, prisoner #12 tastes bottles 1120, 111120, etc Prisoners 2130, 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.


IP Logged 



Andrew Ooi
Guest


Re: Hard: Criminal Cupbearers
« Reply #14 on: Jul 29^{th}, 2002, 8:48am » 
Quote Modify
Remove

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 ]


IP Logged 



fredh
Newbie
Posts: 2


Re: Hard: Criminal Cupbearers
« Reply #15 on: Jul 29^{th}, 2002, 10:13am » 
Quote Modify

I was really intrigued by this riddle and I have an answer that uses only 10 prisoners, and only 13 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 coords which points to the exact bottle. What do you guys think? I hope the explanation was clear enough. Enjoy!

« Last Edit: Jul 29^{th}, 2002, 10:15am by fredh » 
IP Logged 



Alex Harris
Guest


Re: Hard: Criminal Cupbearers
« Reply #16 on: Jul 29^{th}, 2002, 1:01pm » 
Quote Modify
Remove

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


IP Logged 



Rhaokarr
Guest


Re: Hard: Criminal Cupbearers
« Reply #17 on: Jul 30^{th}, 2002, 2:44am » 
Quote Modify
Remove

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


IP Logged 



Razor_Gaunt
Newbie
Posts: 6


Re: Hard: Criminal Cupbearers
« Reply #18 on: Aug 1^{st}, 2002, 1:25pm » 
Quote Modify

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?


IP Logged 



Court Jester
Guest


Re: Hard: Criminal Cupbearers
« Reply #19 on: Aug 1^{st}, 2002, 2:38pm » 
Quote Modify
Remove

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 1100, prisoner two drinks from 102200, 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 taintedif 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!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


IP Logged 



AlexH
Full Member
Posts: 156


Re: Hard: Criminal Cupbearers
« Reply #20 on: Aug 2^{nd}, 2002, 7:42am » 
Quote Modify

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.

« Last Edit: Aug 2^{nd}, 2002, 8:28am by AlexH » 
IP Logged 



Court Jester
Guest


Re: Hard: Criminal Cupbearers
« Reply #21 on: Aug 2^{nd}, 2002, 9:03am » 
Quote Modify
Remove

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


IP Logged 



AlexH
Full Member
Posts: 156


Re: Hard: Criminal Cupbearers
« Reply #22 on: Aug 2^{nd}, 2002, 9:22am » 
Quote Modify

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


IP Logged 



Court Jester
Guest


Re: Hard: Criminal Cupbearers
« Reply #23 on: Aug 2^{nd}, 2002, 9:50am » 
Quote Modify
Remove

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.


IP Logged 



AlexH
Full Member
Posts: 156


Re: Hard: Criminal Cupbearers
« Reply #24 on: Aug 2^{nd}, 2002, 10:33am » 
Quote Modify

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.


IP Logged 



