On Tue, Nov 20, 2012 at 10:35 PM, Thomas Colthurst <thomaswc@gmail.com>wrote:
I found an "unique union" code for n=10 with size 21, just by taking 0000000000 along with all of the circular shifts of 0000001011 and 0001100101.
Since 1000 / 21 = 47.6 ..., this gives a rats solution that loses at most 2*48 = 96 bottles.
-Thomas C
Nice approach! I have a variant that gets down to throwing away 88 bottles. It looks Thomas's size-21 is the best you can do with circularly-symmetric unique union codes. His is one of 16 examples. We can generalize the unique-union idea, though, to codes in which a given pairwise union of codewords can arise from pairwise unions involving at most k different words. The unique-union case is where k=2, meaning that if we partition wine bottles into bins labeled by codewords, we can feed them to rats and throw away at most k=2 bins. If we relax this to k=4, there are circularly-symmetric codes containing 46 as many as words. I found ten examples, of which one is: 0000000000 0000000101 and its circular shifts (ten total) 0000011011 likewise 0001000111 likewise 0001001011 likewise 0000100001 and its circular shifts (five total, as this word has a rotational symmetry itself) Note that the k=4 condition is *not* the same as "there are at most two ways to form each union". This code, for example, has one type of codeword, A=0001000111, which is a union of two others, B=0000000101 and C=0001000010. So if the dead rats are codeword A, then there are a bunch of possibilities for where the poisoned bottles are: A+A, A+B, A+C, A+0, or B+C. But in any case, you throw away the wine in bins A, B, C, and 0. Since there are 46 codewords, you divide wine up into 46 bins with at most ceiling(1000/46) = 22 wine bottles in each, and throw away at most 4 bins, so 88 bottles. (I didn't see a way to arrange the 34 21-bottle bins vs the 12 22-bottle bins to pull this down to 87, but perhaps I missed it.) --Michael