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?
#!/usr/bin/python def circle_shift(n, s): a = n * (2 ** s) return (a % 1024) + a/1024 for i in xrange(1024): for j in xrange(1024): nums = [circle_shift(i, k) for k in xrange(10)] + [circle_shift(j, k) for k in xrange(10)] ors = [a | b for a in nums for b in nums if a < b] if len(ors) == len(set(ors)): print bin(i), bin(j)
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
The n=6 code reminds me that I had a question about the product construction of unique union codes: how does it work exactly? For example, how do you put two copies of the n=3 code (000, 001, 010, 100) together to get an n=6 code? -Thomas C
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