Skip to main content
4 of 9
none on 13
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, 2 nonequivalent solutions, example

10
11

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

110
101
011
111

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

1100
1011
0111
1110
1111

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

11100
11010
11001
10111
01111
11110
11111

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

111000
100111
010111
001111
110110
111100
111011
111110
111101

$n=7$: best is 12, 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?

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147