wu :: forums « wu :: forums - Solution to CRIMINAL CUPBEARERS » Welcome, Guest. Please Login or Register. Apr 17th, 2024, 8:22am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Grimbal, ThudnBlunder, towr, Icarus, SMQ, william wu, Eigenray)    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 27172 times)
v3ritas
Newbie

Posts: 4
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #25 on: Apr 9th, 2009, 1:08pm » Quote Modify

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.
 « Last Edit: Apr 9th, 2009, 5:33pm by v3ritas » IP Logged
RyanJJohn
Newbie

Posts: 1
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #26 on: Oct 9th, 2009, 1:06pm » Quote Modify

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.
 IP Logged
Turok
Newbie

Posts: 2
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #27 on: Nov 24th, 2011, 12:33am » Quote Modify

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.

 IP Logged
Newbie

Gender:
Posts: 3
 Re: Solution to CRIMINAL CUPBEARERS   Criminal_Cupbearers.pdf « Reply #28 on: Nov 24th, 2011, 3:42am » Quote Modify

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
 « Last Edit: Nov 24th, 2011, 3:58am by Sriramadesikan » IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7526
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #29 on: Nov 24th, 2011, 6:27am » Quote Modify

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?
 « Last Edit: Nov 24th, 2011, 6:29am by Grimbal » IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2872
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #30 on: Nov 24th, 2011, 9:06am » Quote Modify

on Nov 24th, 2011, 12:33am, 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.
 IP Logged
Newbie

Gender:
Posts: 3
 Re: Solution to CRIMINAL CUPBEARERS   Criminal_Cupbearers1.pdf « Reply #31 on: Nov 25th, 2011, 1:51am » Quote Modify

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
 « Last Edit: Nov 25th, 2011, 2:27am by Sriramadesikan » IP Logged
Turok
Newbie

Posts: 2
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #32 on: Nov 25th, 2011, 5:34am » Quote Modify

on Nov 24th, 2011, 9:06am, 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.
 « Last Edit: Nov 25th, 2011, 7:31am by Turok » IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #33 on: Nov 25th, 2011, 6:42am » Quote Modify

on Nov 25th, 2011, 1:51am, 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)
 IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7526
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #34 on: Nov 25th, 2011, 9:31am » Quote Modify

on Nov 25th, 2011, 1:51am, 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?
 IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2872
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #35 on: Nov 25th, 2011, 2:43pm » Quote Modify

on Nov 25th, 2011, 5:34am, 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...
 IP Logged
Newbie

Gender:
Posts: 3
 Re: Solution to CRIMINAL CUPBEARERS   Criminal_Cupbearers2.pdf « Reply #36 on: Nov 28th, 2011, 1:12am » Quote Modify

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

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.

 « Last Edit: Nov 28th, 2011, 2:27am by Sriramadesikan » IP Logged
yevvi
Newbie

Gender:
Posts: 8
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #37 on: Mar 2nd, 2015, 2:55am » Quote Modify

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.
 IP Logged
Hippo
Uberpuzzler

Gender:
Posts: 919
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #38 on: Jun 26th, 2017, 12:02pm » Quote Modify

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?
 « Last Edit: Jun 26th, 2017, 12:03pm by Hippo » IP Logged
Hippo
Uberpuzzler

Gender:
Posts: 919
 Re: Solution to CRIMINAL CUPBEARERS   « Reply #39 on: Jul 2nd, 2017, 7:36am » Quote Modify

OK let B(K,D,R) be the number in question and C(K,D)=K!/((K-D)!D!).

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
 « Last Edit: Jul 2nd, 2017, 11:15pm by Hippo » 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 »