login
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)).
3
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)
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
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