wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
riddles >> hard >> Solution to CRIMINAL CUPBEARERS
(Message started by: dayak on Apr 28th, 2006, 11:24pm)

Title: Solution to CRIMINAL CUPBEARERS
Post by dayak on Apr 28th, 2006, 11:24pm
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.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Grimbal on Apr 29th, 2006, 4:20am
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 (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1027806173;start=0).

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by dayak on Apr 29th, 2006, 7:03am
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) + 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


Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Icarus on Apr 30th, 2006, 11:44am
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.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by deadman0601 on Dec 19th, 2006, 9:20pm
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 :)


Title: Re: Solution to CRIMINAL CUPBEARERS
Post by KjSlag on Jan 4th, 2007, 10:23am
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.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by ujjawalmishra on May 12th, 2007, 2:14pm
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.  
8)

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by rmsgrey on May 13th, 2007, 6:23am

on 05/12/07 at 14:14:35, 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.  
8)

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

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Grimbal on May 13th, 2007, 2:47pm
Depends whether prisoner 1 or 2 dies a second time  :P.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by ujjawalmishra on May 13th, 2007, 3:35pm
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............and 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.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Hippo on May 14th, 2007, 12:37pm
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 ...

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by NetSquirrel on Aug 9th, 2007, 10:52pm
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?

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by andrusw on Sep 14th, 2007, 10:20am
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.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Hippo on Sep 14th, 2007, 12:39pm
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)!).

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by SMQ on Sep 14th, 2007, 12:57pm

on 09/14/07 at 12:39:57, 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 (http://www.ocf.berkeley.edu/~wwu/riddles/hard.shtml#criminalCupbearers) on the riddles page (http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml), the thread stays in the hard forum despite its relative ease.

--SMQ

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by hanns on Dec 25th, 2007, 6:12pm
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.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Grimbal on Dec 26th, 2007, 1:43am

on 12/25/07 at 18:12:45, hanns wrote:
edited: i realized my solution is flawed after dinner.

How was the wine?  ;D

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by StallionMang on Jan 2nd, 2008, 1:07am
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!

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by rmsgrey on Jan 2nd, 2008, 9:25am

on 01/02/08 at 01:07:18, 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!)...

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by StallionMang on Jan 2nd, 2008, 4:17pm
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.


Title: Re: Solution to CRIMINAL CUPBEARERS
Post by gallagher118 on May 31st, 2008, 11:55pm
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)




Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Grimbal on Jun 1st, 2008, 12:12am
I think the solution the riddle is shooting for is to number the bottles in binary.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by gallagher118 on Jun 1st, 2008, 10:31am
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.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Hippo on Jun 2nd, 2008, 1:14am

on 06/01/08 at 10:31:26, 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 06/01/08 at 10:31:26, 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.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by IanRon on Feb 17th, 2009, 1:45pm
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.
[hide]
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).[/hide]

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by v3ritas on Apr 9th, 2009, 1:08pm
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.

:>

edit: shaith. with this method only 300 wines are tasted. it can be modified by having one third (plus or minus one prisoner) of the prisoners try three wines, one at, say, 9am, another at 3am, and another at 9pm; and the other third (plus or minus one, depending on what you did with the other third) have four wines throughout the day. then follow what i said before, except keep track of the wines that were sipped by hour.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by RyanJJohn on Oct 9th, 2009, 1:06pm
The solution to this riddle is ineffective since in 5 weeks the open bottles of wine would have surely turned to vinegar and the King would not want to drink them anyway.  It's a very interesting riddle, in any case.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Turok on Nov 24th, 2011, 12:33am
Hello!

Before i post this idea for the solution let me just mention what the problem gives us as info. The time is only to be measured in weeks, not days, hours or even minutes. Because it says 1 month and then 5 weeks, so the only measurable time we can use is one week.

the king groups the bottles in groups of 10. He will have 100 groups. He places all these 100 groups in a square with 10 groups lenght. Prisoner 1 tastes one row and one column. prisoner 2 tastes another row and another column, as the others do with the reaming rows and columns. After 1 week they mix the bottles keeping only one in every group. None of the other 9 bottles in a group should remain in the same group or a group should not be divided in the same row or column. Again the prisoners taste the wine as they did it the first time.
After 4 weeks one or 2 prisoners will die, this will show him the group of ten bottles were the poison is. After another week none or one or two prisoners die. This will tell him where the poisoned bottle is. There will be 2 prisoners missing. If none die the bottle is where the dead prisoners would have tasted. The thing is that he must make the prisoners taste the same rows and columns they did the first time, only the bottles will be different.

i think this is a good solution because we use 10 prisoners and 1 week interval.

please tell me what you think of it.


Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Sriramadesikan on Nov 24th, 2011, 3:42am
I worked  out a solution for 'Criminal Cupbearers.
I read a different version of this puzzle which is titled 'The Emperor'. My solution is in line with the version I read but should not be a problem in understanding it with different versions of the problem.

Significantly, I accidentally fell into a series 1,112, 223, 334...889, 1000 on solving this problem! But i don't have deep insight to study this series from Mathematical perspective

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Grimbal on Nov 24th, 2011, 6:27am
I don't think the prisoners are supposed to die exactly 24 hours after drinking.  If it were the case, you could just have one prisoner drink a drop of each bottle, one every second, and just measure his time of death.  I think they die anytime within 24 hours after drinking.

Anyway, in your solution, who dies when if the poison is in bottle 11?  And what if the poison is in bottle 12?

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by rmsgrey on Nov 24th, 2011, 9:06am

on 11/24/11 at 00:33:25, Turok wrote:
Hello!

Before i post this idea for the solution let me just mention what the problem gives us as info. The time is only to be measured in weeks, not days, hours or even minutes. Because it says 1 month and then 5 weeks, so the only measurable time we can use is one week.

the king groups the bottles in groups of 10. He will have 100 groups. He places all these 100 groups in a square with 10 groups lenght. Prisoner 1 tastes one row and one column. prisoner 2 tastes another row and another column, as the others do with the reaming rows and columns. After 1 week they mix the bottles keeping only one in every group. None of the other 9 bottles in a group should remain in the same group or a group should not be divided in the same row or column. Again the prisoners taste the wine as they did it the first time.
After 4 weeks one or 2 prisoners will die, this will show him the group of ten bottles were the poison is. After another week none or one or two prisoners die. This will tell him where the poisoned bottle is. There will be 2 prisoners missing. If none die the bottle is where the dead prisoners would have tasted. The thing is that he must make the prisoners taste the same rows and columns they did the first time, only the bottles will be different.

i think this is a good solution because we use 10 prisoners and 1 week interval.

please tell me what you think of it.

So, if you label the prisoners 0,1,2,3,4,5,6,7,8,9 and the 100 groups as 00,01,02,03,04,05,06,07,08,09,10,11,...,98,99 according to the row and column they're in, and the individual bottles in each group by their group and which prisoner drinks from them a week later (so group 00's bottles are labelled 000, 001, 002, 003, 004, 005, 006, 007, 008 and 009).

If prisoner 1 dies and no-one else does, then you know it's bottle 111. So far, so good.

If prisoner 1 dies after four weeks, then prisoner 2 after another week, then you know it's bottle 112. Still good.

If prisoners 1 and 2 die after four weeks, and no-one else does, then you know it's one of the bottles 121, 122, 211 and 212. Not so good.

If prisoners 1 and 2 die after four weeks, followed by 3 after another week, then you know the bottle is either 123 or 213. Still not perfect.


You have 100 bottles where you can pin down the exact bottle, 720 where you have a choice of two, and 180 where you have a choice of four. So you have only a 10% chance of having all 999 unpoisoned bottles available to drink from (less three drops each from 720 of them, two drops each from 270, and one drop each from 10, plus the one or two drops counted twice from the poisoned bottle).

It's possible to guarantee having all 999 safe bottles available (less up to ten drops from each) without relying on the timing of the poison being reliable.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Sriramadesikan on Nov 25th, 2011, 1:51am
Of course, All the 10 Prisoners can taste all the 1000 bottles one by one and if the time can be measured for all drinks, we can identify the Poisoned bottle. But it is not practical to administer the test this way effectively within a specific time frame. If the time can be indefinite, it is no more a problem!

My solution is practical and can be comfortably performed successfully(Let me assume that the poison leaves a temporary stain  on the toungue of the drinkers instead of killing!) within  an acceptable time frame.

My solution works on the assumption that a death follows a drink of poison exactly after   a specific time lapse irrespective of the amount of poison taken in and the health of the Prisoners. The specific time need not necessarily be 24hrs but is constant! That is, the effect of the poison is visible exactly in X hrs!.

I clearly explained how to identify the 11th and 12th bottles if any one of them contains poison. For your understanding, I pull that part of my solution and reproduce here. The particular part dealing with the case of 11th  and 12th bottles is in bold italics.

Part of the Solution:
...Analysis: Exactly 24 hrs after the first round drink, if suppose the first Prisoner falls, then we ascertain that the poison bottle is in the first group. That is, among 1-100. Then exactly 24hrs after the second round drink, if suppose the second Prisoner falls, then the poison bottle lies between 11-20. Again exactly 24hrs after the third drink, if suppose the third Prisoner falls, then the poison bottle is the 13th one! In the above scenario, if the fall of second and third Prisoners is interchanged, then the poison bottle is the 22nd one.

For any set of 3 Prisoners out of 10, we have 10C3 = 120 combinations. Each combination covers 6 bottles.
So, totally 120X6=720 bottles are covered.

If only 2 Prisoners fall, the first Prisoner in the first round and the second Prisoner in the second round, then the poison bottle is the 12th one.If the second Prisoner falls in the third round, then the poison bottle is the 2nd one. If the second Prisoner falls in the second round and the first Prisoner falls in the third round, then the poison bottle is the 11th one.For a given set of 2 Prisoners and 3 falling time slots, 6 bottles are covered. We have totally 10C2 Combinations.
10C2=45 combinations.
So, 45X6=270 bottles are covered...


The significance of this approach is that the casualty is in its minimum at just 3!

P.S: Any idea about the number series I fell into while solving this?
series:1,112,223,334,...889,1000

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Turok on Nov 25th, 2011, 5:34am

on 11/24/11 at 09:06:08, rmsgrey wrote:
So, if you label the prisoners 0,1,2,3,4,5,6,7,8,9 and the 100 groups as 00,01,02,03,04,05,06,07,08,09,10,11,...,98,99 according to the row and column they're in, and the individual bottles in each group by their group and which prisoner drinks from them a week later (so group 00's bottles are labelled 000, 001, 002, 003, 004, 005, 006, 007, 008 and 009).

If prisoner 1 dies and no-one else does, then you know it's bottle 111. So far, so good.

If prisoner 1 dies after four weeks, then prisoner 2 after another week, then you know it's bottle 112. Still good.

If prisoners 1 and 2 die after four weeks, and no-one else does, then you know it's one of the bottles 121, 122, 211 and 212. Not so good.

If prisoners 1 and 2 die after four weeks, followed by 3 after another week, then you know the bottle is either 123 or 213. Still not perfect.


You have 100 bottles where you can pin down the exact bottle, 720 where you have a choice of two, and 180 where you have a choice of four. So you have only a 10% chance of having all 999 unpoisoned bottles available to drink from (less three drops each from 720 of them, two drops each from 270, and one drop each from 10, plus the one or two drops counted twice from the poisoned bottle).

It's possible to guarantee having all 999 safe bottles available (less up to ten drops from each) without relying on the timing of the poison being reliable.



a small change :)

when you reorganize the bottles you don't put any in the same row or column, so 2 (ore 1) more prisoners will die after another week showing you the 10 bottles group where the poison is. The bottle that comes from the 10 bottle group of the first deceased prisoner/s is the poisoned one.

and, if you have 2 prisoners dead after 4 weeks it means that the bottle can be in 2 groups (its either a reading after the row or the column) and if you also get 2 deaths in another week (5th) you have 2 groups, BUT only one bottle will be common for all of these 4 groups, the poisoned one.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by ThudnBlunder on Nov 25th, 2011, 6:42am

on 11/25/11 at 01:51:54, Sriramadesikan wrote:
P.S: Any idea about the number series I fell into while solving this?
series:1,112,223,334,...889,1000

The above sequence is the arithmetric progression un = 111n + 1 (for n = 0 to 9)

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Grimbal on Nov 25th, 2011, 9:31am

on 11/25/11 at 01:51:54, Sriramadesikan wrote:
Part of the Solution:
...Analysis: Exactly 24 hrs after the first round drink, if suppose the first Prisoner falls, then we ascertain that the poison bottle is in the first group. That is, among 1-100.
[...]
If the second Prisoner falls in the second round and the first Prisoner falls in the third round, then the poison bottle is the 11th one.


So if the poison is in bottle 11, according to the 1st paragraph, the first prisoner dies in the first round.
And according to the 2nd paragraph, he dies again in the 3rd round.

Shouldn't he die also at the end of round #2?

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by rmsgrey on Nov 25th, 2011, 2:43pm

on 11/25/11 at 05:34:41, Turok wrote:
a small change :)

when you reorganize the bottles you don't put any in the same row or column, so 2 (ore 1) more prisoners will die after another week showing you the 10 bottles group where the poison is. The bottle that comes from the 10 bottle group of the first deceased prisoner/s is the poisoned one.

and, if you have 2 prisoners dead after 4 weeks it means that the bottle can be in 2 groups (its either a reading after the row or the column) and if you also get 2 deaths in another week (5th) you have 2 groups, BUT only one bottle will be common for all of these 4 groups, the poisoned one.

Okay, yeah, if you have up to two out of ten people drink from each bottle in the first wave, and then up to two more from each bottle in the second wave, you can find the unique poisoned bottle out of up to 2181 bottles.

On the other hand, if you allow two waves of deaths, you can do much better - in fact you can pick the unique poisoned bottle out of 59049 bottles...

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Sriramadesikan on Nov 28th, 2011, 1:12am
No... :'(  The 11th bottle is consumed by the first Prisoner only in the third round! Please note that each Prisoner is alloted 100 bottles and they take the mixture of them in the first round. While doing this, they leave a particular column of bottles. 11th bottle falls in the first column of group1 and so it is left in the first round of drink by the first Prisoner.

From the Solution:
...Now, all the 10 Prisoners are asked to prepare a mixture of their respective column mixtures. (i.e., Mixture of CMs within his/her group). While preparing this, the first Prisoner is instructed to leave aside CM1 (The corresponding cell is highlighted in yellow); second Prisoner is instructed to leave aside CM2 so on...

You say that the first Prisoner dies again in the third round :o

Can one die multiple times? ;)

Please note that i explained different possiblities and scenarios by aptly using 'IF' clause.

First Prisoner may fall in the second round in number of scenarios but all those were not explained in my solution.

In the scenario explained, first Prisoner may fall  either in the first round or in the third round and never in the second round!

May I kindly request you to study the tables I illustrated in my solution carefully and go through the explanation including the Analysis once again?

Please replace 1,2,3...,100 in the second table with 101,102,103...,200 respectively and 901,902,903...1000 respectively in the last table of the attached solution file for clarity.

New Observation: When the poisoned bottle lies in any group, the owner of the particular group never falls in the second round! Because, each Prisoner leaves the respective colum of bottles in his/her group in the second round and takes it only in the third round!

I hope i explain your questions in an understandable way.



Title: Re: Solution to CRIMINAL CUPBEARERS
Post by yevvi on Mar 2nd, 2015, 2:55am
Here is my solution: number each bottle 0 to 999 in binary.  Each number should be no more than 10 bits.  Let each of 10 prisoners determine each bit:

Prisoner 1 drinks bottles 0, 2, 4, 6, ....  If after a month he is dead, the 1st bit is 0, otherwise the 1st bit is 1.
Prisoner 2 drinks bottles 0, 1, 4, 5, 8, 9, ... - all numbers with 2nd bit of 0, again if dead 2nd bit is 0, otherwise 1.
Prisoner 3 drinks bottles 0,1,2,3,8,9,10,11,...., that is with 3rd bit of 0, ....
.......
Prisoner 10 drinks bottles 0 to 511, that is with the last bit of 0.

So after a month, depending on which of 10 are still alive, we know all 10 bits and thus the number of the poisoned bottle.

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Hippo on Jun 26th, 2017, 12:02pm
Hi,
have you tought about a variant of the problem, where poison kills in 14 days instead of original 30?

How you can reduce the number of people in risk (and number of people killed as 2nd criteria).

How many bottles can you test with K persons to risk and at most D dying, having 2 rounds of test? (K,D<10)

And more generally:
How many bottles can you test with K persons to risk and at most D dying, having R rounds of test?

Title: Re: Solution to CRIMINAL CUPBEARERS
Post by Hippo on Jul 2nd, 2017, 7:36am
OK let B(K,D,R) be the number in question and C(K,D)=K!/((K-D)!D!).
[hide]
B(K,D,0)=1
for D<=K:
B(K,D,R+1)=\sumi<=D C(K,D-i)*B(K-D+i,i,R).

And some values for 1000 bottles:
R=1:
B(998,1,1)=999<1000=B(999,1,1)
B(44,2,1)=991<1000<B(45,2,1)=1036
B(18,3,1)=988<1000<B(19,3,1)=1160
B(12,4,1)=794<1000<B(13,4,1)=1093
B(10,7,1)=968<1000<B(11,5,1)=1024
B(10,8,1)=1013
B(9,9,1)=512<1000
R=2:
B(499,1,2)=999<1000<B(500,1,2)=1001
B(22,2,2)=969<1000<B(23,2,2)=1059
B(9,3,2)=835<1000<B(10,3,2)=1161
B(6,4,2)=794<1000<B(7,4,2)=1471
B(5,5,2)=638<1000<B(6,5,2)=1586
R=3:
B(332,1,3)=997<1000=B(333,1,3)
B(14,2,3)=890<1000<B(15,2,3)=1021
B(6,3,3)=694<1000<B(7,3,3)=1156
B(4,4,3)=658<1000<B(5,4,3)=1666
R=4:
B(249,1,4)=997<1000<B(250,1,4)=1001
B(11,2,4)<1000<B(12,2,4)
B(6,2,4)=265<1000<B(6,3,4)=1545
B(5,3,4)=821<1000<B(4,4,4)=1813
R=5:
B(199,1,5)=996<1000<B(200,1,5)=1001
B(9,2,5)=946<1000<B(10,2,5)=1176
B(4,3,5)=671<1000<B(5,3,5)=1526
R=6:
B(166,1,6)=997<1000<B(167,1,6)=1003
B(7,2,6)=799<1000<B(8,2,6)=1057
B(3,3,6)=343<1000<B(4,3,6)=1105
R>7:
B(142,1,7)<1000<B(143,1,7)
B(6,2,7)=778<1000<B(7,2,7)=1079
B(5,2,9)=856<1000<B(6,2,8 )=1009
B(4,2,12)=993<1000<B(5,2,10)=1051
B(3,2,18 )=919<1000<B(4,2,13)=1067
B(2,2,31)=961<1000<B(3,2,19)=1027
B(2,2,32)=1024
B(3,3,8 )=729<1000=B(3,3,9)

B(1,1,999)=1000
B(999/R,1,R)~1000

B(K,1,R)=K*R+1
B(K,2,R)=C(K*R,2)+R+1
[/hide]



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