Timeline for Puzzle on deleting k bits from binary vectors of length 3k
Current License: CC BY-SA 3.0
28 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 3, 2013 at 18:24 | comment | added | Simd | I have reformulated the problem as a "hitting set" problem and then coded that as a Mixed Integer Linear Program (MILP). I am using some software called Gurobi to solve the MILP. Unfortunately a disadvantage of my method is that I don't have any sense either for how rare it is or if one could do better. My encoding is also naive making it probably very wasteful. | |
| Oct 3, 2013 at 6:06 | comment | added | Aaron Meyerowitz | Wow! How did you get it? Do you have a sense how rare it is? Do you think 16 is possible? | |
| Oct 2, 2013 at 17:13 | comment | added | Simd | I managed to get a $17$ solution for $(15,5)$. They are 0000001111,0000111111,0001101100,0011100011,0011111000,0100111010,0110001001,0111001110,1000010000,1001100111,1100011100,1101000110,1110000011,1111100000,1111111000 plus the all 0s and all 1s. | |
| Sep 27, 2013 at 8:34 | comment | added | Thomas | Actually, maybe I should try to prove my claim about H(n,1), or at least prove it is an upper bound. | |
| Sep 27, 2013 at 2:55 | comment | added | Thomas | Oh, I didn't see your edits stating that H(8,2)=H(10,3)=10. I will work on extending the walsh sequences for H(14,5) and H(16,6). | |
| Sep 27, 2013 at 1:22 | comment | added | Thomas | I am going to work on H(2a+4,a). I already know 2 of the values, H(6,1) and H(12,4) because of your program, I am going to work on the intermediate cases H(8,2) and H(10,3). I also think that, since for H(12,4), it was close to being 8 (only 32 problem cases out of 4096), I believe that 8 may be the limit value of H(2a+4,a). | |
| Sep 27, 2013 at 1:19 | comment | added | Thomas | I also think I know a closed form for H(n,1). If n is odd, H(n,1)=(n+1 (n+1)/2) ((a b) is a choose b), and if n is even, H(n,1)=2H(n-1,1). This is completely conjectural of course, but it lines up for the first few values. | |
| Sep 27, 2013 at 1:19 | comment | added | Thomas | I believe that 6 is optimal for (2a+3,a) for all a, using the construction described above, but I haven't been able to prove it. | |
| Sep 26, 2013 at 21:22 | comment | added | Simd | @Thomas The sequence for $H(n,1)$ is $2,2,4,6,12,20,40, \leq70 , \leq 141$. This has two different possibilities at oeis.org/… . Do we already know a closed form for $H(n,1)$? | |
| Sep 26, 2013 at 15:07 | comment | added | Simd | @Thomas $12$ is indeed optimal for $(6,1)$ and $20$ is optimal for $(7,1)$. I feel embarrassed releasing my cobbled together code but I am happy to run any tests or describe it in more detail. $6$ is optimal for $(7,2)$. | |
| Sep 26, 2013 at 14:52 | comment | added | Thomas | I conjecture that H(a+2,b+1)<=H(a,b) if a>b. This works for the first few values. | |
| Sep 26, 2013 at 14:43 | comment | added | Thomas | Also, I have tried to use the walsh sequences in the (6,1) problem, by removing the first two digits and the last one, but that did not work, there were 8 left over sequences. | |
| Sep 26, 2013 at 14:39 | comment | added | Thomas | Wow, cool. I am working on the problem for strings of length 6 and being able to remove one bit (6,1). I am having a bit of trouble getting a covering set of size less than the trivial 12 gotten by appending the last digit to the 6 optimal strings for the (5,1) case. I am beginning to think that there isn't one, can you check? Is this program open source so I can download it and use it to solve the problem? Using paper and pen only gets so far. | |
| Sep 26, 2013 at 14:23 | comment | added | Simd | @Thomas All options. In fact I formulated the problem as an integer programming problem and just solved it using scip.zib.de. | |
| Sep 26, 2013 at 14:17 | comment | added | Thomas | Did you search every option, or only the symmetrical ones? | |
| Sep 26, 2013 at 8:47 | comment | added | Simd | I have now proved by computer search that $10$ is optimal for $n=12$. Unfortunately it does not seem feasible to scale this up to $n=15$ without some more work. | |
| Sep 26, 2013 at 6:33 | comment | added | Aaron Meyerowitz | If I had more time I would make this shorter. There are actually 64 12-strings not covered by any of the Walsh strings. These 32 and their complements: 010010001101,010010001110,010010010101,010010010110,010010101001,010010101010,010010110001,010010110010,010011010001,010011010010,010011101101,010011101110,010101010001,010101010010,010101101101,010101101110,011010010001,011010010010,011010101101,011010101110,011100010001,011100010010,011100101101,011100101110,011101001101,011101001110,011101010101,011101010110,011101101001,011101101010,011101110001,01110111001 | |
| Sep 26, 2013 at 3:50 | comment | added | Thomas | It would be nice if someone proved some symmetry properties of the covering sets. For example, that the complement of every string in the covering set is also in the string, but I guess that's too much to hope for. Also, do the 32 problematic elements have some form of symmetry other than the complement symmetry? | |
| Sep 26, 2013 at 2:59 | comment | added | Thomas | My idea is that you have to have some other string of the form (0^a)1^(8-a) to cover 000000111111. I am curious, what are the 32 problematic cases? | |
| Sep 25, 2013 at 16:57 | comment | added | Aaron Meyerowitz | I tried taking those four along with 00000111 and 11111000 but I don't thik you can enlarge that to a covering set of size 8. The eight Walsh strings cover all but 32 out the 4096 length 12 strings so I think a size eight could well be possible. | |
| Sep 25, 2013 at 8:45 | comment | added | Thomas | I have checked a few relatively simple cases, and it seems that using 00011111 and 11100000 would be better than 00001111 and 11110000. I know that it lacks the symmetry of the original solution, but we should try it anyway. | |
| Sep 25, 2013 at 4:57 | comment | added | Aaron Meyerowitz | And it is the unique minimal cover with all these properties. | |
| Sep 25, 2013 at 4:45 | comment | added | Aaron Meyerowitz | A better choice for the "extra" two vectors for $n=12$ is $10010110,01101001$. Then one has the four vectors constant on each half and six more vectors each equal or complementary to its reverse (as before) AND with equally many $0$'s and $1$'s in each half. | |
| Sep 25, 2013 at 2:59 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 26 characters in body
|
| Sep 25, 2013 at 1:24 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 1681 characters in body
|
| Sep 25, 2013 at 1:06 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 1681 characters in body
|
| Sep 24, 2013 at 23:21 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 196 characters in body
|
| Sep 24, 2013 at 21:50 | history | answered | Aaron Meyerowitz | CC BY-SA 3.0 |