Author |
Topic: Hard: Criminal Cupbearers (Read 22595 times) |
|
Three Hands
Uberpuzzler
Gender: 
Posts: 715
|
 |
Re: Hard: Criminal Cupbearers
« Reply #50 on: Jun 11th, 2004, 6:37am » |
 Quote  Modify
|
OK - I didn't really grasp what you were saying carpao. Time for me to spend a few hours with a headache, probably, while I try and catch up with the rest of you 
|
|
 IP Logged |
|
|
|
Mattis
Newbie
Gender:
Posts: 5
|
|
Re: Hard: Criminal Cupbearers
« Reply #51 on: Dec 19th, 2004, 5:41pm » |
Quote Modify
|
Well, I'd say there are plenty of solutions to the problem in this thread. But I think there is one intresting twist you could add to the problem. Suppose there is no way of knowing if a prisoner dies from the poisoned whine or from, say, age, torture or the bad food in the prison.
As the cautious ruler you are, you want to compensate for the risk that one prisoner who didn't drink a poisoned whine dies a "natural" death. We can assume that there is very little risk that more than one prisoner who didn't drink the poison dies.
With that twist, how would you proceed as the evil but cautious king you are? How few prisoners do you need to use to find the poisoned bottle in one month?
I don't have a solution better than 20 prisoners but it should be doable with maybe 12-13 with some sort of error-correcting code or something. Or isn't it? Remember that most error-correcting codes assume that a 1 can become a 0 or a 0 can become a 1 through error in transmission. In this case we only have the latter case (a prisoner who didn't dring poison dies anyway is possible, but not that a prisoner who did drink the poison survives). That could be useful maybe.
One easy thing you could do is to add an 11:th bit to the numbering of the bottles (in the ordinary "mark each bottle with a binary number"-solution), a checksum-bit set so that there always is an even number of '1':s on each number.
Then one prisoner is the checksum-prisoner, set to die if only an odd number of the original prisoners dies (oh how happy he must feel).
Now if an odd number of prisoners die anyway, you know that one must have died of natural causes, but you still don't know which bottle of whine is the poisoned one.
Still you use only 11 prisoners and I claim that only 8 dies from poison in the worst case
But does anyone have a good solution that requires less than 20 prisoners and also points out which bottle is the poisoned one?
|
|
IP Logged |
|
|
|
SwaMpFoX
Newbie
Gender:
Posts: 1
|
|
Re: Hard: Criminal Cupbearers
« Reply #52 on: Jan 30th, 2005, 8:42pm » |
Quote Modify
|
I dont think anyone needs to die why not look for the open bottle. Back in the day wine bottles came with a cork in it then dipped into wax to seal it. 10 prisoners could inspect 100 bottles each the one bottle that has the seal tampered with throw out.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hard: Criminal Cupbearers
« Reply #53 on: Jan 31st, 2005, 12:57am » |
Quote Modify
|
You're assuming the bottle was tampered with after it was closed and sealed.
Besides, even if that were the case, it might have been resealed by a professional and not look suspicious.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Lance
Guest
|
|
Re: Hard: Criminal Cupbearers
« Reply #54 on: May 16th, 2005, 8:05pm » |
Quote Modify
 Remove
|
Take 10 prisoners and divide the 1000 bottles so that each prisoner has 100 bottles. Record which prisoner gets 1-99, 100-199, 200-299, so on. Since that poison is still extremly potent when diluted, mix the 100 bottles together and make each prisoner drink from their batch. By the forth week the King has one dead prisoner and 900 bottles worth of wine to drink by the fifth week.
|
|
IP Logged |
|
|
|
ThyGod
Newbie
:)
Gender:
Posts: 4
|
|
Re: Hard: Criminal Cupbearers
« Reply #55 on: Jun 16th, 2005, 1:57pm » |
Quote Modify
|
i think i have it. To simplify, say that the poison takes 4 hours and the king wants to have 999 bottles of wine at 5. u have prizoners 1, 2, 3, 4, 5, 6, 7, 8, 9, and 0, which will be the tenth prisoner. If you assign each bottle to a unique group of prisoners, such as 1st bottle to prisoner 1, 2 to 2 and so on. So, when the four hours are up, you look at which group of prisoners died, and select their bottle as the poisoned one. Now, since u cant repeat numbers or the order in which they apper, i.e. u cant have 123 and 321 or 231, since the same group of prisoners would die, you have to devise a more complex method of counting. But it is relatively easy. for 11, use 12, eventually u might have to use 5 digit numbers for 3 digit ones, but there will be a unique combo for each bottle, which is the solution. 
|
|
IP Logged |
|
|
|
Obi2Kenobi
Newbie
Posts: 1
|
|
Re: Hard: Criminal Cupbearers
« Reply #56 on: Jun 29th, 2005, 9:33pm » |
Quote Modify
|
Well, you see, he's an evil king. It doesn't explicitly state that he has to use those prisoners to discover which bottle is poisoned, only that he is going to make some prisoners drink the wine. So any number will work; if he runs out of prisoners, he's a king, he can just raise an army against the neighboring queen, capture her, and make her and her nobles drink the rest of the wine if the king isn't smart enough to figure out to do it without wasting tons of his precious prisoners (although he still could use a few thousand prisoners to ease the public concern of crime by being able to honestly state that prison crowding is at an all time low).
Wow, that was a very convoluted/run-on sentence.
|
|
IP Logged |
|
|
|
raj
Newbie
Posts: 2
|
|
Re: Hard: Criminal Cupbearers
« Reply #57 on: Nov 6th, 2005, 4:51pm » |
Quote Modify
|
I approached this problem with the assumption that the king can only run a single day of trials. i.e. no testing on day 2 3 4 etc. He then has to wait 4 weeks for the result. I also assumed that it is possible to subset the bottles into groups and mix 1 drop from each of the bottles in such a subset without tainting occuring.
I divided the bottles into dimensions.
1 dimension = 1000bottles requires 1000 tasters
2 dimensions = 100X100bottles requires 200 tasters
3 dimensions = 10^3bottles requires 30 tasters
etc thereby isolating the poisoned bottle.
I reason that the number of subjects (y) and number of dimensions (x) can be graphed as y = x*(x root 1000). The optimum number of subjects is thus 19, where the bottles are divided up into 6 dimensions (x=6). Any help varifying this would be much appreciated.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Hard: Criminal Cupbearers
« Reply #58 on: Nov 7th, 2005, 1:01am » |
Quote Modify
|
on Nov 6th, 2005, 4:51pm, raj wrote:
I divided the bottles into dimensions.
1 dimension = 1000bottles requires 1000 tasters
2 dimensions = 100X100bottles requires 200 tasters
3 dimensions = 10^3bottles requires 30 tasters
|
|
You probably mean
2 dimensions 1024 ~= 32X32 bottles, requires 64 tasters
Anyway, if you know there is a poisonned bottle, you can save one tester per dimension. Just leave one group untested. If nobody dies, the poison is in the untested group.
|
|
IP Logged |
|
|
|
raj
Newbie
Posts: 2
|
|
Re: Hard: Criminal Cupbearers
« Reply #59 on: Nov 8th, 2005, 12:51am » |
Quote Modify
|
32X32 Whoops! 2 dimensional post completion explanation glitch. Back to flatland for me. Thanks Grimbal. Your solution goes the extra mile...
|
|
IP Logged |
|
|
|
drilly2000
Newbie
Posts: 1
|
 |
Re: Hard: Criminal Cupbearers
« Reply #60 on: Jan 26th, 2006, 8:00am » |
Quote Modify
|
Maybe i'm looking at this wrong but would it not be easier to divide the 1000 bottles into ten groups of 100. One group for each prisoner,have each prisoner sip from each of his 100 bottles. when one dies you now have 9 prisoners alive and only 100 possible bottles then follow the halving method until the offensive bottle is found. May take a while but you'd kill less of the servants. ( 3 less i think)
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hard: Criminal Cupbearers
« Reply #61 on: Jan 26th, 2006, 9:07am » |
Quote Modify
|
I think there was a time limit on when you had to find the offensive bottle.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TheRappingShoe
Newbie
Posts: 4
|
|
Re: Hard: Criminal Cupbearers
« Reply #62 on: Apr 25th, 2006, 7:44pm » |
Quote Modify
|
Right,... here you go: This assumes the poison takes exactly a month. It involves 10 prisoners and takes three days over the one month period.
The answer is worked out by feeding the prisoners a variety of wines over a three day period. This will cause a three day sequence of deaths beginning exactly one month later.
First number all the bottles from 001 -> 999. Bottle 1000 is recorded as 000 just to keep things in a 3 digit system.
Next, draw up a three day schedule of drinking for prisoners 1-9!
In this sequence the * sign represents all numbers from 1-9, but does not include zero.
Code:
Prisoner 1: 1** (day 1)
*1* (day 2)
**1 (day 3)
Prisoner 2: 3** (day 1)
*3* (day 2)
**3 (day 3)
etc...
Prisoner 9: 9** (day 1)
*9* (day 2)
**9 (day 3)
|
|
So ,for example, on day one Prisoner 1 drinks from all the bottles with their first digit as 1. On day two he drinks from all with the 2nd digit as 1. And day three all with the 3rd digit as one.
Prisoner 10 gets wine too, but he's special:
Code:
Prisoner 10:
xyy (day 1) [x is any number from 1-9, y is a different number from 1-9]
*0* (day 2) [all bottles where 0 is the 2nd digit]
**0 & *00 (day 3) [where 0 is the third digit, and where it is both digits 2 and 3] |
|
A month to the day later
-------------------------------
By recording the sequence of deaths over three days you can use a process of elimination to work out which bottle the poison is in. In the majority of instances we only need to look at the deaths of the first nine prisoners. As long of one of these dies every day then we can identify the poisoned bottle.
For example,
Day One: Prisoner ONE dies
Day Two Prisoner TWO dies
Day Three Prisoner THREE dies
Then you know the poison is in bottle 123 
Also, should none of the nine die then we know the poison is in the one bottle that none of them drank from-
Day One: NO-ONE Dies
Day Two: NO-ONE Dies
Day Three: NO-ONE Dies
Then you know the poison is in bottle 000 (aka 1000)
Why do you need prisoner 10?
--------------------------------------
There are eight possible death sequences for the nine prisoners over three days. The first four allow us to identify the poisoned bottle with 100% certainty.
D = a death occurs, A = no death occurs
But in the final four sequences we are left with two or more suspect bottles:
This is where we look to prisoner 10. By cross referencing the day of his death with the original death sequence this lets us narrow the poisoned bottle down to one.
And that's it! Here's a couple of examples of how to use the system...
If the poison was in bottle 747, then the following would happen:
Day 1 : Prisoner 7 dies
Day 2 : Prisoner 4 dies
Day 3 : No-one dies
This fits a DDA sequence, meaning the poisoned bottle is one of 744 (xyy), 740 (xy0) or 747 (xyx). We look to prisoner ten and note that he is still alive and kicking. So the poison must be in the one he hasnt drunk from, which is number 747.
Alternatively, if we had a death sequence of
Day 1 – Prisoner 5 dies
Day 2 – No-one Dies
Day 3 - Prisoner 3 Dies
This is a DAD sequence, so we look and see that Prisoner 10 died on day two. This means that the poison was in a bottle fitting the x0y pattern, which tells us that the poison was in bottle 503.
Simple 
|
| « Last Edit: Apr 26th, 2006, 11:13am by TheRappingShoe » |
IP Logged |
|
|
|
TheRappingShoe
Newbie
Posts: 4
|
|
Re: Hard: Criminal Cupbearers
« Reply #63 on: Apr 26th, 2006, 12:46pm » |
Quote Modify
|
By the way, I know it has been suggested to use a binary numbering system, (binary numbers on bottles, and then lining up prisoners in a row).
I dont think this would work. I not really very familiar with binary, but any such numbering system, so please correct me if I'm wrong:
All numbers have to be represented by ten digits. The binary code for ONE, for example, is '1'. Presumably shown by having prisoner one lying down dead. But the other 9 prisoners would still be there: If they are alive then they would appear as 0's, and if they are dead they appear as 1's. You cant just send them away and pretend they dont count.
So you'd actually be seeing 0111111111 , or 1000000000. What I'm saying is that if you use binary then you can only use numbers that take up ten digits.
Are there a thousand of these?
Anyway, I think my solution (posted above and also at http://www.rhodriwilliams.com/CrimCups.html) is better, and only kills three at most people over a three day period
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hard: Criminal Cupbearers
« Reply #64 on: Apr 26th, 2006, 2:19pm » |
Quote Modify
|
on Apr 26th, 2006, 12:46pm, TheRappingShoe wrote:| Are there a thousand of these? |
|
1024 to be exact.
And the advantage of the binary method is it doesn't matter whether the poison work in exactly a month, or somewhere between 1 and 4 weeks (randomly for each individual). As long as death occurs within 4 weeks, you'll have identified the poisoned bottle.
Of course, all ten prisoners may die, which might be considered a disadvantage.
|
| « Last Edit: Apr 26th, 2006, 2:35pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TheRappingShoe
Newbie
Posts: 4
|
|
Re: Hard: Criminal Cupbearers
« Reply #65 on: Apr 26th, 2006, 5:02pm » |
Quote Modify
|
Yes, I've been discussing this with my computer programmer mate who has been explaining binary to me. Nice and slowly
I still think my method deserves credit for originality  I cant explain these things very well though - all I've ever written for the past 6 years is politics essays! I've not written about logic since I was 15!
Anyway, in terms of likelihood of deaths which is better? The binary method MIGHT cause 10 deaths, but how many on average would it cause?
My method causes a maximum of three deaths (and a 1000/1 shot of no deaths), but in the majority of instances 3 people will end up dying.
Does the binary method, or any other method, undercut this?
I'm sure you could reduce the death average by spreading the testing over seven days.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hard: Criminal Cupbearers
« Reply #66 on: Apr 27th, 2006, 12:39am » |
Quote Modify
|
I think binary would cause 5 deaths on average. Well, slightly less since there are 1000 and not 1024 bottles (so if you start counting at 0, e.g. bottle 1023 which would cause 10 deaths doesn't exist)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2873
|
|
Re: Hard: Criminal Cupbearers
« Reply #67 on: Apr 27th, 2006, 3:56am » |
Quote Modify
|
Binary can be improved on slightly by skipping certain numbers - for instance 511 would kill 9 prisoners, while 1001 only kills 7, and so on...
I'm not convinced by TheRappingShoe's analysis:
If the poison is in bottle 220, for example, following his charts gives:
day 1: prisoner 2 dies
day 3: prisoner 10 dies
conclusion: bottle 200 is poisoned...
It looks like a simple fix is possible though - if prisoner 10 drinks all xyy and x00 (x and y are different and non-0 throughout) on day 1, x0x and x0y on day 2 and xx0 and xy0 on day 3, then the only change is for DAA, when the patterns for prisoner 10 dying on day 1,2,3, or not at all are: x00, x0x, xx0, and xxx respectively...
|
|
IP Logged |
|
|
|
TheRappingShoe
Newbie
Posts: 4
|
|
Re: Hard: Criminal Cupbearers
« Reply #68 on: Apr 27th, 2006, 9:58am » |
Quote Modify
|
Yes I you're quite right. Prisoner 10's schedule needs changing to that. 
|
|
IP Logged |
|
|
|
Whiskey Tango Foxtrot
Uberpuzzler
Sorry Goose, it's time to buzz a tower.
Gender:
Posts: 1672
|
|
Re: Hard: Criminal Cupbearers
« Reply #69 on: Apr 29th, 2006, 11:29am » |
Quote Modify
|
I still think Alexh's original proposition of creating a series of rows and columns was the most rational and easiest to perform, although it would waste a decent amount of criminals. This is a similar idea.
Create a 10 x 10 square of wine jars. Assign a prisoner to drink from each jar in one row. Tell the other 9 to do the same for the other 9 rows. At the same time, assign 9 prisoners to drink from each jar in a column in the same manner that prisoners were assigned to rows. Only nine are needed since the last row can be evaluated by elimination.
Repeat this process for the next nine squares.
So in the end, 190 prisoners are required (10 x 19), but only two criminals die from the poisoning, making it simple to find the poisoned jar.
|
|
IP Logged |
"I do not feel obliged to believe that the same God who has endowed us with sense, reason, and intellect has intended us to forgo their use." - Galileo Galilei
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Hard: Criminal Cupbearers
« Reply #70 on: May 2nd, 2006, 1:02am » |
Quote Modify
|
@WTF:
why don't you extend the method and make a cube of 10x10x10? Assign 9 prisonners to each dimension. You need only 27 of them and max 3 will die.
|
|
IP Logged |
|
|
|
Whiskey Tango Foxtrot
Uberpuzzler
Sorry Goose, it's time to buzz a tower.
Gender:
Posts: 1672
|
|
Re: Hard: Criminal Cupbearers
« Reply #71 on: May 2nd, 2006, 6:14am » |
Quote Modify
|
Why not indeed. It was to be my next post.
I kind of assumed that someone would take issue with the idea before elaborating on it. But you proved me wrong Mr. Grimbal. My faith in humanity is restored.
|
|
IP Logged |
"I do not feel obliged to believe that the same God who has endowed us with sense, reason, and intellect has intended us to forgo their use." - Galileo Galilei
|
|
|
Mattis
Newbie
Gender:
Posts: 5
|
|
Re: Hard: Criminal Cupbearers
« Reply #72 on: May 4th, 2006, 3:30pm » |
Quote Modify
|
Just an interesting thing: The "cube"-solution and the "binary"-solution are really two sides of the same coin, it's just a matter of dimensions.
ONE dimension: Put all bottles on a LINE, let 999 prisoners drink from 999 of them. The ONE that dies marks the poison, (if no one dies, the last bottle is the poison).
TWO dimensions: Put all bottles in a 32x32 SQUARE. Have 31 prisoners drink from all bottles of one row each, and 31 prisoners drink from all bottles of one column each. The TWO that dies marks the bottle (if no one of the "row-prisoners" dies, it was the last row that contains the poison, and the same goes for the "collumn-prisoners").
THREE dimensions: Put all bottles in a 10x10x10 cube, have 9 drink from all bottles in one cut in the XY-plane each, 9 drink from all bottles in one cut in the YZ-plane each, and 9 drink from all bottles in one cut in the XZ-plane (hmm, hard to explain that one, but I hope you understand.). The (at most) THREE prisoners that dies marks the poison.
Now FOUR dimensions: Put all bottles in a 6x6x6x6 hypercube, have 5+5+5+5 prisoners drink all bottles from one... hyperplane (I guess a hyperplane is a cube) each. A bit hard to imagine maybe, but the (at most) FOUR prisoners that dies marks the poison
Finally TEN dimensions: Put all bottles in a 2x2x2x2x2x2x2x2x2x2 ten dimensional hypercube. What? You can't imagine a ten dimensional hypercube? Its just like a nine dimensional hypercube where you add another dimension, no problem. Now have 1+1+1+1+1+1+1+1+1+1=10 prisoners drink from all the bottles from one of the... 9-dimensional hypercubes I guess... It gets pretty messed up as we have a hard time imagining hypercubes, but let me assure you that the (at most) TEN prisoners that die mark the poisoned bottle.
More dimensions means more prisoners might have to die, but fewer are needed.
You can also watch this the other way around. Giving each bottle a coordinate in the 10-dimensional hypercube with side 2 is the same as assigning them each a 10-digit binary number.
Giving each bottle a coordinate in the 3-dimensional cube with side 10 is the same as as assigning them a 3-digit decimal number.
Giving each bottle a coordinate in the 2-dimensional square with side 32 is the same as assigning them a 2-digit number in base 32.
So if we give each bottle a number with n digits in base B, B-1 prisoners is sufficient to find out one of the digits of the poisoned bottle, and n*(B-1) prisoners is sufficient to find out the number of the poisoned bottle. Also, at most one prisoner per digit will die.
|
|
IP Logged |
|
|
|
grad
Newbie
Gender:
Posts: 14
|
|
Re: Hard: Criminal Cupbearers
« Reply #73 on: May 8th, 2006, 4:54am » |
Quote Modify
|
I am trying to solve CRIMINAL CUPBEARERS but I think that everyone has given his own meaning to the problem in the forum. The problem does is very poorly presented. Many things need to be clear.
1) The poison takes EXACTLY one month to surface OR AT LEAST one month 
2) The king can use up to 1000 prisoners but 10 must die OR the king can use ONLY 10 prisoners ??
3) The time that passes from the time someone takes the poison until he dies is the same for every person OR these times can be different?
Please answer my question and sorry for my poor english.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Hard: Criminal Cupbearers
« Reply #74 on: May 8th, 2006, 5:23am » |
Quote Modify
|
1) The effects surface in under 5 weeks, that is sufficient to find a solution
3) The time it takes for any individual to die from the poison may differ, as long as they are guaranteed to die (from the poison) before the party starts.
2) The method he employs kills at most 10. He might use 1000, but I'd assume he goes for efficiency and uses the least number of prisoners.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print