I frittered away some time (both mine and a computer's) on a useless attempt to solve the rats problem via linear programming: a solution is described by a choice of 2^10 integer values b_0, b_1,..., b_1023, where b_k is the number of bottles drunk by exactly rats all-the-1s-in-the-binary-expansion-of-k. The number of bottles you throw away isn't actually the max of a bunch of linear functions of the b's, though -- not until you decide which b's are 0 versus nonzero. At that point you can invoke linear programming, but picking which b's are nonzero is the hard part. I did just look back at this message of Veit's from a few days ago, though, and my "cyclic capped union code" code can answer one small open question: On Sun, Nov 25, 2012 at 2:26 PM, Veit Elser <ve10@cornell.edu> wrote:
A union code with parameters (n,k) is a set of codewords comprising subsets of n symbols with the property that any pairwise union of (not necessarily distinct) codewords can arise from pairwise unions of at most k codewords.
Let M(n,k) be the maximum size code with parameters (n,k). For the poisoned bottle-pair application, in the limit of many bottles, we are interested in maximizing M(n,k)/k.
Michael found a k=4 code for n=10 of size 46, with 46/4=11.5 beating Thomas' k=2 code of size 21 (21/2=10.5). I was curious when k>2 starts outperforming k=2 and wrote an exhaustive search program that gave the following results: [...] n=7: k 2 3 4 5 6 M(7,k) 10 14* 20* 24* 29* M(7,k)/k 5 4.67* 5* 4.8* 4.83*
The numbers marked * are lower bounds. As you can see, the results up to n=7 are inconclusive: only ties for k>2 have been found. The best hope looks like n=7, k=4.
Hey, my trivial Mathematica program can do that: for n=7, there is a 21-element cyclic capped union code with k=4, consisting of the circular shifts of {0000001, 0001011, 0001101}. No reason to think that forcing cyclic symmetry is optimal, but in this case it's good enough. So now we have at least one case where the more-general capped union code out-performs the unique union code. --Michael -- Forewarned is worth an octopus in the bush.