Found by a slightly randomized greedy search algorithm after about a million tries, the following unique union code for n = 10 of size 20: (Not containing {} and it cannot be added.) {2}, {3, 10}, {4, 6}, {7, 9}, {1, 3, 5}, {1, 4, 9}, {1, 6, 10}, {2, 4, 7}, {2, 5, 9}, {3, 4, 8}, {5, 6, 8}, {1, 2, 3, 7}, {1, 2, 5, 6}, {1, 6, 7, 8}, {1, 8, 9, 10}, {2, 3, 8, 9}, {2, 6, 8, 10}, {3, 4, 5, 10}, {3, 6, 7, 9}, {5, 6, 7, 10} Converted to binary strings: 0000000010 0000010101 0000101000 0000110011 0001000111 0001001010 0010001100 0010110000 0011100001 0100001001 0100010010 0101000000 0101100100 0110000110 1000000100 1000011100 1000100001 1001110000 1010100010 1110000001 Perhaps with more patience and a faster computer one could find larger unique codes for n = 10 by this method. Distribution of sizes found of maximal unique union codes for n = 10 in 1102809 tries by randomized greedy search: 3, 17597 4, 5792 5, 132469 6, 18133 7, 14628 8, 126673 9, 286749 10, 35964 11, 38246 12, 120017 13, 165637 14, 86386 15, 33268 16, 16729 17, 4137 18, 364 19, 19 20, 1 21, 0 On Wed, Nov 21, 2012 at 9:14 AM, Veit Elser <ve10@cornell.edu> wrote:
On 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
Wow! I was looking for exactly this object. How did you succeed?
I noticed a pattern among the optimal codes for n=4,6,8 :
0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 0 0 0 1 1
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 1
If we think of the columns as codewords (of codes of length 4, 6, 8), these are all constant weight, constant distance: (w,d)=(1,2), (3,4), (4,6). I have no idea why the columns should have this symmetrical structure, it is just an observation. My next step was going to be to look for a constant weight, constant distance code of size 10, with codewords of length 21. But you beat me to it! Your code (transpose) has constant weight 7 and constant distance 10.
BTW, for the poisoned bottle-pair application one of the codewords of the "unique union" code must be the zero codeword. But all the optimal codes so far have this property.
-Veit
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun