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