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). I don't think most of your message was about this problem -- you gave a way to get 800 non-poisoned bottles, but certainly it is possible to do much better than that. --Michael On Thu, Nov 15, 2012 at 7:50 PM, Warren Smith <warren.wds@gmail.com> wrote:
From: Michael Kleber <michael.kleber@gmail.com> You have 1000 bottles of wine, which you need for a party that starts in an hour. Two of the bottles are poisoned. You have ten rats, and you can cause each rat to drink from any subset of the bottles, which will cause it to die if the bottle is poisoned. But the poison takes most of an hour to act, so you only get one round of giving wine to rats, after which you must throw away any bottle which you do not know is safe. What do you do? I'd be happy to hear either worst-case or average-case results. Obviously if only one bottle were poisoned, you'd number the bottles and assign one rat to each bit of the binary representation, and the dead rats would spell out the binary of the unique poisoned bottle number. But two poisoned bottles seems to make this much more subtle.
--Interesting puzzle.
Let W be the number of wine bottles, P the number poisoned, 1<=P<=W, and R the number of rats. The task is to identify the poisoned wine bottles with a single round of feeding each rat a wine-mixture from a selected bottle-subset. Say rat j gets fed subset Sj.
Consider this WxR boolean matrix M: M_ij = 1 if wine bottle i is in set Sj. Otherwise M_ij=0.
The essential property demanded (for a worst-case result allowing us to identify the P poisoned bottles) is that for any P-element subset of the rows of the matrix, its logical-OR (as an R-bit binary word) is DISTINCT from that arising from any other P-element subset. (This logical OR's locations for its 1-bits give the names of the dead rats.)
So evidently for a solution to exist we need that binomial(W, P) <= 2^R.
It was proposed that W=1000, P=2. Hence the left hand side is 499500=1000*999/2. Hence a solution cannot exist unless there are at least 19 rats, R>=19.
Since Kleber had R=10, we conclude there is no solution guaranteed to identify the two poisoned bottles.
We can however adopt the weaker goal of trying to identify some subset of bottles we can guarantee are safe. In that case, just partition the bottles into R equal-size subsets each with W/R bottles. Then P rats die whereupon we've identified (R-P)*W/R safe wine bottles. With R=10, P=2, W=1000, we identify 800 safe ones this way.
Returning to the original problem of identifying the poisoned bottles, Kleber's binary method shows the inequality I gave is tight (up to integer roundoff) if P=1. But what if P>=2?
I will now attempt to sketch an argument that my trivial inequality is not too far off being tight, for any FIXED P.
To prove this, consider selecting the matrix M at random, each bit chosen by an i.i.d. coin toss, where the coin used is biased with a particular well-chosen constant bias. Specifically, I choose the bias in such a way that the expected number of 1-bits in the R-vector got by ORing P rows of the matrix, comes out to be R/2.
I claim this argument will show that R = C * lg( binomial(W,P) ) rats suffice, for some positive constant C. To prove this (i.e. to supply the details of the proof, which I have not provided since I am lazy), you need to argue that with positive probability, all those P-row-ORs will indeed be distinct. This can be done by arguing the expected number of conflicting P-row-subset pairs is <1. Then since probability>0, that proves some set of such coin tosses must exist, which have this property, hence a suitable experimental-design exists. QED.
Hence, with P=2, since 2 is fixed, there is a solution with R=O(logW) rats and somebody less lazy than I could even work out a good bound on the constant C (1<C<5 sounds safe).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.