login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
1, 4, 6, 9, 16, 20, 26, 36, 42, 52, 64, 74, 86, 100, 114, 130 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 17 23:21 EDT 2019. Contains 325109 sequences. (Running on oeis4.)