A340630 Fill an n X n square with nonnegative integers so that all n^2 von Neumann neighborhoods have distinct sums; a(n) is smallest possible sum of the entries.
0, 6, 9, 27, 63, 128, 237
Offset: 1
Examples
For n = 3 we can construct a square grid such as { 0, 0, 0; 0, 1, 3; 1, 4, 0 } in which the elements sum to 9, and for which the respective sums of each element with its orthogonal neighbors gives the co-grid { 0, 1, 3; 2, 8, 4; 5, 6, 7 } all of whose values are distinct, so a(3) <= 9. There is no qualifying grid with a smaller sum (indeed, by the lower bound no smaller one is possible), so a(3) = 9.
Examples for each size:
n = 1
0
n = 2
0 1
2 3
n = 3
0 0 0
0 1 3
1 4 0
n = 4
0 0 0 0
0 1 3 7
3 6 3 1
0 2 0 1
n = 5
0 0 0 0 0
0 9 5 11 1
1 5 1 3 0
1 6 4 6 0
0 1 6 3 0
n = 6 (Rob Pratt)
0 0 0 0 0 0
0 12 10 5 15 1
1 2 3 4 7 0
0 3 4 3 9 0
2 17 5 5 14 0
0 0 0 2 4 0
n = 7 (Rob Pratt)
0 0 2 0 0 0 0
0 4 15 20 8 20 1
0 13 0 0 0 6 0
1 8 5 14 10 16 0
0 9 0 2 0 14 0
2 11 23 10 3 17 1
0 0 0 0 0 2 0
n = 10
0 0 0 0 0 0 0 0 0 0
0 4 11 20 29 31 22 14 6 1
1 11 5 0 0 0 0 0 14 0
0 20 11 25 24 27 29 16 23 0
0 30 0 33 8 10 7 0 32 0
0 33 0 31 0 19 20 1 36 0
0 24 1 25 30 14 31 0 27 0
0 15 2 13 0 0 11 0 18 0
1 7 15 24 34 37 28 16 10 0
0 1 1 0 0 0 0 0 3 0
Programs
-
PARI
/* Example for a(n)<1/10*n^4+48*n^3+1299/10*n^2+4*n. To get the explicit matrix solution call F(n); this also checks if the matrix is a good solution or not. */ c(x,y,n)={if(x>1&&x -
PARI
/* Return 0 if the matrix M is not a solution, else sum of elements, always > 0 except for M=(0). The 2nd arg specifies the neighborhoods, see below. */ score(M, N=vN(#M), U=[])={M=concat(Vec(M)); for(i=1,#N, #U<#(U=setunion(U,[vecsum(vecextract(M,N[i]))])) || return); vecsum(M)} /* The function vN() below computes the list of von Neumann neighborhoods for each cell labeled 1..n^2. (For repeated calls of score(), this should be computed once, stored, and given as 2nd arg.) */ vN(n)=vector(n^2,i,[c|c<-[i,i-n,if(i%n!=1,i-1),if(i%n,i+1),if(i<=n^2-n,i+n)],c>0]) /* Brute force computation of a(n), not practicable for n>=4. Optional args: verbosity (show increasingly better solutions), neighborhoods, lower & upper bound for elements, target value (stop if found). */ {a(n, verbose=1, N=vN(n), o=0, L=n^2\2+(n==2), T=(n^4-n^2+23)\10+(3
Formula
Lower bound: a(n) >= ceiling( (n^4 - n^2 + 14) / 10 ) for n > 1.
Proof: letting S_c be the sum of the corner elements and S_e the sum of the non-corner edge elements, the sum over all the n^2 von Neumann neighborhoods for any minimal example is 5a(n) - S_e - 2S_c. However those n^2 contributions are required to be n^2 distinct nonnegative integers, which must sum to at least Sum_{0 .. n^2 - 1} i = n^2 (n^2 - 1) / 2. For n > 4, getting the von Neumann neighborhoods of the corner elements to have distinct sums requires edge or corner elements contributing to sums of at least { 0, 1, 2, 3 }. The edge pieces adjacent to the corner with 0 sum must additionally have their other adjacent edge differ by at least 1, so we have S_e + 2S_c >= 7, and hence a(n) >= ceiling((n^2*(n^2 - 1)/2 + 7) / 5) = ceiling( (n^4 - n^2 + 14) / 10 ) for n > 4. Values found show that it actually holds for n > 1.
a(n) < (1/10)*n^4 + 48*n^3 + (1299/10)*n^2 + 4*n, see the PARI program. - Robert Gerbicz, Jan 15 2021
Extensions
a(5) confirmed minimal and a(6)-a(7) found by Rob Pratt
Comments