On Mar 17, 2013, at 9:44 PM, Michael Kleber <michael.kleber@gmail.com> wrote:
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.
Thanks for these new 8% solutions! I noticed that your first code, for equal wine bottle partitions, has a larger symmetry group than the one in which you searched. It's of order 16 and has a nice relationship to Pauli matrices. Here's the correspondence: {2, 5, 3, 1, 4, 9, 6, 8, 10, 7} = I Px {10, 9, 3, 7, 6, 1, 2, 8, 4, 5} = I Py {7, 10, 3, 6, 9, 2, 5, 8, 1, 4} = I Pz The permutations refer to the bits of your code, I = sqrt(-1), and Px, Py, Pz are the standard Pauli matrices. These generate the quaternion group of order 8 and act on the code exactly as all the 4/50 codes I found with the wax-and-wane algorithm (which assumed no symmetry). But your new code's symmetry also includes the generator {2, 5, 8, 1, 4, 7, 10, 3, 6, 9} = I This exchanges 3 and 8, unlike the others which keep these bits fixed; the corresponding 2x2 matrix is sqrt(-1) times the identity. You may have found the most symmetric 8% solution! It was a great idea to adapt the mixed-integer programming so it acts on symmetry orbits; n>7 is clearly out of reach otherwise. But you must feel frustrated that the best so far just ties the equal-partition result! You might try the slightly smaller quaternion group instead of the group of 10 cyclic shifts. -Veit
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