From: Michael Kleber <michael.kleber@gmail.com> I didn't quite follow this, Warren. What are you saying is almost tight? Just to be clear, the puzzle I'm passing along is: Come up with a way of assigning a subset of wine bottles to each rat, such that by observing which rats die you can produce a set of wine bottles known to be safe, where the set of safe bottles is as large as possible (either expected-value or worst-case size).
--Actually, it was not at all clear from your problem statement what you wanted. I was interested in the problem of identifying the exact set of poisoned bottles, using as few rats as possible, in 1 round. I argued with P poisoned bottles, P fixed, out of W total bottles, R rats with R=O(logW), would suffice, and this is best possible up to the constant hidden in the O. ---- But if P is not fixed, but instead is allowed to grow with W, for example P=W^(1/3), then I do not know a good answer. I can produce a good answer if we allow only a strong probability (not certainty) of success. Divide the W bottles into P*logW almost equal random disjoint subsets. With good probability, each such set contains at most a constant number of poisoned bottles. Now use my previous scheme that works well when P is bounded by a constant, within each subset. This has sketched a proof of existence of a scheme in which R=O(P*logW) rats are used, and which will, with probability>2/3, succeed in identifying the exact set of P poisoned bottles, and this works for any 0<=P<=W with P known ahead of time. However, with some probability<1/3, it will fail. The failure probability can be made to be <(1/3)^k by doing this k times in parallel (then k times as many rats needed), which I presume/guess means that O(P*(logW)^2) rats suffice to get certainty. (That is unproven, but you might be able to prove it using more careful and expanded version of this argument.) If that conjecture is true then we are tight up to an annoying log factor. ----- Mike Speciner pointed out that dividing the W bottles into R+P-1 almost-equal subsets allows us to use R rats in 1 round to identify at least (R-1)*floor( W/(R+P-1) ) safe bottles if we know at most P are poisoned.