Skip to main content
9 of 9
added 122 characters in body
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

NEW VERSION The earliest version of this answer was incorrect, as noted by Rob Pratt and Oleg567. My new code was apparently correct but there was an embarrassing bug in old code used with it. Keep fingers crossed...


Call two solutions equivalent if one is obtained from the other by permuting columns. I made some crude code, not well checked, and found these optimal solutions for vectors of length $n$.

$n=2$: best is 2, with 2 inequivalent solutions, example

10
11

$n=3$: best is 4, with 2 inequivalent solutions, example

110
101
011
111

$n=4$: best is 5, with 48 inequivalent solutions, example

1100
1011
0111
1110
1111

$n=5$: best is 7, with 877 inequivalent solutions, example

11100
11010
11001
10111
01111
11110
11111

$n=6$: best is 9, with 114227 inequivalent solutions, example

111000
100111
010111
001111
110110
111100
111011
111110
111101

$n=7$: best is 12, with 118485 inequivalent solutions, example

1000000
0100000
0010000
1001000
1101100
1001011
0011110
1110010
0111010
0111001
0100111
1010101

The method I'm using might be able to do $n=8$, but $n=10$ is impossible. If someone could verify the above are solutions, that would improve confidence in the results.

The slowest part by far is testing for equal subset sums. I run through all the subsets using a gray code, with only a few machine instructions for each. But what it really needs is some way to test the condition without enumerating subsets. Is there one?

It took about 45 seconds to do $n=6$ and 220 hours to do $n=7$. All the above solutions can be found on my [combinatorial data page][1].

ADDED Feb 24: For $n=8,9,10$ I have not proved what the largest size is. It would be plausible to prove it for $n=8$ but I don't know how to do larger sizes.

For $n=8$, I have more than 4 million sets of size 14 and there are more.

For $n=9$, I have 160445 sets of size 16 but there are more.

For $n=10$, I have 27620 sets of size 19 but there are more. Here is one:

0001111011
1010111100
1011010001
0111010100
1110110111
1101000101
1011100010
0100110011
0110010001
0101101100
1101101101
0110100011
0001010110
0000110110
1100011010
1000101001
0010001111
1000010111
0110001000

In a separate answer I prove an upper bound of 30 for $n=10$. However I will be quite surprised if even 20 is possible. [1]: http://cs.anu.edu.au/~bdm/data/dissociated.html

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147