A228882 - OEIS

%I #33 Sep 25 2020 10:24:20

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

%N 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)).

%C 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_.

%C From _Rob Pratt_, Jul 27 2015: (Start)

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

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

%H IBM Research, <a href="https://www.research.ibm.com/haifa/ponderthis/challenges/December2012.html">Maximal sum 6x6 grid</a>, Ponder This December 2012.

%H Hugo Pfoertner, <a href="/A228882/a228882.txt">Examples of 9 X 9 matrices with sum of matrix entries = 216</a>.

%e a(2)=7 because no matrix satisfying the neighbor criterion with sum of elements greater than that of

%e    (3 2)

%e    (1 1)

%e exists.

%e a(3)=20:

%e    (2 4 1)

%e    (1 3 2)

%e    (2 4 1)

%e a(4)=39:

%e    (2 4 1 3)

%e    (1 3 4 2)

%e    (3 2 5 1)

%e    (2 1 3 2)

%e a(5)=63 (from _Robert Gerbicz_):

%e    (1 3 2 4 1)

%e    (2 5 1 3 2)

%e    (3 4 2 4 1)

%e    (1 1 3 5 2)

%e    (3 2 4 1 3)

%e a(6)=93 (from Mark Mammel):

%e    (1 3 2 3 1 3)

%e    (2 5 1 4 5 2)

%e    (3 4 1 2 3 1)

%e    (1 2 3 5 4 1)

%e    (3 5 4 1 2 3)

%e    (2 1 2 3 4 1)

%e a(7)=128:

%e    (1 4 2 1 3 2 1)

%e    (2 3 5 1 4 5 3)

%e    (3 1 4 3 2 1 2)

%e    (4 1 2 4 5 1 3)

%e    (2 3 5 1 3 2 4)

%e    (1 3 4 2 5 4 1)

%e    (3 2 1 3 1 3 2)

%e a(8)=170:

%e    (2 3 1 2 4 1 3 2)

%e    (1 4 1 4 3 2 5 1)

%e    (3 2 3 5 1 3 4 2)

%e    (4 1 5 2 4 5 1 1)

%e    (2 3 4 1 3 2 3 4)

%e    (1 5 2 4 5 1 4 2)

%e    (2 4 1 3 2 3 5 1)

%e    (1 3 2 4 1 4 2 1)

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

%K nonn,hard,more

%O 1,2

%A _Hugo Pfoertner_, Sep 06 2013

%E Edited by _Jon E. Schoenfield_, Sep 21 2013

%E a(1)-a(8) confirmed by _Rob Pratt_, Jul 27 2015

%E a(9) from _Hugo Pfoertner_, Sep 17 2020