A181018 Maximum number of 1's in an n X n binary matrix with no three 1's adjacent in a line along a row, column or diagonally.

1, 4, 6, 9, 16, 20, 26, 36, 42, 52, 64, 74, 86, 100, 114, 130

Offset

1,2

Comments

Diagonal of A181019.

Three or more "1"s may be adjacent in an L-shape or step shape (cf. bottom of first example) or 2 X 2 square (top right of 2nd example) or similar. One possible (not always optimal) solution is therefore to fill the square with 2 X 2 squares of "1"s, separated by rows of "0"s: this yields the lower bound (n - floor(n/3))^2 = ceiling(2n/3)^2 given in FORMULA. I conjecture that this is optimal for n = 2 (mod 3) and that a(n) ~ (2n/3)^2. For n = 3k, the array can be filled with 2k(2k+1) "1"s by repeating the optimal solution for n = 3 on the diagonal, and filling the rest with 2 X 2 blocks separated by rows of "0"s, cf. the 4th example for 6 X 6. - M. F. Hasler, Jul 17 2015 [Conjecture proved to be wrong, see below. - M. F. Hasler, Jan 19 2016]

74 <= a(12) <= 77. - Manfred Scheucher, Jul 23 2015

You can repeat a 4 X 2 block [1100; 0011] infinitely in both directions and then crop the needed square. That gives ceiling(n^2/2). It eventually surpasses the solutions we've found so far: at 17*17 the pattern above gives 12*12=144 but this one ceiling(17*17/2)=145. The credit for finding this goes to Jaakko Himberg. - Juhani Heino, Aug 11 2015

Links

Table of n, a(n) for n=1..16.

Manfred Scheucher, Python Script

Peter J. Taylor, Java program to compute terms

Formula

a(n) >= ceiling(2n/3)^2; a(3k) >= A002943(k) = 2k(2k+1). - M. F. Hasler, Jul 17 2015; revised by Juhani Heino, Aug 11 2015

a(n) >= ceiling(n^2/2). - Juhani Heino, Aug 11 2015

Example

Some solutions for 6 X 6:
  0 1 1 0 1 1    0 1 1 0 1 1    0 1 1 0 1 1    0 1 1 0 1 1
  1 0 1 0 0 1    1 0 1 0 1 1    1 0 1 0 0 1    1 0 1 0 1 1
  1 1 0 0 1 0    1 1 0 0 0 0    1 1 0 0 1 0    1 1 0 0 0 0
  0 0 0 0 1 1    0 0 0 0 1 1    0 0 0 0 1 1    0 0 0 0 1 1
  1 0 1 1 0 1    1 0 1 1 0 1    1 1 0 1 0 1    1 1 0 1 0 1
  1 1 0 1 1 0    1 1 0 1 1 0    1 1 0 1 1 0    1 1 0 1 1 0
A solution with 73 ones for 12 X 12 (I replaced "0" with "." for readability):
  1 1 . 1 1 . 1 1 . 1 . 1
  1 1 . . 1 1 . 1 1 . 1 1
  . . . 1 . . . . . . 1 .
  1 1 . 1 . 1 . 1 1 . . 1
  . 1 1 . . 1 1 . . 1 1 .
  1 . . . 1 . 1 . 1 . . 1
  1 1 . . 1 1 . . 1 . 1 .
  . 1 . 1 . 1 . 1 . . 1 1
  1 . . 1 1 . . 1 1 . . 1
  . 1 . . . . 1 . 1 . 1 .
  1 1 . 1 1 . 1 1 . . 1 1
  1 . 1 . 1 1 . 1 . 1 . 1
- Manfred Scheucher, Jul 23 2015
An optimal solution with 74 ones (denoted by O) for 12 X 12 (also symmetric):
  O . O . O . O O . O O .
  O O . O O . . . O O . O
  . O . O . O O . . . O O
  O . . . O O . O O . O .
  . O O . . . O . . . . O
  O O . O O . O . O O . .
  . . O O . O . O O . O O
  O . . . . O . . . O O .
  . O . O O . O O . . . O
  O O . . . O O . O . O .
  O . O O . . . O O . O O
  . O O . O O . O . O . O - Giovanni Resta, Jul 29 2015

Prog

(Java) See Taylor link
(MATLAB with CPLEX)
function v = A181018(n)
%
Grid = [1:n]' * ones(1, n) + n*ones(n, 1)*[0:n-1];
f = -ones(n^2, 1);
A = sparse(4*(n-2)*(n-1), n^2);
count = 0;
for i =1:n
  for j = 1:n-2
    count = count+1;
    A(count, [Grid(i, j), Grid(i, j+1), Grid(i, j+2)]) = 1;
  end
end
for i = 1:n-2
  for j = 1:n
    count = count+1;
    A(count, [Grid(i, j), Grid(i+1, j), Grid(i+2, j)]) = 1;
  end
end
for i = 1:n-2
  for j = 1:n-2
    count = count+2;
    A(count-1, [Grid(i, j+2), Grid(i+1, j+1), Grid(i+2, j)]) = 1;
    A(count, [Grid(i, j), Grid(i+1, j+1), Grid(i+2, j+2)]) = 1;
  end
end
b = 2*ones(4*(n-2)*(n-1), 1);
[x, v, exitflag, output] = cplexbilp(f, A, b);
end;
for n = 1:11
  A(n) = A181018(n);
end
A % Robert Israel, Jan 14 2016

Crossrefs

Cf. A000769, A181019, A219760, A225623.

Sequence in context: A010436 A085955 A266346 * A155569 A189484 A155567

Adjacent sequences: A181015 A181016 A181017 * A181019 A181020 A181021

Keyword

nonn,more,nice

Author

R. H. Hardin, Sep 30 2010

Extensions

a(11)-a(12) from M. F. Hasler, Jul 20 2015

a(12) deleted by Manfred Scheucher, Jul 23 2015

a(12) from Giovanni Resta, Jul 29 2015

PARI code (which implemented a conjectured formula shown to underestimate) deleted by Peter J. Taylor, Jan 06 2016

a(13)-a(15) from Peter J. Taylor, Jan 09 2016

a(16) from Peter J. Taylor, Jan 14 2016

Status

approved