I just got out from my Math and Logic class with my friend. During the lecture, a well-known math/logic puzzle was presented:
The King has $1000$ wines, $1$ of which is poisoned. He needs to identify the poisoned wine as soon as possible, and with the least resources, so he hires the protagonist, a Mathematician. The king offers you his expendable servants to help you test which wine is poisoned.
The poisoned wine is very potent, so much that one molecule of the wine will cause anyone who drinks it to die. However, it is slow-acting. The nature of the slow-acting poison means that there is only time to test one "drink" per servant. (A drink may be a mixture of any number of wines) (Assume that the King needs to know within an hour, and that any poison in the drink takes an hour to show any symptoms)
What is the minimum amount of servants you would need to identify the poisoned wine?
With enough time and reasoning, one can eventually see that this requires at most ten ($10$) servants (in fact, you could test 24 more wines on top of that 1000 before requiring an eleventh servant). The proof/procedure is left to the reader.
My friend and I, however, was not content with resting upon this answer. My friend added the question:
What would be different if there were $2$ wines that were poisoned out of the 1000? What is the new minimum then?
We eventually generalized the problem to this:
Given $N$ bottles of wine ($N \gt 1$) and, of those, $k$ poisoned wines ($0 \lt k \lt N$), what is the optimum method to identify the all of the poisoned wines, and how many servants are required ($s(N,k)$)?
After some mathsing, my friend and I managed to find some (possibly unhelpful) lower and upper bounds:
$ log_2 {N \choose k} \le s(N,k) \le N-1 $
This is because $log_2 {N \choose k}$ is the minimum number of servants to uniquely identify the $N \choose k$ possible configurations of $k$ poisoned wines in $N$ total wines.
Can anyone help us find an optimum strategy? Besides the trivial one requiring $N-1$ servants. How about a possible approach to start?
Would this problem be any different if you were only required to find a strategy that would for sure find a wine that is not poisoned, instead of identifying all poisoned wines? (other than the slightly trivial solution of $k$ servants)