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?
The idea of giving each bottle a 10-bit code does the work. In order to have as few deaths as possible, we should try using codes with not many "1" bits. There are 1024 possible codes, so we should discard the code formed with all 1's, the 10 codes with nine "1"s and one "0", and 9 of the codes with eight "1"s and two "0"s.
If we take the 1024 codes, we get 5120 "1"s; discarding the 20 codes set above, we get 4948 bits, or 4.948 average per bottle.
So: the average number of deaths is 4.948; the minimum, 0; the maximum, 8.
Some statistics
