Rats return! For the original problem (2 of 1000 poisoned, 10 rats) I'm still at discarding 80 bottles, but now I have two additional 80-bottle solutions to report. First, a brute-force search for capped union codes bore fruit. I looked for codes with symmetry dihedral of order 4 -- that is, if a word w is in the code, so are reverse(w) and cyclic_shift(w,5) -- and there are indeed some 50/4 codes of that form. Here's one, for posterity, representing the length-10 bit strings in decimal as usual: {3, 4, 9, 14, 18, 21, 24, 33, 39, 48, 66, 72, 77, 96, 106, 116, 128, 138, 145, 184, 210, 225, 258, 264, 278, 288, 300, 305, 323, 324, 344, 393, 418, 448, 513, 528, 540, 548, 553, 562, 576, 582, 593, 643, 672, 712, 768, 773, 778, 912} Second and more interestingly is Veit's mixed integer programming representation, which I've been playing with a bit. As Veit reported earlier, solvers like Gurobi can rapidly dispatch sufficiently small cases, so for starters I ran through the various numbers of rats restricted to codewords of weight up to 2 (= at most 2 rats drink from any bottle). Veit already reported the 12/49 fraction for n=6 rats (which turns out to be optimal even without the weight constraint) and 4/21 for n=7. For n=8, 9, 10 the best fractions are 2/13, 12/97, and 4/39 respectively. Interestingly, all solutions have the property that codewords with the same weight always get the same fraction of wine bottles. I'm trying to run the solver on n=7 and max_weight=3, the case where Veit reported on Mike Quist's 2/11 solution. That solution is the incumbent (best-so-far) but there's a ways to go for showing optimality. But as always, I'm looking at the 10-rat case, where even weight=3 seems way out of reach. So I decided to try the same trick as before, restricting to solutions with a reasonably large symmetry group. And it paid off! Restricting to codes with n=10, max_weight=4 and 10-fold cyclic symmetry, Gurobi was able to find the optimal solution, which again involved throwing away 80 (aka 8/100 of the) bottles: * Any pair of rats that is a cyclic shift of 0000000011, 0000000101, 0000001001, or 0000010001 -- that is, all pairs except (i, i+5) -- drinks from 1/100 of the bottles. * Any four-tuples of rats that is a cyclic shift of 0001000111 or 0000101101 drink from 3/100 of the bottles. This makes me happy, as it's the first 80-bottle solution sufficiently symmetric that I can carry it around in my head. --Michael PS: I wish we had any movement at all on a lower bound. The gap between 80 and the information-theoretic lower bound of 32 is vast. On Sun, Jan 27, 2013 at 2:41 PM, Veit Elser <ve10@cornell.edu> wrote:
I have no improvement to report on the 10-rat case, but here's a surprise development we owe to my former student Mike Quist.
Shortly after I explained the poisoned bottle problem to him he pointed out that one shouldn't make the assumption that a uniform partition of the bottles is always going to be optimal. To prove his point, Mike constructed, for 7 rats, a 4-unique code of size 19. When the bottles are partitioned evenly this would give a discard fraction of 4/19, inferior to what one gets with Michael's size 21 4-unique code reported Nov. 28. However, by unequally partitioning the bottles you can get a discard fraction of 2/11 with Mike's code!
Rather than show you Mike's code I'll give you the simplest case of this phenomenon which requires 6 rats. Using a mixed-integer program I checked that for less than 6 rats the equal partition is optimal. The same linear programming method found the following code for 6 rats:
Construct the 2+2+2 product code from the 2-rat code {00,01,10}. This has 27 codewords. Now remove all the codewords of weight 3; that gives a code having 1 word of weight 0, 6 words of weight 1, and 12 words of weight 2, for a total of 19 codewords. Partition the wine bottles so 7/49 are assigned to the zero word, 1/49 to each of the weight 1 words, and 3/49 to each of the weight 2 words. You can check that for any union of codeword pairs you never have to discard more than the fraction 12/49 -- a modest improvement over 1/4. For example, there are some unions where 6 codewords are implicated (it is a 6-unique code), but in all these cases the bottle partition has the form (1+1+1+3+3+3)/49=12/49.
Are unequal bottle partitions going to be the rule for optimal codes? So far we only know it is true for 6 and 7 rats. When I relax the equal partition condition and optimize the good codes we found in the past with respect to this I get no improvement (the optimal partition is the uniform one). So it seems we need a new approach to get the truly optimal codes.
I can send the *.lp file for 7 or more rats to anyone interested with access to a big computer. At this point we only have optimal solutions up to 6 rats:
n 1 2 3 4 5 6 f 1 2/3 1/2 2/5 1/3 12/49
The gurobi solver finds the last entry in 2 sec when I restrict the codewords to weight 2 and 15 minutes when I allow weight 3. For 7 rats it finds the 4/21 solution, that is optimal for weight < 3 , in 15 sec. But finding Quist's 2/11 solution, which includes weight 3, is not going to happen on my laptop!
-Veit
On Jan 6, 2013, at 4:46 PM, Veit Elser <ve10@cornell.edu> wrote:
Wow -- that was fast!
wax & wane has found several more 50/4's, all with the same (quaternion unit) symmetry group. I'll try a deeper search to see if something else turns up.
-Veit
_______________________________________________ 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.