wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> hard >> Criminal Cupbearers loophole
(Message started by: MorbidJoe on Jul 24th, 2006, 2:07pm)

Title: Criminal Cupbearers loophole
Post by MorbidJoe on Jul 24th, 2006, 2:07pm
Sorry for not using the other topic, but this isn't really an answer.


Quote:
An evil king has 1000 bottles of wine. A neighboring queen plots to kill the bad king, and sends a servant to poison the wine. The king's guards catch the servant after he has only poisoned one bottle. The guards don't know which bottle was poisoned, but they do know that the poison is so potent that even if it was diluted 1,000,000 times, it would still be fatal. Furthermore, the effects of the poison take one month to surface. The king decides he will get some of his prisoners in his vast dungeons to drink the wine. Rather than using 1000 prisoners each assigned to a particular bottle, this king knows that he needs to murder no more than 10 prisoners to figure out what bottle is poisoned, and will still be able to drink the rest of the wine in 5 weeks time. How does he pull this off?



Quote:
this king knows that he needs to murder no more than 10 prisoners to figure out what bottle is poisoned


Surely it should be use because he could give 1 bottle to each prisoner and he would still be murdering no more than 10 prisoners.

Just a thought  :)

Title: Re: Criminal Cupbearers loophole
Post by Icarus on Jul 24th, 2006, 5:11pm
Actually, the deficiencies in the problem statement have been a subject of discussion in the earlier threads as well. You are correct that the problem should have read "use".

Title: Re: Criminal Cupbearers loophole
Post by maorizio on Aug 2nd, 2006, 7:50am
I am not sure I understood.
what's wrong with this answer:

General idea:
we will do it in 3 similar stages - in the first 3 days, where in the end of each stage we will have only 10% of the bottles suspicous (regarding the previous stage).
1. divide each criminal 90 bottles to drink from.
after a month we will know which criminal died and we will have 90 suspicious bottles with 9 prisoners left, or 100 bottles with 10 prisoners.
2. (day 2) divide each group of bottles (where goup of bottles is the group that some prisoner drank from)  into 10 groups of 9, beside the last group - to be divided into 10 groups of 10.
each prisoner drinks a cup from a bottle of each group EXCEPT if he already drank from that bottle!
a month after - we will have 10/9 suspicious bottles depending if someone dies.
3. (day 3) each prisoner drinks 1 bottle from each (small) group he hasn't drank from it before.
and we will know a month later which is the poisened

more specifically (if I wasn't mistaken)
each prisoner drinks 90 cup from 90 bottles:
P1 from bottles 1-90
P2 from bottles 91-180
...
P10 from bottles 811-900
(so that after a month we will have 90 suspicious bottles, if one dies, or 100 if no-one dies)

on the 2nd day - each one drinks cup from 9 bottles of each group of Px, and 10 bottles from group 901-1000 (so we covered all the bottles)
( i.e. each one drinks 9 cups from bottles<=900
and 10 cups from > 900.) - each prisoner than drinks 9*9+10=91 bottles
i.e.
P1 drinks cup from 91-99, 181-189, ... ,811-819,  901-910
P2 drinks cup from 1-9, 190-198, ... , 820-828, 911-920
...
P10 drinks cup from 82-90, 172-180, ...,802-810, 991-1000
(so that after a month - we will have 9 suspicious bottles if 2 criminals died, or 10 if 1 criminal died).

and the 3rd day each drink
1 cup from each group he didn't drink before.
P1 drinks from 100, 110, ... , 990
P2 drinks from 11, 21, ..., 991
...
P10 drinkfrom 9, 19, ..., 989

e.g. assume WLOG that P1 died after month.
so we know that the suspicious bottles are 1-90
WLOG P2 died after month+day
again - the suspicious bottles are 1-10
and a day after WLOG died P3 - so the poisned is 1

if after 1 month nobody died, then the suspicious are 901-1000
if WLOG day after P1 dies, then its 901-910
and the 3rd day will determine which bottle is the poisened.

total deaths of 2/3 criminals.

Title: Re: Criminal Cupbearers loophole
Post by LaCiTy on Sep 3rd, 2006, 6:58pm
The correct answer is even more simple.

Remember that the effect of the poison is visible 1 month after ingestion meaning that you have to wait more than 1 month, typically 5 weeks to be sure you have seen it, as poisoning is not an exact science.

Indeed, if poisoning was very sharp you could take 1 prisonner and get him drink 1/1000 L every minute (so that he doesn't get too drunk) to detect what bottle is tainted.

This riddle should be ranked medium as no deep reasoning is involved, but little mental arithmetic.

Title: Re: Criminal Cupbearers loophole
Post by Icarus on Sep 8th, 2006, 5:55pm
I agree, except that William had no set criterion when he posted his riddle pages, and placed this one on the "Hard" page. There are simpler puzzles than this to be found under "Hard" (for example: 3 men and a hotel room).

Title: Re: Criminal Cupbearers loophole
Post by logan on Nov 28th, 2006, 3:15am
since the poison is that fatal and can not be eleminated in any means take small drips from each bottle and make 2 glasses from 500 bottle each. Wait a month see the man dies or not. you already rescued 500 bottles which is clean. king can start drinking them. than make a mixture of 250-250, 125-125, 64-61, (worst case is bigger number), 32-32, 16-16,8-8,4-4,2-2, and 1-1. each trial needs only one men (make him drink one half if dead take the other half if not take the half that he tasted). In worst case if a man died in each trial, still he has to sacrifice 10 at most. count it from 1-1 to 500-500 10 trials.

Title: Re: Criminal Cupbearers loophole
Post by Icarus on Nov 28th, 2006, 4:52pm
Unfortunately, the king is throwing a major party in one month and needs all 999 good bottles then. The puzzle is to find the poisoned bottle with the minimum number of prisoners, when all testing has to be done "in parallel". I.e., all testing has to take place at the same time - you cannot wait for the results of one test before performing another.

Title: Re: Criminal Cupbearers loophole
Post by rmsgrey on Nov 28th, 2006, 5:22pm

on 11/28/06 at 03:15:18, logan wrote:
since the poison is that fatal and can not be eleminated in any means take small drips from each bottle and make 2 glasses from 500 bottle each. Wait a month see the man dies or not. you already rescued 500 bottles which is clean. king can start drinking them. than make a mixture of 250-250, 125-125, 64-61, (worst case is bigger number), 32-32, 16-16,8-8,4-4,2-2, and 1-1. each trial needs only one men (make him drink one half if dead take the other half if not take the half that he tasted). In worst case if a man died in each trial, still he has to sacrifice 10 at most. count it from 1-1 to 500-500 10 trials.

But you can improve on that by doing two steps at once - take the last two steps as an example.

You go in knowing the poison is in one of 4 bottles. You divide them into two pairs - AB and CD - and get the prisoner to drink from AB. If he dies, then the next prisoner will drink from A; if he survives, then the next prisoner (which may be the same prisoner in this case) will drink from C. So instead of waiting, you can get the next prisoner to drink from AC now then when you get the result from the first prisoner. If you combine all ten steps this way, you can get your final answer in a month's time and have (most of) 999 bottles available for the royal ball a couple of days later.

Your method works better when only some of the wine needs to be available immediately, but if there's no time pressure, then just having the available prisoners each sample one bottle a month is more humane - it kills at most one prisoner - and, on average, uses less wine (roughly half as much)

The fast solution - doing all ten steps at once - uses about 5 times as much wine as your solution, or about 10 times what testing a single bottle at a time would use on average.



Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board