OFFSET
1,2
COMMENTS
In other words, largest number of nonintersecting vertex-disjoint diagonals / and \ that can be packed in an n X n grid.
/ and \ cannot be adjacent horizontally or vertically.
Two \ cannot be adjacent on a northwest-to-southeast diagonal, two / cannot be adjacent on a southwest-to-northeast diagonal.
We also extended this to m X n grids, and have some limited results.
a(n) is the size of a maximum independent set in a graph with vertices (x,y,z), x=1..n, y=1..n, z=1..2, with edges joining (x,y,z) to (x,y,3-z), (x+1,y,3-z), and (x,y+1,3-z), (x,y,1) to (x+1,y-1,1) and (x,y,2) to (x+1,y+1,2). - Robert Israel, Nov 01 2015
From Rob Pratt, Nov 09 2015: (Start)
382 <= a(27) <= 383.
a(29) = 440.
For the number of optimal solutions see A264667. (End)
Conjecture: partial sums of A260307. - Sean A. Irvine, Jul 15 2022
From Aleksandr V. Novozhilov, Apr 01 2025: (Start)
a(27) = 382.
a(31) = 501.
566 <= a(33) <= 567.
636 <= a(35) <= 637. (End)
a(35) = 636, proved using SCIP ILP solver. - Aleksandr V. Novozhilov, Apr 09 2025
LINKS
Peter Boyland, Gabriella Pintér, István Laukó, Ivan Roth, Jon E. Schoenfield, and Stephen Wasielewski, On the Maximum Number of Non-intersecting Diagonals in an Array, Journal of Integer Sequences, Vol. 20 (2017), Article 17.2.4.
Robert Israel, Code for MATLAB with CPLEX
Robert Israel, Optimal configurations for n=1..26
Mathematics StackExchange, How to solve 5x5 grid with 16 diagonals
Aleksandr V. Novozhilov, Optimal configurations for n=1..32
NRICH, Distinct Diagonals
Gabriella Pinter, Figure used to illustrate proof of lower bound in n=6k-1 case, k=1,2,3
Gabriella Pinter, Lower bound for the case n = 6k-1, Oct 27 2015
Gabriella Pinter, Solution when there are an even number of rows of cells
Yaohui Zhu, Kaiming Sun, Zhengdong Luo, and Lingfeng Wang, Progressive Self-Learning for Domain Adaptation on Symbolic Regression of Integer Sequences, Proc. 39th AAAI Conf. Artif. Intel. (2025) Vol. 39, No. 1, 1692-1699. See p. 1698.
FORMULA
Theorem: a(2*n) = n*(2n+1) (the even-indexed terms among the triangular numbers A000217). More generally, for the 2k X m case, the optimal solution is k*(m+1). See third Pinter link for proof.
Theorem: a(6*n-1) >= n + 3*n*(6*n-1). See second Pinter link for proof.
Theorem: a(n) <= a(n-2) + 2*n.
Empirical g.f.: x*(1 + 2*x + 2*x^2 + 2*x^3 + 3*x^4 + x^5 + x^6) / ((1 - x)^3*(1 + x)^2*(1 - x + x^2)*(1 + x + x^2)). - Robert Israel, Nov 01 2015. Corrected by Colin Barker, Jan 31 2018
a(n) = a(n-1) + a(n-2) - a(n-3) + a(n-6) - a(n-7) - a(n-8) + a(n-9) for n>9 (conjectured). - Colin Barker, Jan 31 2018
a(n) = n*(n+1)/2 for n even, floor(n*(n/2+2/3)+1/6) for n odd (conjecture). - Bill McEachen, Aug 11 2025
EXAMPLE
For a(2) = 3, an optimal configuration is
//
./
(This is best seen using a fixed-width font. It is better to use "." instead of " " for blank squares, because " " tends to disappear.)
Note that the bottom left square can't have / because that would conflict with the / at top right, or \ because that would conflict with its horizontal and vertical neighbors.
For a(3) = 6, an optimal configuration is
///
../
/./
For a(4) = 10, an optimal configuration may be depicted, with the grid lines explicitly drawn, as
+-+-+-+-+
|/| |\|\|
+-+-+-+-+
|/| |\| |
+-+-+-+-+
|/| | | |
+-+-+-+-+
|/|/|/|/|
+-+-+-+-+
or, using "o" and "." to represent used and unused vertices, as
.-o-o-o-.
|/| |\|\|
o-o-o-o-o
|/| |\| |
o-o-.-o-.
|/| | | |
o-o-o-o-o
|/|/|/|/|
o-o-o-o-.
For a(5) = 16, an optimal configuration is
///.\
../.\
\\.\\
\./..
\.///
For more examples, see the link "Optimal configurations for n=1..32".
CROSSREFS
KEYWORD
nonn,more,nice
AUTHOR
Gabriella Pinter, Stephen Wasielewski, Peter Boyland, Ivan Roth, G. Christopher Hruska, Jeb Willenbring, Oct 22 2015
EXTENSIONS
Additional comments and terms a(9)-a(26) from Robert Israel, Nov 01 2015
This entry is the result of merging two independent submissions, merged by N. J. A. Sloane, Nov 11 2015
Cases n=27, n=31 proved using SCIP ILP solver by Aleksandr V. Novozhilov, Apr 01 2025
STATUS
approved