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?

My solution is a combination of two styles:

Style 1 - each tester tests a distinct batch of size S, with no overlap between the testers, and with one batch untested.  6 days later there will be either 0 or 1 deaths, and we'll know which batch the poison is in.  We can narrow down the problem like this over and over. 

Style 2 - by overlapping the testers, M testers can actually test 2M -1 bottles per day, with each tester testing M bottles per day.  For example, with 3 testers:
Tester1 tests: A, B, C, D
Tester2 tests: B, C, D, E
Tester3 tests: C, D, E, F
Tester4 tests: D, E, F, G
On the next day, Tester1 would start at H.  When a subset of the testers dies, based on which testers are in that set, you can tell which bottle was poisonous.  From our example, if 6 days later Tester1 and Tester2 died (and the others didn't), B had the poison.  Also, we can leave 1 bottle from our total batch untested, and if nobody dies, that bottle contained the poison.  So with this style N bottles can be tested in Ceiling{(N-1)/(2M-1)} days, with 6 days of waiting after.

The reason we mix the two styles is because Style 1 cuts down the totle number of bottles really quickly, but there comes a point when the 6 days of waiting in between each round aren't worth it.

So, for 10 testers, I found this:

Day1: using Style 1 with S = 91, leaving 90 untested.  6 days later we have either 10 testers and 90 bottles left to test, or 9 testers and 91 bottles left to test.  The worst case scenario, using Style 2, is 6 testing days + 6 waiting days for a total of 19 days overall.

Note that with Style 1 there is a balance between how many testers survive and how many bottles remain, so that there is benefit to having the untested batch be larger than the batch that each tester tests.  However, in our particular case I couldn't get the worst case down to under 19 days.

The same idea with 9 testers leads to 20 days minimum.  I have a feeling I'm missing something, but I think this is a good start.

Posted by iamkobe on 2005-02-26 19:17:30