[seqfan] n X n binary array quasi-packing problem

[Ron Hardin]

/tmp/fwd

A quasi-packing problem.
Take a binary n X n array.
Compute S = the number of 0's which are adjacent to some 1 MINUS the number of 1's which are adjacent to some 0.
What is the maximum value of S(n)?

Upper bound.  If "adjacent" has b neighbors (in the interior case), then
S(n) <= (b-1)*n*n/(b+1)

For adjacent = "king-move", b=8

n=1 S=0 bound=0.78
n=2 S=2 bound=3.11
n=3 S=7 bound=7.00
n=4 S=10 bound=12.44
n=5 S=17 bound=19.44
n=6 S=28 bound=28.00
n=7 S=34 bound=38.11
n=8 S=46 bound=49.78

All.solutions.for.6X6..
..0..0..0..0..0..0..
..0..1..0..0..1..0..
..0..0..0..0..0..0..
..0..0..0..0..0..0..
..0..1..0..0..1..0..
..0..0..0..0..0..0..

Apparently king-move adjacency will meet the upper bound whenever n is divisible by 3.

For adjacent = "horizontally and vertically", b=4

n=1 S=0 bound=0.60
n=2 S=1 bound=2.40
n=3 S=3 bound=5.40
n=4 S=8 bound=9.60
n=5 S=11 bound=15.00
n=6 S=17 bound=21.60
n=7 S=25 bound=29.40
n=8 S=32 bound=38.40

All.solutions.for.4X4..
..0..0..1..0....0..1..0..0..
..1..0..0..0....0..0..0..1..
..0..0..0..1....1..0..0..0..
..0..1..0..0....0..0..1..0..

Some.solutions.for.6X6..
..0..1..0..0..1..0....0..1..0..0..0..1....0..1..0..0..0..1....0..0..1..0..0..0..
..0..0..1..0..0..0....0..0..0..1..0..0....0..0..0..1..0..0....1..0..0..0..0..1..
..1..0..0..0..0..1....1..0..0..0..1..0....1..0..0..0..0..1....0..0..0..1..0..0..
..0..0..0..1..0..0....0..0..1..0..0..0....0..0..1..0..0..0....0..1..0..0..0..0..
..0..1..0..0..0..1....0..0..0..0..0..1....0..0..0..0..1..0....0..0..0..0..1..0..
..0..0..0..1..0..0....0..1..0..1..0..0....0..1..0..0..1..0....0..0..1..0..0..0..

All.solutions.for.7X7..
..0..1..0..0..0..1..0....0..0..1..0..1..0..0..
..0..0..0..1..0..0..0....1..0..0..0..0..0..1..
..1..0..0..0..0..0..1....0..0..0..1..0..0..0..
..0..0..1..0..1..0..0....0..1..0..0..0..1..0..
..1..0..0..0..0..0..1....0..0..0..1..0..0..0..
..0..0..0..1..0..0..0....1..0..0..0..0..0..1..
..0..1..0..0..0..1..0....0..0..1..0..1..0..0..

Upper bound: in the perfect case, there are y 1's and n^2-y 0's.
Each 1 has to uniquely own b 0's (no overlap).
So n^2 - y = b * y, or y = n^2/(b+1).
Thus S(n) = n^2 - 2*y = (b-1)*n^2/(b+1).

More terms?  These were done by painful enumeration.
 rhhardin at mindspring.com rhhardin at att.net (either)