wu :: forums « wu :: forums - Solution to CRIMINAL CUPBEARERS » Welcome, Guest. Please Login or Register. Apr 17th, 2024, 7:52am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: towr, Eigenray, Icarus, william wu, ThudnBlunder, Grimbal, SMQ)    Solution to CRIMINAL CUPBEARERS « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: Solution to CRIMINAL CUPBEARERS  (Read 27171 times)
dayak
Newbie

Posts: 2
 Solution to CRIMINAL CUPBEARERS   « on: Apr 28th, 2006, 11:24pm » Quote Modify

The solution to the CRIMINAL CUPBEARERS riddle is:
The king divides the 1000 bottles in 2 groups of 500 bottles. He then mixes samples of all the wine per group into a cup. So he has 2 cups. One cup contains the poison the other doesn't. The 1st prisoner is to drink both cups determining which group of bottles contains the poison. The remaining 500 bottles are divided in half etcetera.
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7526
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #1 on: Apr 29th, 2006, 4:20am » Quote Modify

Welcome to the forum !

I have 2 remarks regarding your answer:
1. The king wants to drink the rest of the wine in 5 weeks.  The poison takes 4 weeks to kill.  With your solution, there will be only 500 safe bottles after 5 weeks.
2. Why prepare 2 cups?  If you prepare only 1 cup with 500 bottles, depending whether the prisonner dies or not, you know in which half the poison is.  (OK, this is assuming you are 100% sure there is only one poisoned bottle).

PS: I realized this is a new thread.  A previous discussion can be found
here .
 « Last Edit: Apr 29th, 2006, 4:25am by Grimbal » IP Logged
dayak
Newbie

Posts: 2
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #2 on: Apr 29th, 2006, 7:03am » Quote Modify

Maybe I didn't explain myself clear. The King can decide in 10 steps the exact bottle containing the poison. In each step he determines if the poison is in the one half group of bottles or in the other. He does this by mixing samples of wine of each bottle in one group. So per step you have 2 cups, one for each group.
step 1: 1000 bottles split in 2 groups = 500 + 500. One group will contain the poison, the other doesn't. He continues with the 500 bottles containing the posion. The other 500 are fine and can be used (within 5 weeks because the bottle is openend so the wine doesn't taste well after 5 weeks).
step 2: 500 bottles split in 2 groups = 250 + 250
step 3: 250 bottles split in 2 groups = 125 + 125
step 4: 125 bottles split in 2 groups = 62 + 63
step 5: 62 (or 63) bottles split in 2 groups = 31 + 31 (or 32)
step 6: 31 bottles split in 2 groups = 15 + 16
step 7: 15 (or 16) bottles split in 2 groups = 7 (or + 8
step 8: 8 bottles split in 2 groups = 4 + 4
step 9: 4 bottles split in 2 groups = 2 + 2
step 10: 2 bottles split in 2 groups = 1 + 1. He can now exactly say in which botle the poison was. All other bottles can be used safely. Enjoy!

The method for this solution is a common search algorith called binary search (used for a fast way of finding an item in a large collection of data like a telephone book).

PS appologies for the extra tread. I overlooked the previous

 IP Logged
Icarus
wu::riddles Moderator
Uberpuzzler

Boldly going where even angels fear to tread.

Gender:
Posts: 4863
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #3 on: Apr 30th, 2006, 11:44am » Quote Modify

The problem, dayak, is that the poison takes a month to have an effect. So it takes 4 weeks to find the outcome of each of your steps, and your total process takes 40 weeks, not 5.
 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
Newbie

Posts: 1
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #4 on: Dec 19th, 2006, 9:20pm » Quote Modify

2^10=1024

take 10 prisoners, and go through each of the wines...
For each wine, either a prisoner drinks it or does not drink it... and you can have a unique binary number for each bottle of wine. You dont need a week to do this, make em drink it all at once.. Based on the combination of prisoners who die, you can figure out the # of the wine bottle.

Peace

 IP Logged
KjSlag
Newbie

Posts: 4
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #5 on: Jan 4th, 2007, 10:23am » Quote Modify

Note:
I'm sorry if this solution has already been posted somewhere.

My Solution:
number the bottles 1-1000
number 10 prisoners 1-10
- Prisoner 1 samples bottles 1-512 (when a prisoner samples a bottle, he is only drinking enough wine so that he will die if that bottle is poisoned)
- Prisoner 2 samples 1-256 and 513-768
- Prisoner 3 samples 1-128, 257-384, 513-640, and 769-896
- Prisoner 4 samples 1-64, 129-192, 257-320, ... , and 897-960
- Prisoner 5 samples 1-32, 65-96, 129-160, ... , and 961-992
- Prisoner 6 samples 1-16, 33-48, 65-80, ... , and 993-1000 (not a mistake, if there were 1024 bottles, this would end at 993-1008)
- Prisoner 7 samples 1-8, 17-24, 33-40, ... , and 993-1000
- Prisoner 8 samples 1-4, 9-12, 17-20, ... , and 993-996
- Prisoner 9 samples 1-2, 5-6, 9-10, ... , and 997-998
- Prisoner 10 samples 1, 3, 5, 7, 9, ... , and 999
After a month, check to see which prisoners are alive. You can form a base 2 number where the first digit is 0 if prisoner 1 is dead and 1 if the prisoner is alive, the second digit is 0 if prisoner 2 is dead and 1 if the prisoner is alive, and so on. Add 1 to this number. The final number is the number of the bottle that is poisoned (in base 2).

Example 1:
If prisoner 1, 4, 7, 9, and 10 die, then the poison is in bottle 0110110100+1=0110110101 (in base 2), or 437 (in base 10).
Example 2:
If they all die, then the poison is in bottle 0000000000+1=0000000001 (in base 2), or 1 (in base 10).
False Example:
If no prisoners die, none of the 1000 bottles were poisoned. We would only have a case where no prisoners die if there were 1024 bottles that need to be tested. I'm just pointing this out so that nobody points it out as an error on my part.
 « Last Edit: Jan 4th, 2007, 10:26am by KjSlag » IP Logged
ujjawalmishra
Newbie

Posts: 2
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #6 on: May 12th, 2007, 2:14pm » Quote Modify

The king will divide 1000 bottles in 10 groups 100 of each.then he willl call ten prisoners make them to drink a mixture made from 100 bottles of a particular group.then he will divide remaining 100 bottles of each group into 10 parts of 10 bottles each and repeat same phenomena on the next day by making each drink 10 mixtures of which one is of his group(100 bottle) and other 9(gp of 10 bottle) is of others group.now same method is used to divide 10 bottles into each group of 1 bottle.now each willl drink sample of 1of each of his own 10 groups and 90 others bottle on third day..........................
after 30 days one prisoner dies ......so king can figure out group of 100 bottle containing poison.on the next day if no other prisoner dies ,it means that the poison was in the group of 10 bottle which dead prisoner had taken.but if  another prisoner dies so king now identify group of 10 bottles belonging to previous group.now as 10 bottles are identified king can enjoy 990 bottles but if he is greedy one,then he waits for another day and if no other person dies it means prisoner dying at second no. drank again poison,but if dies then simply the bottle which is  1 belong to 10 poison bottle group which belong to 100 poison bottle group,taken by the dying person.   king meanwhile enjoy bottles excluding poisonous groups.

i think i have saved 7 lives.

 « Last Edit: May 13th, 2007, 2:31am by ujjawalmishra » IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2872
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #7 on: May 13th, 2007, 6:23am » Quote Modify

on May 12th, 2007, 2:14pm, ujjawalmishra wrote:
 The king will divide 1000 bottles in 10 groups 100 of each.then he willl call ten prisoners make them to drink a mixture made from 100 bottles of a particular group.then he will divide remaining 100 bottles of each group into 10 parts of 10 bottles each and repeat same phenomena on the next day by making each drink 10 mixtures of which one is of his group(100 bottle) and other 9(gp of 10 bottle) is of others group.now same method is used to divide 10 bottles into each group of 1 bottle.now each willl drink sample of 1of each of his own 10 groups and 90 others bottle on third day.......................... after 30 days one prisoner dies ......so king can figure out group of 100 bottle containing poison.on the next day if no other prisoner dies ,it means that the poison was in the group of 10 bottle which dead prisoner had taken.but if  another prisoner dies so king now identify group of 10 bottles belonging to previous group.now as 10 bottles are identified king can enjoy 990 bottles but if he is greedy one,then he waits for another day and if no other person dies it means prisoner dying at second no. drank again poison,but if dies then simply the bottle which is  1 belong to 10 poison bottle group which belong to 100 poison bottle group,taken by the dying person.   king meanwhile enjoy bottles excluding poisonous groups.     i think i have saved 7 lives.

So what happens when prisoner 1 dies first, then prisoner 2, then no-one? is it bottle 121 or 122 that's poisoned?

Anyway, it's easy enough to arrange the binary method so that no more than 8 prisoners will die...
 IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7526
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #8 on: May 13th, 2007, 2:47pm » Quote Modify

Depends whether prisoner 1 or 2 dies a second time  .
 IP Logged
ujjawalmishra
Newbie

Posts: 2
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #9 on: May 13th, 2007, 3:35pm » Quote Modify

the king  will mark each bottle with a no  according to its group
e.g.    10 100's bottle group  -a,b,c.........i ,j etc
then a1,a2................a9,a0..etc of same group
then a11,a12........etc
assuming :poison will show its action exactly after 30 days.

now as  you  asked if prisoner 1 dies on day 1 and prisoner 2 dies on day 2 ,then no person dies on third day .the bottle poisoned can be found in this way......
prisoner 1 dies means  group 'a'  contain poisoned bottle.
now p2 dies on second day , which gives the next no.(because every prisoner has consumed sample one of the group i.e. of 'a1'or'a2' etc) let say it is   'a3'.
now on third day no one dies means p2 had taken poison again ,let say he has taken bottle no 'a35'(because every prisoner had to drink sample of one bottle of each group i.e. 'a35',a12,a23,...............,b12,b24,..............c14,c23............a nd so on.
now the bottle poisoned is 'a35'
i think it is  clear now .but still if you think i m wrong then please justify.
 IP Logged
Hippo
Uberpuzzler

Gender:
Posts: 919
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #10 on: May 14th, 2007, 12:37pm » Quote Modify

I don't thing the number of killed prisoners is the question. Number of prisoners to risk is in the question.
(Otherwise it is not difficult to beat your solution by 2 more prisoners easily).

If you are trying to minimize number of killed prisoners while the number of prisoners in the risk remains minimal than your solution has mentioned problem with 12- situation, when you cannot find all safe bottles. The binary method can be optimised a bit using 24 positions remaining to 210. I didn't check how many lives in the worst case must be lost...

And exact 30 days probably is not guaranated ... what does not cause problems to binary method but is crucial for your method. If there are k "distinguishable time windows" (and all experiments should be started before first result is known), the optimal solution would be different ...
 « Last Edit: May 14th, 2007, 12:47pm by Hippo » IP Logged
NetSquirrel
Newbie

Posts: 1
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #11 on: Aug 9th, 2007, 10:52pm » Quote Modify

I agree with deadman's binary method as the probable intended solution.

However, there is an apparent error in the phrasing of the riddle itself:

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

Clearly, assigning one prisoner to each bottle will only result in one death, not 10. Isn't that the most humane solution?
 IP Logged
andrusw
Newbie

Posts: 1
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #12 on: Sep 14th, 2007, 10:20am » Quote Modify

Here is how I tried to solve the problem.

Knowing that this was somehow related to the binary. (2^10 is approx 1000)

I then simplified the question by dealing with 8 bottles of wine and 3 prisioners, assuming that the 2^10 has something to do with the solution.

So, I came up with this ad-hoc solution:

Bottle 1: Prisoner 1 drinks
Bottle 2: Prisoner 2 drinks
Bottle 3: Prisoner 3 drinks

Bottle 4: Prisoner 1 & 2 drinks
Bottle 5: Prisoner 1 & 3 drinks
Bottle 6: Prisoner 2 & 3 drinks

Bottle 7: Prisoner 1 & 2 & 3 drinks

Bottle 8: No one drinks.

So for example if prisoner 1 & 3 dies, then you know it must be bottle 5 that was poisoned.

I guess this could be looked at as some type of Venn diagram, and/or combinatorics. I don't know if this solution would work for 1000 bottles and 10 prisoners.
 IP Logged
Hippo
Uberpuzzler

Gender:
Posts: 919
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #13 on: Sep 14th, 2007, 12:39pm » Quote Modify

According to criterias I have read it seems to me this belongs to easy...

There is 1024 binary numbers of length at least 10.
1 of them consists of 10 ones, 10 of them consist of 9 ones and one zero, 45 of them consist of 8 ones and 2  zeros. If you want to minimize the number of prisoners in risk and to minimize the number of killed as second criterium, use binary numbers of length at least 10 and remove 24 of them with the most ones. At most 8 prisoners would be killed from 10 in risk.

Write chosen numbers on bottles (one on each) and make mix for i-th prisoner using wine from bottles with i-th binary digit equal to 1.
Killed prisoners as ones and living as zeros writes the number of poisoned bottle in binary.

... everything was already written in thread pointed by grimbal at the 2nd post ...

If there is 11th prisoner victim as the 10, king can use 11digit numbers using at most 5 ones ... risking 11 prisoners and killing at most 5. Next step is 13 to risk killing at most 4. Then 19 risk, kill at most 3. Then 45 risk, kill at most 2, and 999 risk, kill at most 1.

Actually you are optimising sumi=0kill Cirisk>999. Where Ckn=n!/(k!(n-k)!).
 « Last Edit: Sep 15th, 2007, 1:46am by Hippo » IP Logged
SMQ
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 2084
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #14 on: Sep 14th, 2007, 12:57pm » Quote Modify

on Sep 14th, 2007, 12:39pm, Hippo wrote:
 According to criterias I have read it seems to me this belongs to easy...

Indeed (or possibly medium), however, since the original riddle is in the hard section on the riddles page, the thread stays in the hard forum despite its relative ease.

--SMQ
 IP Logged

--SMQ

hanns
Newbie

Gender:
Posts: 1
 Re: Solution to CRIMINAL CUPBEARERS   criminal_cupbearers1.gif « Reply #15 on: Dec 25th, 2007, 6:12pm » Quote Modify

new to this site... thanks to StumbleUpon i have wasted my christmas morning being dazed w/ thinking about this.

edited: i realized my solution is flawed after dinner.
 « Last Edit: Dec 26th, 2007, 12:31am by hanns » IP Logged

Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7526
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #16 on: Dec 26th, 2007, 1:43am » Quote Modify

on Dec 25th, 2007, 6:12pm, hanns wrote:
 edited: i realized my solution is flawed after dinner.

How was the wine?
 IP Logged
StallionMang
Junior Member

Gender:
Posts: 73
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #17 on: Jan 2nd, 2008, 1:07am » Quote Modify

If we are using combinations of prisoners, then the formula, assuming a total pool of 10 and a choose size of n, is :

10! / ((10-n)! * n!)

So, let's look at the number of total combinations of prisoners you can make:

For combos of 1 : 10! / (9!1!) = 10 combos
For combos of 2 : 10! / (8!2!) = 45 combos
For combos of 3 : 10! / (7!3!) = 120 combos
For combos of 4 : 10! / (6!4!) = 210 combos
For combos of 5 : 10! / (5!5!) = 252 combos
For combos of 6 : 10! / (4!6!) = 210 combos
For combos of 7 : 10! / (3!7!) = 120 combos
For combos of 8 : 10! / (2!8!) = 45 combos
For combos of 9 : 10! / (1!9!) = 10 combos
For combos of 10: 10! / 10! =    1 combo

Total number of combinations = 1023

I know this basic premise has already been established in this thread.  I just felt like writing it out in gory detail.

BTW, I'm new here.  Howdy!
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2872
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #18 on: Jan 2nd, 2008, 9:25am » Quote Modify

on Jan 2nd, 2008, 1:07am, StallionMang wrote:
 If we are using combinations of prisoners, then the formula, assuming a total pool of 10 and a choose size of n, is :   10! / ((10-n)! * n!)   So, let's look at the number of total combinations of prisoners you can make:   For combos of 1 : 10! / (9!1!) = 10 combos For combos of 2 : 10! / (8!2!) = 45 combos For combos of 3 : 10! / (7!3!) = 120 combos For combos of 4 : 10! / (6!4!) = 210 combos For combos of 5 : 10! / (5!5!) = 252 combos For combos of 6 : 10! / (4!6!) = 210 combos For combos of 7 : 10! / (3!7!) = 120 combos For combos of 8 : 10! / (2!8!) = 45 combos For combos of 9 : 10! / (1!9!) = 10 combos For combos of 10: 10! / 10! =    1 combo   Total number of combinations = 1023   I know this basic premise has already been established in this thread.  I just felt like writing it out in gory detail.   BTW, I'm new here.  Howdy!

You missed a possibility:

combo of 0: 10!/(10!0!)...
 IP Logged
StallionMang
Junior Member

Gender:
Posts: 73
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #19 on: Jan 2nd, 2008, 4:17pm » Quote Modify

Yeah, good point.  That brings the total to 1024.

But I totally wouldn't use the zero combo.  That would be the bottle that no one tastes, and then if no one dies, I am to assume it must have been the poison one.  But if I were the evil king, I would definitely want confirmation through a positive result rather than a negative.  In other words, I wouldn't be able to sleep easy at night until someone was poisoned to death.  That's just how I roll.

 IP Logged
gallagher118
Newbie

Posts: 2
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #20 on: May 31st, 2008, 11:55pm » Quote Modify

I can't help but think this is a poorly constrained problem.  Obviously the easy way is 1 bottle per prisoner, and you only kill 1.

I think the solution the riddle is shooting for, is to use prime factors.   I came to this by thinking about the 10 killed constraint.

If you assign a prisoner to all the primes < 1000, and make them drink the bottles they divide into, you would almost know the right bottle.  The problem would be the multiples like 2^3*17.

So the modification to that would be to have additional prisoners for all those multiples IE:

2*2
2*2*2
2*2*2*2...out to 2^8
3*3 out to 3^6
5*5 out to 5^4
ect down to
31*31

So you'd need 168 to cover the primes, 1 to cover 1, and 7+5+3+2+1+1+1+1+1+1 to cover the multiple factors.  ==192 prisoners

After they drank, you'd look at whom died, and then you'd know the factorization of the poisoned bottle.

At most 9 would die, at bottle 512 which is why I think this is the right solution.

Actually, you could have 1 drink them all, then at most 10 would die.  (and if only he died, then you'd know it was one)

 « Last Edit: May 31st, 2008, 11:58pm by gallagher118 » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7526
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #21 on: Jun 1st, 2008, 12:12am » Quote Modify

I think the solution the riddle is shooting for is to number the bottles in binary.
 IP Logged
gallagher118
Newbie

Posts: 2
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #22 on: Jun 1st, 2008, 10:31am » Quote Modify

I agree the binary solution is probably the best.  (you only need 10 guys)

I had considered it, but it didn't explain the wording of the problem.   With this solution, never will all 10 die.  (which is why I moved on)

The phrasing of the problem needs a tweak,  I would suggest stating he only needs to RISK 10 prisoners lives.
 IP Logged
Hippo
Uberpuzzler

Gender:
Posts: 919
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #23 on: Jun 2nd, 2008, 1:14am » Quote Modify

on Jun 1st, 2008, 10:31am, gallagher118 wrote:
 I agree the binary solution is probably the best.  (you only need 10 guys)

This actually is only well chosen notation. You can use it on your primality solution as well. It will show the waste of measuring quickly.

on Jun 1st, 2008, 10:31am, gallagher118 wrote:
 The phrasing of the problem needs a tweak,  I would suggest stating he only needs to RISK 10 prisoners lives.

The risking/killing was discussed earlier, too.
 « Last Edit: Jun 2nd, 2008, 1:16am by Hippo » IP Logged
IanRon
Newbie

Posts: 1
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #24 on: Feb 17th, 2009, 1:45pm » Quote Modify

You can solve this problem with 6 prisoners, and 3 will die every time.  For this solution, it is assumed that 1 month equals 30 days.  So if a prisoner tried the poisoned bottle on Day 1, he would die on Day 31.

Number the bottles 001 through 1000.  Divide the prisoners into 3 groups of 2.  On Day 1, Prisoner 1 tries all bottles with a 0 as the last digit (i.e. 010, 020... 1000 etc.).  On Day 1, Prisoner 2 will try any bottle ending in 5 (i.e. 005, 015... 995).  This is pattern is continued with Prisoners 3 through 6, so that the breakdown is as follows:

DAY  1     2     3     4     5
PRISONER
1          XX0  XX1  XX2  XX3  XX4
2          XX5  XX6  XX7  XX8  XX9
3          X0X  X1X  X2X  X3X  X4X
4          X5X  X6X  X7X  X8X  X9X
5          0XX  1XX  2XX  3XX  4XX
6          5XX  6XX  7XX  8XX  9XX

Where X is any number 0-9.

With this arrangement, you can now know which bottle is the poisoned one based on which prisoners die during Days 31 to 35.  For example, if the poisoned bottle is number 369, then Prisoner 2 will die on Day 35, Prisoner 4 will die on Day 32, and Prisoner 5 will die on Day 34.  If Prisoners 1, 3, and 5 die on Day 31, then you know the poisoned bottle was 1000.

So, by the end of Day 35, you are guaranteed to know which bottle was the culprit (though you could know earlier).
 « Last Edit: Feb 17th, 2009, 1:47pm by IanRon » IP Logged
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

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