You are an emperor of a huge kingdom and are conducting a party tomorrow in which you have invited very important guests. You had ordered for 2009 bottles of expensive wine for the celebration. However, you come to know that the wine in one of these bottles has been poisoned (but you don't know which one) and that this poison exhibits no symptoms until death. Also, death occurs within ten to fifteen hours after consuming even the minutest amount of this poison. Since the guests are very important you cannot risk serving them poisoned wine. You have slaves at your disposal who could be made to drink the wine in order to detect the poisoned bottle. Since you don't want to disturb the other important tasks the slaves are carrying out, you want to do this with the least number of slaves possible. How would you go about doing this so that you could have a smooth celebration tomorrow and what is the minimum number of slaves you would have to use?
Link to the Solution
25 comments:
since i am the emperor, i will delegate this task to an intelligent minister
also, i dont really care how many slaves die, more slaves can always be bought/made!
There must be 1005 slaves for testing.Per slave will have two bottles n one drop from it.and order them to have that drops at the interval of 10 hrs.Slaves have to keep the bottles with them.Thus,emperor can get to know which bottle contains poison.
Or if emperor wish he can also have one bottle.just for fun.
:)
human rights violation
@thread: It's 6th century AD now and you don't have human rights in place yet :P
@mythalez: how will the minister carry it off? .. Also, read the question again. I have changed it a bit :P
@shona: What if they die after 15 hours?
lolz 2 mythales.
Okay 2 things:
Death will occur between 10th and 15th hour of consuming the wine.
So dividing a day into such windows:
Wine taken at 0 hour will show effect between 9th and 14th hour.
Next drop should be taken at 5 hours amounting to a death between 15th and 20th hour.
Basically, each slave could test 3 wine bottles.
So for 2009 bottles, 2009/3 = 670 slaves should be needed.
i cant see what u changed in the question :P btw, the minister can do thus:
arrrange the bottles in a square: 45x45 approx. 45 slaves drink each row, 45 slaves drink each column
depending on which two die .. u knw! :P
@Vivek: Agreed, but mythalez has already reduced it to 90 slaves!
@mythalez: Good solution. Try to reduce the number of slaves further :P
infact, one row and one column dont need a slave, so 44+44=88 slaves will suffice
@mythalez: Nice! But try to reduce it further :)
can be reduced further with every slave drinking from consecutive rows (and similarly columns), so that 43 slaves only will be required for all rows. therefore 86 in total. example:
slave1 will drink from r0 and r1
next slave from r1 and r2, so until r43, u will need 43 slaves only. r44 - no one drinks :P
if r1+r2 an r2+r3 slaves die, it means r2 is poisoned and similarly in column
u can use the same set of slaves for rows and columns, but in a different order .. so that makes it 43 in total, or perhaps 44 :P
ok, forget last two comments :P
each row neednt need 45 slaves to test. it can again be represented as a square 7x7, thus needing 14 only. overall = 28.
again the row of this smaller square can be represented as a square 3x3, thus needing 6 slaves only per this smallest square. so 12 slaves for the total set of rows (0f 25x45), so 24 for the whole set of bottles
@mythalez: Again for this don't you need more than 24 hours?
How about this:
(thanks for the heads up rama)
2009 = 41 * 7 * 7, so let's arrange the bottles in 3D array.
Total slaves needed for testing this 41+7+7 = 55.
Depending upon the slaves getting killed we can find the poisoned wine. Eg. (10, 3, 5), (34, 6, 2)
Now, as I already deduces, one slave can test 3 times before 24 hours run out. So we don't need 55, we just need 55/3 = 19 slaves.
They can work as (for instance, assigning to rows colums and height)(14*2*2), (13*2*3) and (14*3*2)
Final answer 19.
@Vivek: Good work! But try to reduce it further :P
@Vivke: Infact you could have represented it as ( (2009)^1/3 ) ^ 3. i.e. a 13x13x13 in 3D. And by your logic you would have to use only 13 slaves. Now think about more number of dimensions and about hypercubes and try to reduce it further :P
Hypercubes you say.. and more dimensions?
Then.. I'd chose time.. I would take only one slave.. he tests each bottle .. slave goes back in time at the time of dying since you dint mention anything about instant death within microseconds.
Final answer 1 :P
If I'm the King.. my slaves are more important to me.. they work for me..
I'd rather watch one of the freeloader guests dying :P
Using hints from dilip and vivek, looks like a 7th dimension hypercube is the best fit, number of slaves required would be 3*7/3 = 7, each side of the cube have 3 bottles, 3^7 > 2009. Good puzzle and solution by you guys.
@Ankit: Why not 11th dimension? (2^11 > 2009)
The emperor can solve his problem using the life of only a single slave. First of all the slave should be a girl, she should be beautiful and a virgin ... sorry, thats a different story.
The real answer:
The emperor should give a random bottle to a single slave ( male or female), and then after X hours if the slave dies, it becomes known that all the other bottles are OK. So these are server to the guests.
Other wise( in case the slave does not die), the bottle the slave drank from is OK. Then the emperor serves that single bottle to all his guests. Everyone gets tiny portions but no one dies.
-vishal
doesn't 11th dimension means 11*2/3= 7.33 slaves? which is ofcourse more then 7*3/3=7, so to me 7th looks like the best choice.
@Ankit: As mythalez had pointed out you can leave out one row/column in each dimension (without a slave) .. so it is 11/3 not 11*2/3.
Post a Comment