A219760 -id:A219760 - cp's OEIS frontend

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

R. H. Hardin, Sep 30 2010

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

			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

Manfred Scheucher, Python Script
Peter J. Taylor, Java program to compute terms

Cf. A000769, A181019, A219760, A225623.

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

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

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

A213222 Minimum number of distinct slopes formed by n noncollinear points in the plane.

Original entry on oeis.org

3, 4, 4, 6, 6, 8, 8, 10, 10, 12, 12, 14, 14, 16, 16, 18, 18, 20, 20, 22, 22, 24, 24, 26, 26, 28, 28, 30, 30, 32, 32, 34, 34, 36, 36, 38, 38, 40, 40, 42, 42, 44, 44, 46, 46, 48, 48, 50, 50, 52, 52, 54, 54, 56, 56, 58, 58, 60, 60, 62, 62, 64, 64, 66, 66, 68, 68, 70, 70, 72, 72, 74, 74, 76, 76, 78, 78, 80, 80, 82, 82, 84

Offset: 3

Charles R Greathouse IV, Mar 02 2013

Scott formulated the problem (on the basis of a similar problem of Erdős), gave bounds, and conjectured the formula which Unger later proved.

Also the edge chromatic number of the n-polygon diagonal intersection graph. - Eric W. Weisstein, Mar 23 2018

Martin Aigner and Gunter M. Ziegler, Proofs from THE BOOK, Second Edition, Springer-Verlag, Berlin, 2000. Chapter 10.

Vincenzo Librandi, Table of n, a(n) for n = 3..1000
J. E. Goodman and R. Pollack, On the combinatorial classification of nondegenerate configurations in the plane, J. Combin. Theory Ser. A, 29 (1980), pp. 220-235.
Giovanni Resta, Illustration of terms a(3)-a(7)
P. R. Scott, On the sets of directions determined by n points, The American Mathematical Monthly 77:5 (1970), pp. 502-505.
Peter Ungar, 2N noncollinear points determine at least 2N directions, Journal of Combinatorial Theory, Series A, 33:3 (1982), pp. 343-347.
Eric Weisstein's World of Mathematics, Edge Chromatic Number
Eric Weisstein's World of Mathematics, Polygon Diagonal Intersection Graph
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A000769, A000755, A219760.

Cf. A000217 (maximum number of slopes, with offset 1).

[2*Floor(n/2): n in [3..100]]; // Vincenzo Librandi, Mar 29 2014

A213222:=n->`if`(n = 3, 3, 2*floor(n/2)); seq(A213222(n), n=3..100); # Wesley Ivan Hurt, Mar 28 2014

CoefficientList[Series[(3 + x - 3 x^2 + x^3)/((1 + x) (1 - x)^2), {x, 0, 100}], x] (* Vincenzo Librandi, Mar 29 2014 *)
LinearRecurrence[{1,1,-1},{3,4,4,6},100] (* Harvey P. Dale, Dec 29 2024 *)

PARI
```
a(n)=if(n>3,n\2*2,3)
```

a(n) = 2*floor(n/2) for n > 3.

G.f.: x^3*(3+x-3*x^2+x^3)/((1+x)*(1-x)^2). [Bruno Berselli, Mar 04 2013]

A277433 Martin Gardner's minimal no-3-in-a-line problem, all slopes version.

Original entry on oeis.org

1, 4, 4, 4, 6, 6, 8, 8, 8, 8

Offset: 1

Robert Israel, Oct 14 2016

a(n) is the minimal number of counters that can be placed on an n X n grid, no three in a straight line, such that adding one more counter on any vacant grid point will produce three in a line.  Lines can have any slope.
The "queens" version of this problem, where lines are restricted to vertical, horizontal and diagonal, is A219760.
a(11) <= 10, a(12) <= 10.

Robert Israel, Examples for n <= 12 (provably optimal for n <= 10).
Sandi Klavžar, James Tuite, and Ullas Chandran, The General Position Problem: A Survey, arXiv:2501.19385 [math.CO], 2025. See p. 39.

Cf. A219760.

A225623 Number of ways to arrange 2n queens on an n X n chessboard, with no more than 2 queens in each row, column or diagonal.

Original entry on oeis.org

0, 1, 2, 11, 92, 1097, 19448, 477136, 14244856, 537809179, 24194010708, 1317062528249

Offset: 1

Vaclav Kotesovec, Aug 04 2013

This problem is slightly different from A000769 or A219760. In the first example on an 8 x 8 board, the queens c7, d5 and e3 (or queens a2, c5 and e8) are in a line, but such case is allowed. The elementary step can be only [0,1], [1,0] or [1,1], not for example [1,2] or [2,3].

Vaclav Kotesovec, Examples

Cf. A000170, A000769, A001499, A001501, A058528, A075754, A172544, A172541.

Definition clarified by Vaclav Kotesovec, Dec 18 2014

a(10)-a(12) from Martin Ehrenstein, Jan 09 2022

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Java

Formula

Extensions

A213222 Minimum number of distinct slopes formed by n noncollinear points in the plane.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A277433 Martin Gardner's minimal no-3-in-a-line problem, all slopes version.

Views

Author

Keywords

Comments

Links

Crossrefs

A225623 Number of ways to arrange 2n queens on an n X n chessboard, with no more than 2 queens in each row, column or diagonal.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions