There are 1000 bottles of wine and you know that there is exactly one of them that is poisonous, and will kill the drinker in 7 days. (To be precise, it will take randomly from 7 days to 7 days 23 hr 59 min 59 sec.) Now you have 10 testers who are willing to risk their lives and test-drink those wines. What is the smallest number of days you need to figure out which bottle contains the poisonous wine? In addition, under this strategy, what is the maximum and minimum number of deaths? The extension to this problem is, how will your strategy change if you only have 9 testers?

You can do it in precisely 7 days.

You will notice that there are 10 testers, and 1000 can be represented in 10 bits. Firstly, you number the bottles from 1-1000. Each tester represents a bit position in the binary respesentation of the numbers, and each tester drinks wine from those wine bottles which have their respective bit set.

Then, 7 days later, some subset of the testers die, and you know their bit positions were 1 while the others were 0, and you have the answer.

For instance, if testers 34 and 7 died, the poisonous bottle would be 1001100b = 76.

Posted by vertigo on 2005-02-26 18:57:41