Problem
An assassin has infiltrated your wine cellar where you keep 1000 pristine bottles of vintage. The assassin poisons one of the bottles before being startled and fleeing the cellar. You are left unsure which bottle of wine has been poisoned. However, you know the poison is powerful, and that even a diluted drop would be deadly. Moreover, you know the poison takes effect within 24 hours of imbibing. Once it takes effect, death is immediate.
Fortunately, you have a poison testing device. Less fortunately, you only have ten non-reusable testing cups for the device. So, for example, you might use a cup to test one bottle of wine for poison, but afterwards the cup cannot be used to test another. As with human ingestion, the poison can be detected when it takes effect, sometime within 24 hours of the test, and once it takes effect, it may be detected immediately.
Perhaps even less fortunately, you have intended to serve the 1000 bottles during a lavish party in exactly 24 hours. Clearly you cannot do so now. Always the optimist, you are sure there is a way to isolate the poisoned bottle using only the ten testing cups, allowing the remaining 999 bottles for the party.
Question
How do you find the poison?
Solution
Let's begin with some intuitive labels. Name the testing cups A, B, C…J. Name the bottles 1-1000.
Let's try on a few putative solutions, observing where they fail and why, and also where they succeed and why.
First Pass - Clearly, we might test ten bottles of wine, one for each cup. That is, we might take some small portion of wine from, say, bottle 1 and place it in testing cup A. Similarly, we might take some small portion of wine from bottle 2 and place it in testing cup B, etc. At some time within 24 hours we will then know if one of the tested bottles has been poisoned.
However, since the testing cups are non-reusable, this approach would leave us with 990 bottles untested. A more subtle approach is warranted.
Second Pass - We might instead divide the 1000 bottles into ten allotments of 100 bottles each, e.g. 1-100 would form an allotment, as would 101-200, and so on. We might then take, say, a small portion of wine from each of the 100 bottles in allotment 1-100, which we place in testing cup A. Similarly, a small portion of wine from each of 101-200 would be placed in testing cup B, and so on. At some time within 24 hours we will then know if one of the allotments contains the poisoned bottle of wine.
This pass is a significant improvement over the first. To see why, assume the poison is in wine bottle 425. Then testing cup A-D and F-J will not indicate poison has been detected, while testing cup E will. Of course, that leaves us with poison somewhere among 100 bottles. We assumed the poison was in bottle 425, but we would've achieved the same result had we assumed the poison was in any of the 401-500 bottles. In the interest of having a stellar party rather than merely an amazing party, let's press on.
Third Pass - Keep the second pass attempt, but add that A also tests bottles with names ending in "1", B tests those ending in "2", C in "3" and so on until we reach J which tests, in addition to 901-1000, those bottles with names ending in "0".
The result seems to significantly narrow down the poison. For example, say the poison is in bottle 467. Then E will indicate poison since E tests 401-500. So will G, since G tests not only 601-700, but also every bottle ending in "7". Unfortunately, both E and G overlap in many other places, e.g. 407, 417, etc. This pass offers little advantage over the last. We must continue.
Final Pass - Each preceding pass was an attempt to uniquely identify each bottle by some distribution of samples over testing devices. You're an optimist, but the preceding failures might lead you to think the glass is half empty, i.e. there is no such arrangement. Note, however, there are 1000 bottles and 10 testing cups. Each testing cup either will or will not test a given bottle of wine. But then there are 2^10=1024 ways we might uniquely distribute the bottles along the cups. Since there are only 1000 bottles, we should be able to uniquely identify each bottle. We need only find the right arrangement.
And these observations reveal the lines along which we may find our solution. There are two 'values' with respect to each bottle of wine, that a testing cup might take. For the purposes of book-keeping, if a testing cup tests a bottle, say that cup is evaluated as 'True' at that bottle, or 'T'. Otherwise, say that cup is evaluated as 'False' at that bottle, or 'F'. If, for example, testing cup A tests bottle 456, then A will be evaluated as 'T' at that bottle. If not, then 'F'. I chose these values to better illustrate our unique identification using a feature of a commonly taught algorithm for evaluating sentences in propositional logic: truth tables. Appealing to truth table distributions of 'T' and 'F' will provide the needed distribution of 1000 bottles of wine (rows) over 10 testing cups (columns).
But working with a truth table with over 1000 rows is cumbersome. Let's illustrate instead with a smaller example and then generalize. Specifically, let's examine our solution with only 3 testing cups, resulting in 2^3=8 rows in the truth table, each of which will correspond to a bottle of wine:
A B C
1 T T T
2 T T F
3 T F T
4 T F F
5 F T T
6 F T F
7 F F T
8 F F F
Each row is distinct. Then according to the table every testing cup will test bottle 1, A and B will test 2, A and C will test 3, and only A will test 4. A will not, however, test any of the remaining bottles. Rather, B and C will test 5, B will test 6, C will test 7, and no cup will test 8. Then if no cup indicates poison has been detected, it is in bottle 8. If only C, then 7; only B, then 6; only A then 4. If both B and C, then 5; A and C, then 3; A and B, then 2. If all testing cups indicate poison has been detected, then the poison is in bottle 1.
It is easy to see how our illustration of 3 testing cups and 8 bottles generalizes to the case of 10 cups and 1000 bottles. In that case, as stated, we are able to uniquely identify 2^10=1024 bottles, and hence, 1000 bottles with some to spare.
So, retain your optimism. It looks like you'll have a party to remember (or not!) after all. Though, keep an eye on the guest list; there's an assassin out there looking for you.