The standard version of this puzzle is as follows: you have $1000$ bottles of wine, one of which is poisoned. You also have a supply of rats (say). You want to determine which bottle is the poisoned one by feeding the wines to the rats. The poisoned wine takes exactly one hour to work and is undetectable before then. How many rats are necessary to find the poisoned bottle in one hour?


It is not hard to see that the answer is $10$. Way back when math.SE first started, [a generalization](https://math.stackexchange.com/questions/639/logic-problem-identifying-poisoned-wines-out-of-a-sample-minimizing-test-subjec) was considered where more than one bottle of wine is poisoned. The strategy that works for the standard version fails for this version, and I could only find a solution for the case of $2$ poisoned bottles that requires $65$ rats. Asymptotically my solution requires $O(\log^2 N)$ rats to detect $2$ poisoned bottles out of $N$ bottles.


Can anyone do better asymptotically and/or prove that their answer is optimal and/or find a solution that works for more poisoned bottles? The number of poisoned bottles, I guess, should be kept constant while the total number of bottles is allowed to become large for asymptotic estimates. 



Identifying poisoned wines
Each bottle of wine corresponds to the set of rats who tasted it. Let $\mathcal{F}$ be the family of the resulting sets. If bottles corresponding to sets $A$ and $B$ are poisoned then
$A \cup B$ is the set of dead rats. Therefore we can identify the poisoned bottles as long as for all $A,B,C,D \in \mathcal{F}$ such that $A \cup B = C \cup D$ we have $\{ A, B \} = \{ C, D \}$. Families with this property are called *(strongly) union-free* and the maximum possible size $f(n) $ of a union free family $\mathcal{F} \subset 2^{ [n] } $ has been studied in extremal combinatorics. In the question context, $f(n)$ is the maximum number of bottles of wine which can be tested by $n$ rats.


In the paper ["Union-free Hypergraphs and Probability Theory"](http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_frankl_union-free-and-entropy.pdf) Frankl and Furedi show that
$$2^{(n-3)/4} \leq f(n) \leq 2^{(n+1)/2}.$$
The proof of the lower bound is algebraic, constructive, and, I think, very elegant.
In particular, one can find $2$ poisoned bottles out of $1000$ with $43$ rats. 


