The bad king's wine cellar
A bad king has 1000 bottles of wine. A neighboring king plots to kill the bad king, and sends a servant to poison the wine. the servant is able to poison only one of them before he is caught. The guards don't know which bottle was poisoned, but they do know that the poison is so potent that even if it was diluted 1,000,000 times, it would still be fatal. Furthermore, the effects of the poison take one month to surface. The king decides he will get some of his prisoners in his vast dungeons to drink the wine. At a minimum how many servants does he need to kill to find out the poisioned bottle of wine and will still be able to drink the rest of the wine in 5 weeks time? As an added note, he does not want to bring in 1000 of his servants as he knows there are a lot lesser number of prisoners he can bring in to begin with.Level: Hard
posted by Karthik Nagaraj at
12:04 PM
31 Comments:
1 servant
Well, I have added an addendum, he does not want to bring in all the 1000 to try out the drink as he knows there is a much lesser number he can bring to the cellar to begin with. So 1 is not the answer.
Well, if you all are thinking that he can bring in 1000 servants and have them all taste the drink and see who dies - then we can work on probability and say that he can bring in only 999 and isolate one bottle (prob = 1/1000) that might be good. So he might not even need to kill any servant. So thats not the question - the question is if he does not want to bring in 1000 servants - lets say for space constraints in the wine cellar, he knows that he can bring in a lot lesser servants and still find out the poisoned bottle. So 1 servant/no servant is the wrong answer.
Well, for those in the field of computers and love mathematics this should be easy - the binary way 2^10 - 1024 !
10 prisoners lined up.
Number the bottles from 0 - 999
Now, divide the bottles into blocks of powers of 2.
Prisoner 9 drinks from 0 - 511.
Prisoner 8 drinks from 0 to 255 and 512 to 999.
Prisoner 7 drinks from 0 to 127, 256 to 383, 512 to 639, 768 to 896
Prisoner 6 drinks from 0 to 63, 128 to 191, 256 to 319, 384 to 447, 512 to 575, etc.,
Prisoner 1 drinks from every second bottle
A month later, line up the Prisoners and treat the dead ones as 1s and the living ones as 0s - you'll have the answer in binary and find the dreaded bottle!
Answer : The king will need 10 Prisoners !
The more servants he kills, the less he feeds/maintains. I say, dont bother optimizing servant inventory . Find the poisoned bottle. Period.
If Cheap labour is a concern, find more scoundrels in the kingdom and jail 'em
Kala, You got the answer - but is there any way of optimizing it further to avoid killing 10 of them? Think...BTW thanks for the update and quick responses
Ajith,
The more servants he kills, yes the more easy it will be for him to find the poisoned bottle BUT yes he will be diminishing his feed. But then if optimization is ruled out, then computers and alogorithms and logic will have no place. So I guess optimization is an important thing because personally I dont care how many servants the king kills - all we need is to find a suitable algorithm that can solve the issue of minimization given the constraints.
What can I say -- my priorities were a solution and the quickest response...for now I'll let the others indulge themselves in this further...
BTW, Is there a way of linking this to the alumni e-mails as a different section that people can subscribe to, if it interests them. These remaining as separate entities may not present people on the alumni the opportunity to see the threads of this blog.
Kala, I agree that getting the solution was important. So, if it is the solution, we are after then I'm afraid '10' is not the answer. :) the question clearly says what is minimum he will "need" to kill to get the poisoned bottle. I believe you can do better than killing 10 people.
About the suggestion: I was just thinking about that you read it aloud for me. I will send out an email to everyone tonight how to subscribe to this as an RSS feed using an RSS reader. Thanks for the suggestion.
the answer is 8 ppl. the algorithm is same as kala but the twist is in 5 weeks. and the effects show up in 30 days... according to kala we would know on the 30th itself...so no of ppl is not optimized...
so split the wine bottles into batches of 0-199 , 200-399 and so on.
2 power 8 = 264 > 200.
so according to kalas logic u know which bottle ( u'll get the no as binary btw 0-199) and based on the day the effect shows up we can find out which batch it was from. therefore we get the exact bottle no. !!
Ok, the story so far - Kala has already said that the king will need 10 prisoners. So we know that there is a solution possible using 10 people and not 1000. So lets work from there.
Balaji says the king needs 8 people. I'm afraid its not 8 Balaji. But I was reading your solution - I did not quite understand it. Lets do a very quick dry run of what Kala has said - Let us assume the bottle # 624 is poisoned. So according to Kala's reply, at the end of the 30th day, on the 31st day - the 10th, 7th, 6th and the 5th prisoners are dead. (start representing the prisoners from right to left as 1, 2, 3, ...) So the Binary equivalent would have gotten you back to 624.
But now, if we split the bottles into bunches of 200, it would be 0-199, 200-399 and so on as you have said. BTW, 2^8 = 256 and not 264. Anyway, so how can we apply the same logic to this? Shouldn't it be a power of 2 to apply the logic of binary? I don't know how you can possibly arrive at a bottle that has a greater binary representation of 2^8 which is the first 256 bottles. Maybe I'm missing something. Sorry.
yeah sorry for tht mistake...but tht should not make a difference.infact it is better to group them into 250 bottles.
what the king does is he makes the 8 prisoners drink 0-249 on day1.(effects will show on day 31)
next day the same 8 drink 250-499.(results will show on day 32)
and so on...
so if the prisoners die on day 32 and the binary number got is x then actual bottle number is 250 + x
if results show up on day 33 then 500 + x
if day 34 then 750 + x.
this way by the end of the day 34 the king will know which bottle was exactly poisoned.
then the king can drink the remaining wine the next day ;)
Yes, I wanted to actually add on to my comment that you should be adding the offset. Thats fine. So after you split into 4 groups of 250 each you apply Kala's methodology to get your offset. Probably it will work - but then you are missing the point here - the question needs to be understood as a solution that requires you to minimize the number of guinea pigs needed (in this case the prisoners) for the king to perform his methodology. Then find the actual number of minimum the king would require to get his results with those guinea pigs. So in that case 8 is not the correct answer. There must be some way we can do better than 8.
I will give you a clue - 10 is the number of guinea pigs needed as already solved by Kala. Now find out if all the 10 need to die. You need to get a deterministic solution as to how many people can afford to actually die for the king's solution to work. In the solution of Kala's, it can be 1/2/3/4/5/6/.../10. It is undeterministic.
You have thought of the right approach - using the fact that the poison shows up after 4 weeks and that each day you begin with a different bottle - so work on that, you might crack it. Good one, keep them flowing. Thats the energy.
Remember - you have already gotten the minimum guinea pigs needed - now minimize the actual # that need to die to determine the poison bottle.
OK, Here I go again...With a fact that we have 5 days of buffer time to test the wines(*thank you for the clue from the previous posts)..
I am making some assumptions to come to a solution:
"a" number of days for poison to take effect i.e., 30th day midnight to the 31st day midnight & we have 5 days of buffer -- so it will end at 35th midnight to 36th midnight (*although it is still day 35); so a=5.
using "b+1" as the method to identify each bottle
"c" prisoner will drink from "b+1" on day "d"; then if the "cth" digit is "d"; till we proceed in the same fashion till the "cth digit" is 0(no testing)
Minimum number of prisoners required : (log f)/ (log b+1)
Now, per the puzzle we do not have a number for the prisoners, we need to bring in an assumption of a fixed number somewhere to derive an equation and an answer :)).
So, if we wish to limit the deaths:
Let's freeze on "e" number of prisoners
We then get the "f" sequences of "e" prisoners for bottles "b+1" with minimum probability on non-zeroes
Eg:
f = 1000 bottles
a = 5 days
Prisoners = 4 (assuming all die)
Therefore --> 6^4=1296(which is greater than 1000)
Basically, what I wrote up earlier for testing over 1 day, the testing is done over a period of 5 days.
:) ..Karthik I hope this is right... in your terms 4 guinea pigs !!
Kala,
Nice to see your pic after a long time :) You look the same though since school time :) Ok coming back to the solution - Wow, you have some terms like f, a, b, ...
I still have to digest your steps with a dry run. But just wanted to update you -
The minimum is not log f /(log b + 1). The maximum number of prisoners the king will ever need is log f to base 2 which you have already cracked it to be 10. That means the king will not require any more than 10. The issue is - does the king really need all the 10? So that would bring the next part of the problem - what is the minimum number of deaths that should occur for the kings solution to work.
As per your solution it is 4 - right? BTW, thats not the # of guinea pigs needed, but it is the # of actual deaths that has to occur amongst the 10 guinea pigs that have been selected
And if that is what you intended to say - then 4 is not the answer :) Sorry again
:((( I'll come back tomorrow... or maybe ..play it smart and wait for the rest to discover the rest of the answer..
Kala,
I appreciate your enthu in this. Thanks for the active participation. Sure, think about it and I'm sure you will come up with the solution. Good luck.
don't tell me its 7.
7 is wrong.Answer is (<5)It is a whole computer code by itself.
since we have 5 buffer days, split 1000 into batches of 200.
we need 8 ppl to conduct the experiment.
Now we can minimize the number of people dying by rplacing those critical numbers ( like 127 (01111111) or 191 (10111111) which contain 7 ones which cause more death) with water bottles. and replacing the bigger numbers with lesser number of ones like (but bigger in magnitude) like 224 which is 11100000 and will cause lesser number of deaths .
this is the main funda of optimization i am using here.
and by continuing it we can cut down all the 7 oners to 3 or 4 oners.
and the optimal number of ppl is ofcourse 5.
but the problem is unclear....
the leaast number of ppl dying would be 1 if there are 200 prisoners.
but as the number of prisoners keep reducing from 200, then the number of people dying will increase. like 199 prisoners may kill 2 ppl.
firstly.....the minimum number of ppl required for the experiment is 8.
for 8 pigs....the number of pigs that will die (by the logic explained above) is 5.
Balaji,
You say that the minimum # needed to begin with is 8 - which I'm not so sure. Lets look at it this way - Using your methodology, can you dry run for bottle # 624, for example.
Also, 5, I'm afraid is not the right answer either for how many people actually need to die to get the king's methodology to work.
Good thinking though!
Karthik,
This is not my last attempt, but atleast looks very convincing :)...I am hoping this is it..like always ;) Here you go...
Make the 10 prisoners test a combination of numbered bottles over a 3 day period. Based on this test period; there MAY be deaths beginning exactly one month later - over a 3 day period.
1. Number all bottles from 001 -> 999. Bottle 1000 is numbered as 000 to retain the 3 digit numbering system.
2. Schedule prisoners 1-9 over a three day period for testing.
For Eg:
Day 1.
Prisoner 1 drinks from all the bottles with their first digit as 1.
Day 2.
Prisoner 1 drinks from all the bottles with the 2nd digit as 1.
Day 3.
Prisoner 1 drinks from all the bottles with the 3rd digit as 1.
For easier representation: x sign represents all numbers from 1-9 and the numbers do not repeat themselves in the combination(Eg: 122,344,etc.,) and does not include zero.
Prisoner 1:
1xx (day 1)
x1x (day 2)
xx1 (day 3)
.
.
.
Prisoner 3:
3xx (day 1)
x3x (day 2)
xx3 (day 3)
and so on till....
.
.
.
Prisoner 9:
9xx (day 1)
x9x (day 2)
xx9 (day 3)
Prisoner 10:
yzz (day 1) where y is any number from 1-9 & z is a different number from 1-9
x0x(day 2) He drinks from all bottles where 0 is the 2nd digit
xx0 & x00 (day 3) He drinks from all bottles with 0 in the third digit, and where 0 is both the 2nd & the 3 digit.
An x cannot be a 0, he wouldn't drink from bottle # 100 on day 2.
A month later ...
Record the sequence of deaths over days 1,2 & 3 & use a process of elimination to identify the dreaded bottle.
Eg:
Day 1: Prisoner 1 dies
Day 2: Prisoner 2 dies
Day 3: Prisoner 3 dies
Therefore, Bottle #123 is the dreaded one !
If 1-9 Prisoners don't die; then the dreaded bottle is among the ones drunk by Prisoner #10.
Day 1: None Die
Day 2: None Die
Day 3: None Die
Therefore, Bottle #000 is the dreaded one ie., Bottle #1000 !
Therefore, you will need 10 prisoners as a minimum to test and a maximum of 3 prisoners to die and a minimum of 1 to die to find the dreaded bottle...
Phew..this wasn't easy :)
this is in response to kala's recent post.
if either of bottles 010 or 011 ( or 121 or 122) are poisoned, will u be able to tell which bottle it exactly was?
Yes.
010
No one dies
Prisoner 1 dies on day 2
Prisoner 10 dies on day 3
011
No one dies
Prisoner 1 dies on day 2
Prisoner 10 dies on day 1
121
Prisoner 1 dies on Day1
Prisoner 2 dies on Day 2
No one dies
122
Prisoner 1 dies on Day 1
Prisoner 2 dies on Day 2
Prisoner 10 dies on Day 1
ah... prisoner 10 is the key. i didn't pay enuf attention to that. sorry
awesome solution. :)
cracked it!! great sol. kala!
but what if u have only 9 prisoners????
thts the reason to optimize the number of prisoners being used too.
Ok, so what's happening fellas? Thought I would observe some comments before I pour in mine. So Kala's solution fits in the best.
Answer: We need 10 people to perform the test and in fact only 3 need to die.
We could isolate one bottle, and keep only 999 for testing, but anyway you get the basic point. What is the main objective of this puzzle?
Given any 'n' number of bottles of wine and if any one was poisoned, then we need to have log n to base 2 number of guinea pigs to perform our experiment on and in fact only num_of_digits(n-1) people actually need to die. So lets say the # of bottle were 10000: # of folks needed would be log 10000 = 13 people and only 4 need to die in the experiment. Now someone might ask, why is it we need 10 people when only 3 can die, why not choose 3? The answer is simple, you don't know which 3 are going to die. I'm my intelligent friends would have already figured this out.
There are a couple of solutions for this problem and strains of both have been discussed in the comments of this puzzle:
[1] Binary method of solving is the most obvious method - you will know how many guinea pigs are needed, but not an optimal solution for the actual # of deaths that should occur. This method is already explained in the very first few comments to this puzzle by Kala. Of course a variation to this by Balaji was also given.
[2] Using the number system - 100s place, 10s place and units place. As already sent in by Kala yesterday. There is a similar idea here to that of Kala's. Split the 1000 bottles into groups of 100. We already know 2^10 > 1000, so we need only 10 people at most to perform this.
On the first day, make the 1st guy taste all the 100 from their corresponding group - 1st prisoner: 1 - 100, 2nd prisoner: 101 - 200, and so on...On the second day split the 100s into groups of 10s. Make every prisoner taste from the corresponding 10s block from every block of 100s. So on day 2 prisoner 1: 1-10, 101-110, 201-210, ...Prisoner 2: 11-20, 201-210, 301-310, ...and so on...On day 3, make every prisoner drink from the first one of every block of 10. So on day 3, prisoner 1: 1, 11, 21, 31, 41, ...prisoner 2: 2, 22, 32, 42, ... and so on...
Now wait for 4 weeks, see who dies, you will get which group of the 100 the poison bottle is in. That gives you the 100s place digit value for the poisoned bottle. Wait for the next day, record who dies, you will know which 10s group the poison bottle is in. You will get the 10s place digit of the poisoned bottle. Wait for the next day and record who dies - you will know the units place digit of the poisoned bottle.
Take an example of 624 and number the prisoners 1 to 10 from left to right - so on the 30th day the prisoner #7 will die indicating the 100s place digit is 6. On the 2nd day, prisoner #3 will die, indicating the 10s digit is 2. On the 3rd day, prisoner #5 will die, indicating that the unit's digit is 4. So we get 624 as the poisoned bottle.
So the king would need 10 prisoners to do the job, only 3 need be killed, and he can enjoy his wine on the 34th day - 4 weeks and 4th day - that's within the 5 weeks time.
The important words that need to be caught here are
[1] ...poison takes 4 weeks to surface...
[2] ...if the king wants to enjoy the wine within 5 weeks time...
[3] ...if diluted 1,000,000 times, it would still be fatal...
Good thinking guys!
Think about this situation. Some prisoner is very intelligent and logical amongst all the others. How would he increase his chances of survival. Lets say the king is very nice to those prisoners at this time after he has selected his favorite 10 for the job? Something more to brood on...
Thank you Vikram, Karthik & Balaji ! However, Karthik never stops at making twists in the already twisted puzzle :)
Ha Ha :) Well, not that I framed this puzzle and also not that I added this little twist, but just a pinch of fun intended in the problem :) Try it out, you will be surprised at the way it turns out to be.
The moot time is up and its already been a week. So here I'm finishing off the last part of the puzzle Very simply I could restate the new problem to be - If a prisoner wants to increase his chances of living and he were told that he could choose his position, then what position would that be?
Well, it really depends on what methodology the king adopts. If he goes by the binary method, then you would want to be in any of the bit positions that show up from 1001 to 1023 (we only have 1000 bottles, so thats good). Thats would be the from bit 6 to bit 10. So you would liketo be prisoner 6 to 10.
Now, if the king chooses to use the decimal split methodology (split into hundreds, tens and units) then there is no point in being anywhere as everyone gets to taste something and the probability of being the dreaded bottle is same for each bottle = 1/1000.
So, either way the prisoner can position himself between 6th and 10th positions and if the king chooses to go otherwise, the prisoner can kiss his lucky chance goodbye and pray for his good luck now!
This puzzle is now offically SOLVED and CLOSED!
Subscribe to Post Comments [Atom]
<< Home