Author |
Topic: Hard: Criminal Cupbearers (Read 22581 times) |
|
Frederik Bonte
Guest
|
 |
Re: Hard: Criminal Cupbearers
« Reply #25 on: Aug 8th, 2002, 5:17am » |
 Quote  Modify
 Remove
|
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
|
|
 IP Logged |
|
|
|
Gavin
Guest
|
|
Re: Hard: Criminal Cupbearers
« Reply #26 on: Aug 9th, 2002, 7:37am » |
Quote Modify
Remove
|
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...
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Hard: Criminal Cupbearers
« Reply #27 on: Aug 9th, 2002, 9:11am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Jonathan_the_Red
Junior Member
Gender: 
Posts: 102
|
|
Re: Hard: Criminal Cupbearers
« Reply #28 on: Aug 9th, 2002, 12:48pm » |
Quote Modify
|
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?"
|
|
IP Logged |
My arcade cabinet
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Hard: Criminal Cupbearers
« Reply #29 on: Aug 10th, 2002, 12:22am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Bigswede
Newbie
Posts: 1
|
|
Re: Hard: Criminal Cupbearers
« Reply #30 on: Aug 10th, 2002, 12:24am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Matthew
Guest
|
|
Re: Hard: Criminal Cupbearers
« Reply #31 on: Aug 23rd, 2002, 4:58am » |
Quote Modify
Remove
|
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  Cathy's combination solution is by far the most elegant IMHO. Doh why didny I think of that?
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Hard: Criminal Cupbearers
« Reply #32 on: Aug 23rd, 2002, 10:36am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Hard: Criminal Cupbearers
« Reply #33 on: Aug 23rd, 2002, 12:20pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
troll314
Newbie
Gender:
Posts: 4
|
|
Re: Hard: Criminal Cupbearers
« Reply #34 on: Aug 24th, 2002, 7:06am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: Hard: Criminal Cupbearers
« Reply #35 on: Aug 24th, 2002, 9:52am » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
troll314
Newbie
Gender:
Posts: 4
|
|
Re: Hard: Criminal Cupbearers
« Reply #36 on: Aug 24th, 2002, 12:14pm » |
Quote Modify
|
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 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,
|
|
IP Logged |
|
|
|
Cassie M
Guest
|
 |
Re: Hard: Criminal Cupbearers
« Reply #37 on: Dec 31st, 2002, 9:49am » |
Quote Modify
Remove
|
 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. 
|
|
IP Logged |
|
|
|
blurp
Guest
|
|
Re: Hard: Criminal Cupbearers
« Reply #38 on: Jan 11th, 2004, 4:09am » |
Quote Modify
Remove
|
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...
|
|
IP Logged |
|
|
|
Marios_Bonmercy
Newbie
Gender:
Posts: 1
|
|
Re: Hard: Criminal Cupbearers
« Reply #39 on: Mar 8th, 2004, 4:27pm » |
Quote Modify
|
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 
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Hard: Criminal Cupbearers
« Reply #40 on: Apr 27th, 2004, 4:54pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Mahmoud
Guest
|
|
Re: Hard: Criminal Cupbearers
« Reply #41 on: May 19th, 2004, 5:01am » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Hard: Criminal Cupbearers
« Reply #42 on: May 19th, 2004, 3:29pm » |
Quote Modify
|
Quote:| Furthermore, the effects of the poison take one month to surface. |
|
|
| « Last Edit: May 19th, 2004, 3:30pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
carpao
Guest
|
|
Re: Hard: Criminal Cupbearers
« Reply #43 on: Jun 9th, 2004, 1:53am » |
Quote Modify
Remove
|
on Aug 2nd, 2002, 10:33am, AlexH wrote:
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. |
|
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?
|
|
IP Logged |
|
|
|
carpao
Newbie
Posts: 8
|
|
Re: Hard: Criminal Cupbearers
« Reply #44 on: Jun 9th, 2004, 3:31am » |
Quote Modify
|
on Jun 9th, 2004, 1:53am, carpao 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? |
|
5.476 for the average case...
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Hard: Criminal Cupbearers
« Reply #45 on: Jun 9th, 2004, 1:57pm » |
Quote Modify
|
on Jun 9th, 2004, 3:31am, carpao wrote:
5.476 for the average case...
|
|
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. 
|
|
IP Logged |
|
|
|
carpao
Newbie
Posts: 8
|
|
Re: Hard: Criminal Cupbearers
« Reply #46 on: Jun 10th, 2004, 1:27am » |
Quote Modify
|
on Jun 9th, 2004, 1:57pm, Grimbal 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. |
|
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 :
some times is better to drink less and throw away more (sorry for my english)
and here my best solution for the worst case:
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 )
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
BTW I discovered a little error in my calculation about the average case... it is a LITTLE BETTER...
5.47078
|
| « Last Edit: Jun 10th, 2004, 1:34am by carpao » |
IP Logged |
|
|
|
Three Hands
Uberpuzzler
Gender:
Posts: 715
|
|
Re: Hard: Criminal Cupbearers
« Reply #47 on: Jun 10th, 2004, 7:31am » |
Quote Modify
|
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...)
|
|
IP Logged |
|
|
|
carpao
Newbie
Posts: 8
|
|
Re: Hard: Criminal Cupbearers
« Reply #48 on: Jun 10th, 2004, 7:43am » |
Quote Modify
|
on Jun 10th, 2004, 7:31am, Three Hands wrote:| I thought that the aim was to find out precisely which bottle is poisoned, not just one of two. |
|
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...
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2872
|
|
Re: Hard: Criminal Cupbearers
« Reply #49 on: Jun 11th, 2004, 5:05am » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print