Borrowed from folj.com.
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 over a thousand paid caterers to help with the testing and just under 24 hours to determine which single bottle is poisoned.
You have a handful of prisoners about to be executed, and it would mar your celebration to have anyone else killed.
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?
Solution directly from folj.com
Answer: 10 prisoners must sample the wine. Bonus points if you worked out a way to ensure than no more than 8 prisoners die.
Number all bottles using binary digits. Assign each prisoner to one of the binary flags. Prisoners must take a sip from each bottle where their binary flag is set.
| <><><><><> | Bottle 1 | <><><><><>Bottle 2 | <><><><><>Bottle 3 | <><><><><>Bottle 4 | <><><><><>Bottle 5 | <><><><><>Bottle 6 | <><><><><>Bottle 7 | <><><><><>Bottle 8 | <><><><><>
| Prisoner A | <><><><><><><><><><> | X | <><><><><><><><><><> | X | <><><><><><><><><><> | X | <><><><><><><><><><> | X | <><><><><>
| Prisoner B | <><><><><><><><><><> | <><><><><> | X | <><><><><>X | <><><><><><><><><><> | <><><><><> | X | <><><><><>X | <><><><><>
| Prisoner C | <><><><><><><><><><> | <><><><><> | <><><><><> | <><><><><> | X | <><><><><>X | <><><><><>X | <><><><><>X | <><><><><>
Here is how you would find one poisoned bottle out of eight total bottles of wine.
In the above example, if all prisoners die, bottle 8 is bad. If none die, bottle 1 is bad. If A & B dies, bottle 4 is bad.
With ten people there are 1024 unique combinations so you could test up to 1024 bottles of wine.
Each of the ten prisoners will take a small sip from about 500 bottles. Each sip should take no longer than 30 seconds and should be a very small amount. Small sips not only leave more wine for guests. Small sips also avoid death by alcohol poisoning. As long as each prisoner is administered about a millilitre from each bottle, they will only consume the equivalent of about one bottle of wine each.
Each prisoner will have at least a fifty percent chance of living. There is only one binary combination where all prisoners must sip from the wine. If there are ten prisoners then there are ten more combinations where all but one prisoner must sip from the wine. By avoiding these two types of combinations you can ensure no more than 8 prisoners die.
One viewer felt that this solution was in flagrant contempt of restaurant etiquette. The emperor paid for this wine, so there should be no need to prove to the guests that wine is the same as the label. I am not even sure if ancient wine even came with labels affixed. However, it is true that after leaving the wine open for a day, that this medieval wine will taste more like vinegar than it ever did. C'est la vie.
you need 14 prisoners and only 4 of them will die. Each caterer is given one bottle, which they will serve to a group of 4 prisoners out of the 14. No two caterers can serve the same set of 4 prisoners. Whichever caterer's bottle kills all 4 will be the bottle that's poisoned.
ReplyDelete-wats
I like that. My way requires fewer prisoners, but potentially more that could die.
ReplyDeletewho cares if prisoners die? flan and i came up with a solution that only requires the efforts of 10 prisoners. get the rest doing manual labor.
ReplyDeleteyou need only 10 prisoners.
ReplyDeletenumber the bottles from 0 to 1000, and in binary
representation you need 10 digits to represent the numbers till 1000. so this is why you need 10 prisoners.
the rule is the following:
each prisoner will be assigned number from 1 to 10
each prisoner will drink from the bottle that in its binary representation the prisoner digit is 1.
then the prisoners that will die will show you which number of bottle they all drink from and they is only one, that is common between them, assign 1 to the prisoners digits and that will be the number of the bottle
You only need one prisoner. The prisoner can sample all the bottles of wine...right?
ReplyDeleteYou missed the part where its mentioned that it takes 10-20 hrs for the poison to take effect!
DeleteGive me 10 prisoners and 3 iterations and I'll make sure that at least 7 survive, with a small chance of having all 10 prisoners surviving.
ReplyDeleteFirst trial, divide the wines in 11 batches, 10 of 91 and 1 of 90. have the prisoners taste 1 batch each. none will try the 11th (90 wine) batch.(this is how you maximize your results... no result is also valuable information)
The bad wine is in the batch that kills the prisoner. If noone dies, the bad wine is in the 11th batch (the one noone tasted).
divide the batch containing the bad wine in 10 batches of 9 (if noone died) or 8 batches of 9 and 1 of 10.
Again, have prisoners taste one batch each (again, noone tries the last batch, and if noone died on the first round, 1 prisoner auto survives!).
Again, the poisoned wine is in the batch that kills (or doesn't kill) a prisoner. you are left with either 9 wines (and 8 prisoners) or 10 wines (and 9 or 10 prisoners)
Lastly, have 1 prisoner taste each wine, having a wine that noone tastes, (if you got lucky, 2 prisoners have automatically survived)...
he who dies found the poisoned wine. if noone dies, that's you poisoned wine too!
This method is a good compromise between time invested and people required/killed. Even if the poison takes 10 hours to kill, by the time the party starts, you are up to your final 9 bottles, and 991 bottles of wine is still plenty alcohol for the party, without risking your guest's lives.
72% chance 3 prisoners die
25.28 chance 2 die
2.63% chance 1 dies
.09% chance no casualties (yup, slim chance, but at least there is a chance)
To me i will prefer taking a little numbers of prisoners and bottles.
ReplyDelete@erosan :only we have 20 hrs so we cant test it continuously .....
ReplyDeleteYes, BUT! His first sample narrows it down to a batch of 91 bottles by the time the party starts, guaranteed. Presumably the party will go on for a time and the wine won't be all consumed at the onset. Assuming it takes the maximum (20 hours) between samples for a prisoner to die from poisoning, you enter the party with a minimum of 1000-91 = 909 bottles of wine that are proven good after the 20 hours.
Delete4 more hours (at least, assuming nobody died from wine already thus identifying the bad batch) of testing the remaining batch before the party starts, leaves a minimum of 6 hours and a maximum of 16 hours until the remaining 90-91 bottles are narrowed down to 8-10 possible offenders. This super party can be presumed to last all day, when the final batch of wine is brought out to serve those who stuck around.... roughly 80 bottles. The remaining 10 bottles can be used as a part of the execution process, if they don't die by poison they die by whatever other means was intended. The remaining good bottles can then be served among those who attend the executions, a maximum of 60 hours in, minimum of 30 hours (immediately after the party starts.)
I have another approach to it.. other than the binary solution..
ReplyDeletewhat we can do is
STEP 1: Arrange all these bottles in a 10X10X10 cube.. so that at every co-ordinate of that cube one will have a bottle..
now let us suppose there are Xo,X1,X2... X9..SIMILARLY Y0,Y1...,Y9. SIMILARLY for Z i.e. 30 glasses(can also us a single glass for X0,Y0,Z0 so 28 glasses)
STEP 2: Now what we do is we add all small drops of wine from the bottles at the respective coordinates in the plane thus formed to a glass i.e. we add all wine to the glass in the plane X=1 to the glass X1.. and so on...
STEP 3: Now we arrange these 28 glasses of wine in a rectangle of 7X4... and place a rat at each of X0,X1..X7 and Y0,Y1..Y4(can consider rat X0,Y0 to be same so we get 10 rats).
FINAL STEP: Let us consider that the bottle with co-ordinates X=1,Y=2,Z=3 is poisoned so the glass X1,Y2,Z3 will also be poisoned so now two rats would drink wine from one bottleso 6 rats would die and we sould be able to spot the 3 glasses which are poisoned from the 7X4 rectangular co-ordinate system..as we find that X1,Y2,Z3 are poisoned we can easily find the bottle which is poisoned from our 3-d stack of 10X10X10.
Please reply if u find any flaws in this solution. Thank you!
Flaw #1 - A 10x10x10 cube only holds 600 bottles...
Deletehow come?? 10 cube is thousand right????
DeleteHere is the complete explanation for the answer http://www.faqinterview.in/interviewquestion/puzzle/1000-wine-bottles-1-bottle-having-poison-in-it
ReplyDeletewhy complicate it so much.. you will need 34 prisoners.. but only one dies!
ReplyDeleteyou have under 24 hours. and minimum 10-20 hours for the poison to take effect. so basically you have only 2 rounds to determine which bottle is poisoned. make groups of (1000 bottles/30slaves) bottles. which comes to 33.33. I know that is an odd figure but I am the ruler, so I can make one group test for 30 bottles while the other for 32! so considering that, so the slave who dies at the end of 10 hours, the poisoned bottle is in his group. now since one is dead, 29 prisoners from the last round plus 5 more u can add since u have over 1000 slaves at ur disposal and 34 bottles and 14 hours. have each prisoner taste each bottle. the one who dies at the end, that bottle is poisoned. so, my final answer is 35 prisoners need but only 2 die.
ReplyDeleteVery nice and lovely work :) I like your good ideas, thanks for the inspiration!
ReplyDeletewordpress
ufa88kh.blogspot
youtube
កីឡាបាល់ទាត់ អនឡាញ
land slot auto เล่นเกมสล็อตได้ทุกค่าย ครบทุกเกมไปกับ ทุกค่ายเกมสุดสนุก แบบแปลกใหม่ ไม่มีซ้ำใครกันแน่ เล่นได้ไม่น่าเบื่อ PG ไม่เหมือนกันด้วยการเป็นบริการเกมสล็อตออนไลน์
ReplyDeleteJoker123 ที่พวกเราพรีเซ็นท์ เกมออนไลน์ได้เงินจริง ที่ตื่นเต้นเยอะแยะ กราฟฟิกงามไม่มีอันตราย ให้คุณเพลินและก็ศึกษาและทำการค้นพบระยะเวลาที่ความสนุกที่ pg และก็คุ้มค่ามาก
ReplyDeleteimba96 ออนไลน์ ยังมีการบริการลูกค้าอย่างมืออาชีพ ที่พร้อมให้คำปรึกษาและแก้ไขปัญหาต่างๆ pg slot ให้กับผู้เล่นโดยตลอด ไม่ว่าจะเป็นการสอบถามด้านเทคนิค การเลือกเล่นเกมส์
ReplyDelete