A228882 Maximum sum of elements of an n X n matrix filled with numbers such that if a(j,k)=i, then all numbers 1 ... i-1 are represented in (a(j-1,k), a(j+1,k), a(j,k-1), a(j,k+1)).

1, 7, 20, 39, 63, 93, 128, 170, 216

Offset

1,2

Comments

The IBM Ponder This Challenge of December 2012 was asking for a(6) and a corresponding matrix. Sequence proposed by Dan Dima. a(5) found by exhaustive search by Robert Gerbicz.

From Rob Pratt, Jul 27 2015: (Start)

216 <= a(9) <= 226, 269 <= a(10) <= 288, obtained via integer linear programming.

A trivial upper bound of 5n^2-4n arises from summing the upper bound (3, 4, or 5) on each matrix entry. (End)

Links

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

IBM Research, Maximal sum 6x6 grid, Ponder This December 2012.

Hugo Pfoertner, Examples of 9 X 9 matrices with sum of matrix entries = 216.

Example

a(2)=7 because no matrix satisfying the neighbor criterion with sum of elements greater than that of
   (3 2)
   (1 1)
exists.
a(3)=20:
   (2 4 1)
   (1 3 2)
   (2 4 1)
a(4)=39:
   (2 4 1 3)
   (1 3 4 2)
   (3 2 5 1)
   (2 1 3 2)
a(5)=63 (from Robert Gerbicz):
   (1 3 2 4 1)
   (2 5 1 3 2)
   (3 4 2 4 1)
   (1 1 3 5 2)
   (3 2 4 1 3)
a(6)=93 (from Mark Mammel):
   (1 3 2 3 1 3)
   (2 5 1 4 5 2)
   (3 4 1 2 3 1)
   (1 2 3 5 4 1)
   (3 5 4 1 2 3)
   (2 1 2 3 4 1)
a(7)=128:
   (1 4 2 1 3 2 1)
   (2 3 5 1 4 5 3)
   (3 1 4 3 2 1 2)
   (4 1 2 4 5 1 3)
   (2 3 5 1 3 2 4)
   (1 3 4 2 5 4 1)
   (3 2 1 3 1 3 2)
a(8)=170:
   (2 3 1 2 4 1 3 2)
   (1 4 1 4 3 2 5 1)
   (3 2 3 5 1 3 4 2)
   (4 1 5 2 4 5 1 1)
   (2 3 4 1 3 2 3 4)
   (1 5 2 4 5 1 4 2)
   (2 4 1 3 2 3 5 1)
   (1 3 2 4 1 4 2 1)

Crossrefs

Cf. A337433 (similar problem for a triangular region of the hexagonal lattice), A337434.

Sequence in context: A063151 A297882 A318790 * A140676 A025056 A038349

Adjacent sequences: A228879 A228880 A228881 * A228883 A228884 A228885

Keyword

nonn,hard,more

Author

Hugo Pfoertner, Sep 06 2013

Extensions

Edited by Jon E. Schoenfield, Sep 21 2013

a(1)-a(8) confirmed by Rob Pratt, Jul 27 2015

a(9) from Hugo Pfoertner, Sep 17 2020

Status

approved