You are the ruler of a medieval empire and you are about to have a celebration tomorrow. The celebration is the most important party you have ever hosted. You've got 1000 bottles of wine you were planning to open for the celebration, but you find out that one of them is poisoned.
The poison exhibits no symptoms until death. Death occurs within ten to twenty hours after consuming even the minutest amount of poison.
You have thousands of prisoners at your disposal and just under 24 hours to determine which single bottle is poisoned.
What is the smallest number of prisoners you must have to drink from the bottles to be absolutely sure to find the poisoned bottle within 24 hours?
Posts
8 comments:
999.....???
actually first i need to know wat is the exact time in which a person dies after consuming poison... 10 to 20 is very arbit... if its is less than 12 hrs then minimum is 63 prisoners.. else its 999...
The information given in the problem is sufficient. Whether a prisoner dies in 10 or 20 hours depends on his body. Figures '10' and '20' have been chosen with care and even with this arbitrariness the answer is exact.
And 999 is not the answer. Had it been so, this puzzle wouldn't have found place here in my blog.
tu studd hai yaar...
So far I can see how you do it with 10, but it is clearly redundant - number of bottles is less than 1024, and the strongest testers will be ready for reuse in 20 hours. Working on it...
After some thinking I believe the "10 to 20 hours" thing is simply designed to throw you off a bit, but generally tells you not to count on taster reuse (taste some now, then, if alive in less than 12 hours - another one).
So, the solution is binary; demonstrating by example seems to be easier than explaining it - to be short I showed how four tasters find poisoned one among 16 bottles. In table below rows correspond to bottle numbers (1st, 2nd, etc.; 0-based), columns - to taster numbers:
b1 0 0 0 0
b2 0 0 0 1
b3 0 0 1 0
b4 0 0 1 1
b5 0 1 0 0
...
b8 1 1 1 1
Taster 1 (rightmost column) tastes every other bottle; taster 2 (2nd column from right) tastes every other two bottles (skip two, taste two, skip two...); etc.
Total of 10 tasters is needed to taste 1024 bottles (2^10), which is enough for a 1000. Then, a unique combination (a bottle number in binary!) of dead tasters gives you the answer.
Works?
@tomilchik: you're right, "10 to 20 hrs" is just to confuse you. In fact, if there are chances of reaction time being more than 12 hrs, people cannot be reused.
You can think of it this way. how many different groups (combinations) can you make using 10 people? Take the 1st man. There are two possibilities: whether he is in the group or he is not. Similarly, for the 2nd man there are two possibilities: whether he is in or not: and so on for the rest eight members. So number of total possibilities (ie total different types of groups) are 2^10 i.e. 1024.
Since 10 members make 1024 groups, 1024 bottles can be tested.
(This question was a child's play. You should try the 12-coin problem, my favourite.)
Post a Comment