As a matter of curiosity a rather poor (but cute) lower bound can be obtained for the unique union code size by restricting oneself to two element subsets of the given n-set. One gets a classical graph theory problem, namely: If a(n) is the maximum number of edges in an n-vertex graph of girth 5. Then a(n) <= M(n). If G is a (simple) graph on n vertices with girth 5 then G has no 3-cycles or 4-cycles. This implies that the set of edges is a unique union code on n symbols. [Here an edge is a 2 element set of vertices.] Thus a(n) <= M(n). In particular, the value a(10) = 15 is given by the Petersen graph<http://en.wikipedia.org/wiki/Petersen_graph>. Values of a(n) for n to 30 are given in http://oeis.org/A006856. The extremal graphs can be found in the paper Extremal graphs without three-cycles or four-cycles<http://www.math.udel.edu/%7Elazebnik/papers/ex34a_v2.pdf>by Garnick, et al. --Edwin On Mon, Nov 19, 2012 at 8:42 PM, Veit Elser <ve10@cornell.edu> wrote:
With the help of OEIS I discovered some history for this problem. First I came up with a better term for the name of the relevant codes.
A "unique union" code on n symbols is a set of subsets of these n symbols with the property that all pairwise unions of the subsets is unique.
Here is an example of a unique union code of size 4 for n=3:
0 0 0 1 0 0 0 1 0 0 0 1
The 1's indicate the inclusion of the symbol in the subset. There is no larger unique union code for n=3, so M(3)=4.
With only n=3 rats to test for poison, we would partition the bottles into equal (or as near to equal as possible) sets and deliver samples to the 3 rats according to the unique union code. If the two poisoned bottles are in different sets of the partition we will know their identities from the union of their codewords. On the other hand, if both poisoned bottles are in the same partition, then we will see just one codeword. But if this codeword is not the zero codeword, then we must consider the possibility that we are seeing the union of the non-zero codeword and the zero codeword. In either case, to be safe we must eliminate 2 partitions of the bottles. The fraction we can eliminate is therefore 2/M(n).
J.P. Grossman's post describes a product construction of unique union codes with sizes
M'(3k) = 4 2^(k-1) M'(3k+1) = 5 2^(k-1) M'(3k+2) = 6 2^(k-1)
For n<8 these are optimal. Today I wrote a short program to find M(8)=13, an increase by 1 over the product code. Fortunately I now had enough of the M(n) sequence
1, 2, 3, 4, 5, 6, 8, 10, 13
to get a manageable output from OEIS. The rat-puzzle numbers turn out to have been studied by Erdos and others, see A054961. The sequence has been computed only to M(8)=13, but since already the value for n=8 is larger than the product code value, we can be sure that M'(10)=20 is also not optimal and so a larger fraction of the bottles can be saved.
-Veit
optimal n=8 code:
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1
On Nov 17, 2012, at 12:16 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
Thanks, J.P. This is indeed the best approach I know of.
Well, except that if you're thinking worst-case, you've overlooked the rounding problems that come from the fact that 1000 is not a multiple of 4*4*5=80. You can certainly arrange the bottles into 4*4*5 sets of 12-or-13 each and discard at worst 104. Someone at work argued that you could do 102 if you're clever, though I didn't quite follow how. But I don't know of a way to get down to actually only discarding 100 bottles.
On the lower-bound side of the argument, there are 1000-choose-2 possible pairs of poisoned bottles, and you can at best separate them into 1024 classes based on rat mortality -- so each rat-outcome forces you to discard the bottles from at least 488 pairs, which means a bare minimum of 32 bottles (since discarding 32 bottles tosses 32-choose-2 = 496 pairs). That's obviously wildly too few, though: you'd need to partition the bottles into lots of size 31-or-32 and always have the two poisoned bottles in the same lot.
Can anyone tighten these bounds?
--Michael
On Sat, Nov 17, 2012 at 12:02 PM, J.P. Grossman <jpg@alum.mit.edu> wrote:
Another way to think of the P=1 case is that each additional rat allows us to reduce the number of dangerous (possibly poisoned) bottles by 1/2. When P=2 a single rat doesn't allow us to eliminate any dangerous bottles, but Mike observed that with k rats we can reduce the number by 2/(k+1).
With 4 rats we can directly reduce the number by 2/5, or we can divide the rats into 2+2 and reduce the number by 2/3 * 2/3 > 2/5. Better to use all four rats at once.
With 5 rats we can directly reduce the number by 2/6 = 1/3, or we can divide the rats into 2+3 and reduce the number by 2/3 * 2/4 = 2/3. It's a wash.
With > 5 rats it's always better to subdivide, and we find that the optimal division or rats within this approach depends on the number of rats mod 3:
- With 3k rats, use k * 3 to reduce the number of dangerous bottles by 1/2^k - With 3k+1 rats, use (k-1) * 3 + 4 to reduce the number by 1/2^(k-1) * 2/5 = 1/2^(k-2) * 1/5 - With 3k+2 rats, use k * 3 + 2 to reduce the number by 1/2^k * 2/3 = 1/2^(k-1) * 1/3
So in particular with 10 rats, we use the division 3 + 3 + 4 to reduce the number of dangerous bottles by 1/10, meaning that with 1000 bottles we can save 900 of them.
To make this approach concrete, write the bottle numbers with a mixed-radix representation using radix 4 for all digits but the last, and radix 3, 4 or 5 for the last digit depending on whether the number of rats is 2, 0 or 1 (respectively) mod 3. Each group of 2-4 rats in the partition gets assigned to one digit, and within that group a bottle is given to rat m if, for that bottle, the selected digit is m.
Note that there's no claim that this approach is optimal.
J.P. On Fri, Nov 16, 2012 at 9:00 AM, Mike Speciner <ms@alum.mit.edu> wrote:
You can trivially do better than 800 by dividing the 1000 into 11 (almost) equal subsets, and assign a rat to each but one of them. You end up guaranteeing 9/11 of the 1000 bottles safe. Presumably you can do still better on average with an algorithm that potentially has different numbers of rats dying.
--ms
On 2012-11-15 19:50, Warren Smith 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<; http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
______________________________**_________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/**cgi-bin/mailman/listinfo/math-**fun<; http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>
_______________________________________________ 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. _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun