Author |
Topic: Hard: Criminal Cupbearers (Read 22606 times) |
|
DewiMorgan
Guest
|
|
Re: Hard: Criminal Cupbearers
« Reply #75 on: Jun 2nd, 2006, 10:44pm » |
Quote Modify
Remove
|
It would IMHO be better rephrased as "he has only ten cupbearers, but doesn't want to lose more than 8 of them". Though I do also like the rephrasing to make the amount of wine the important thing - the discarding of a while bottle was a pleasant surprise.
|
« Last Edit: Jun 2nd, 2006, 10:45pm by DewiMorgan » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Hard: Criminal Cupbearers
« Reply #76 on: Jun 5th, 2006, 3:12pm » |
Quote Modify
|
Another variation: The king gets informed that one of the prisonners has developed a resistance to the poison. He doesn't know which. How many prisonners does he need now?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hard: Criminal Cupbearers
« Reply #77 on: Jun 6th, 2006, 12:43am » |
Quote Modify
|
on Jun 5th, 2006, 3:12pm, Grimbal wrote:Another variation: The king gets informed that one of the prisonners has developed a resistance to the poison. He doesn't know which. How many prisoners does he need now? |
| 14 I think
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Hard: Criminal Cupbearers
« Reply #78 on: Jun 6th, 2006, 3:39am » |
Quote Modify
|
I know that a classical solution gives that as an upper bound, I was wondering whether it could be improved. After all, no prisonner can die while he is not supposed to...
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Hard: Criminal Cupbearers
« Reply #79 on: Jun 6th, 2006, 5:39am » |
Quote Modify
|
OK, I found the necessary references, I agree with towr. The Varshamov-Tenengolts code and Sloane's A000016
|
|
IP Logged |
|
|
|
Aravis
Junior Member
Posts: 56
|
|
Re: Hard: Criminal Cupbearers
« Reply #80 on: Jul 14th, 2006, 7:49am » |
Quote Modify
|
I was working this problem, and came up with what people are calling the binary solution (I used the hypercube method actually, because it is easy to generalize from the 4 wine bottles and 8 wine bottles cases), but if I were king, I figure making a list of all the wine bottles in hypercube format would be a bummer. So I made a simple boolean statement that determines whether a prisoner should drink a given bottle of wine. We already know that given B bottles of wine we need at least log2B prisoners (the next integer above it obviously, no fractional prisoners), an let this numper be P, the number of prisoners. Label each bottle of wine W starting from 0 (ranging to B-1) Label each prisoner N staring from 0 (ranging to P-1) If the following statement is true, prisoner N drinks from bottle W. W mod 2P-N < 2P-N-1
|
|
IP Logged |
Duct tape is like the force. It has a light side, a dark side, and it holds the universe together. -Carl Zwanzig
|
|
|
aditrip
Newbie
Posts: 2
|
|
Re: Hard: Criminal Cupbearers -Only 3 needs to die
« Reply #81 on: Sep 6th, 2006, 11:57pm » |
Quote Modify
|
I have a pretty simple solution , Do you find anything wrong with this solution: 1. number the prisoners from 000, 001..100,101..256,257.....999. 2.Number the prisoners from 0 to 9. 3. Let the prisoner no say, 2, 5 and 6 taste the wine from bottle 256. Likewise, all bottles numberd xyz is tasted by prisoner no x, y and z. 4. If, say prisoners 2, 5 and 6 die, then bottle no 256 is poisoned. Similarly is prisoner no x,y and z die then bottle no xyz is poisoned. 5.Best case, one prisoner die (bottle no 000) 6.Worst case - 3 prisoners die. Aditya Mani Tripathi
|
|
IP Logged |
|
|
|
aditrip
Newbie
Posts: 2
|
|
Re: Hard: Criminal Cupbearers
« Reply #82 on: Sep 7th, 2006, 12:19am » |
Quote Modify
|
That's wrong. 256 and 526, can't differentiate. Same approach with binary can find the result. One of my friends Anil Goyal found this out.
|
|
IP Logged |
|
|
|
v3ritas
Newbie
Posts: 4
|
|
Re: Hard: Criminal Cupbearers
« Reply #83 on: Apr 9th, 2009, 1:11pm » |
Quote Modify
|
i posted this in the other thread, and someone probably has the same solution i have but i don't feel like going through five pages of proposed solutions. here's mine though: 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. :>
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hard: Criminal Cupbearers
« Reply #84 on: Apr 9th, 2009, 1:33pm » |
Quote Modify
|
on Apr 9th, 2009, 1:11pm, v3ritas wrote: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. |
| 10 prisoners * 30 days = 300 bottles, which falls short of 1000 by 70%. Quote: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. |
| But most of the wine will still not be cleared after 5 weeks as required. Only 70 bottles have been tasted in the first week, so you can only clear those, unless by chance you found the poison by then. Not to mention it depends on the poison killing after exactly one month. Which is rather unlikely. It can be solved without that assumption.
|
« Last Edit: Apr 9th, 2009, 1:36pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
v3ritas
Newbie
Posts: 4
|
|
Re: Hard: Criminal Cupbearers
« Reply #85 on: Apr 9th, 2009, 5:42pm » |
Quote Modify
|
yeah i realized the 300 bit earlier. here's my edit from the other post: Quote: 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. |
| the riddle says that it takes one month for the effects to surface. it says one month, not a month and a few days. one month. so when you see a prisoner show effects of the poison, track down which wine he drank.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hard: Criminal Cupbearers
« Reply #86 on: Apr 9th, 2009, 11:54pm » |
Quote Modify
|
on Apr 9th, 2009, 5:42pm, v3ritas wrote:the riddle says that it takes one month for the effects to surface. it says one month, not a month and a few days. one month. |
| A month is not a precise unit. Or do you expect that the poison takes 28 days to work when you ingest it in February, and 31 days if you ingest it in March? At the very least a month can be anything from 28 to 31 days. And I wouldn't bet a poison would take much notice of those bounds. Nor does the solution make a use of it; as long as it kills within 5 weeks it will work.
|
« Last Edit: Apr 9th, 2009, 11:55pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
v3ritas
Newbie
Posts: 4
|
|
Re: Hard: Criminal Cupbearers
« Reply #87 on: Apr 10th, 2009, 12:26pm » |
Quote Modify
|
that's true. we could take 365.24 days and divide by 12, which is 30.43 days. this could be assumed as the "month". however, 5 weeks multiplied by 7 days is 35 days, so there wouldn't be the full week following the wine sampling, which means the wines tasted in the latter part of the "month" can not take effect within the 5 week period. to make up for this more wines could be tasted throughout the day. later i'll try and figure the math
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hard: Criminal Cupbearers
« Reply #88 on: Apr 10th, 2009, 2:03pm » |
Quote Modify
|
Well, I'm fully confident you can work out how often you should give a prisoner a drink if death sets in an exact number of hours or minutes after ingestion (and you'd really only need one prisoner. Every ten minutes for a week works out to 1008; and who cares if the prisoner doesn't get to sleep.) But can you figure out a scheme where you give the ten prisoners a selection of drinks all at one time, and then simply wait 5 weeks to get results?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|