This question was submitted by a reader (I'm not sure if I have his permission to show his name).
Does trying to find the ONE bottle of wine that is poisoned out of many others sound familiar?
I am sending you this e-mail to propose you a QotD. I like you blog and I'd like to see how other people manage this one:
There was a king that for some reason had to throw a big party in 3 weeks and for some reason had 1000 bottles of a very good wine, many of which he wanted to use at the party. He knew that one and only one bottle of the one thousand was poisoned and that the poison killed whoever drank from that bottle in APPROXIMATELY 2 weeks. He had 10 people that were willing to risk their lives so that he could find the poisoned bottle. How did he find it?
Assumptions: if a pawn drinks from the poisoned wine today, he could die in 11 or 17 days, or whatever; a drop of wine out of the many that a pawn can drink certainly kills him if it is poisoned; there is a solution.
If you have any questions, please ask, so you can solve it, don't read the solution. So, good luck; I am looking forward to hearing from you.
Begin by numbering the wines 0 to 999. The convert those numbers to binary, so that they range from 0 to 1111100111--10 binary digits. Label the bottles with these binary representations. Then have the first tester sample all bottles with a 1 in the first digit. If he dies, we'll know the poisoned bottle has a 1 in the last digit of its binary index; otherwise, we'll know the poisoned bottle has a 0 in the last digit. Have the second tester sample all bottles with a 1 in the second digit, the third sample all bottles with a 1 in the third digit, and so forth.
ReplyDeleteJust before the party (at which time, presumably, any testers that are going to die have done so; we've given them an extra week), simply look at which testers are dead. Since each completely determines a digit, the ten of them together completely determine the bottle's number. For instance, if they all live, the poison is in bottle 0000000000; if only the third tester dies, the poison is in bottle 0000000100; and so forth. Throw out the poisoned bottle and any accompanying bodies, and enjoy the feast.
Actually, we could have even accommodated an extra 24 bottles with this method (indexing from 0 to 1023, or 00000000000 to 1111111111), so if the king wants to buy a couple dozen more and mix them in with the rest, tell him to knock himself out.
As always, you guys can't be stumped!
ReplyDeleteAlthough this wasn't my question, so I can't say for sure, that answer looks good to me.