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
The n=6 and n=8 patterns can be re-arranged (per permuting rows and columns) into n=6: 000 000 001 001 010 010 100 100 001 110 010 101 100 011 111 000 n=8: 0000 0000 0001 0001 0010 0010 0100 0100 1000 1000 0001 1010 0010 1100 0100 1001 1010 0001 1100 0010 1001 0100 0000 0111 0111 0000 I've been playing with these because I really want to find an unique union code for n=15 of size >1000 (i.e., show that you can uniquely identify the two poisoned wine bottles with only 15 bottles). -Thomas C
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