login
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

%I #40 Nov 25 2021 12:41:20

%S 0,6,9,27,63,128,237

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

%C Also known: 405 <= a(8) <= 411; 650 <= a(9) <= 653; a(10) = 992; 1454 <= a(11) <= 1457; 2061 <= a(12) <= 2066.

%C Conjecture: a(n) = ceiling( (n^4 - n^2 + 14) / 10 ), matching the lower bound, for all n > n_0 for some constant n_0.

%F Lower bound: a(n) >= ceiling( (n^4 - n^2 + 14) / 10 ) for n > 1.

%F 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.

%F a(n) < (1/10)*n^4 + 48*n^3 + (1299/10)*n^2 + 4*n, see the PARI program. - _Robert Gerbicz_, Jan 15 2021

%e 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.

%e Examples for each size:

%e n = 1

%e 0

%e n = 2

%e 0 1

%e 2 3

%e n = 3

%e 0 0 0

%e 0 1 3

%e 1 4 0

%e n = 4

%e 0 0 0 0

%e 0 1 3 7

%e 3 6 3 1

%e 0 2 0 1

%e n = 5

%e 0 0 0 0 0

%e 0 9 5 11 1

%e 1 5 1 3 0

%e 1 6 4 6 0

%e 0 1 6 3 0

%e n = 6 (Rob Pratt)

%e 0 0 0 0 0 0

%e 0 12 10 5 15 1

%e 1 2 3 4 7 0

%e 0 3 4 3 9 0

%e 2 17 5 5 14 0

%e 0 0 0 2 4 0

%e n = 7 (Rob Pratt)

%e 0 0 2 0 0 0 0

%e 0 4 15 20 8 20 1

%e 0 13 0 0 0 6 0

%e 1 8 5 14 10 16 0

%e 0 9 0 2 0 14 0

%e 2 11 23 10 3 17 1

%e 0 0 0 0 0 2 0

%e n = 10

%e 0 0 0 0 0 0 0 0 0 0

%e 0 4 11 20 29 31 22 14 6 1

%e 1 11 5 0 0 0 0 0 14 0

%e 0 20 11 25 24 27 29 16 23 0

%e 0 30 0 33 8 10 7 0 32 0

%e 0 33 0 31 0 19 20 1 36 0

%e 0 24 1 25 30 14 31 0 27 0

%e 0 15 2 13 0 0 11 0 18 0

%e 1 7 15 24 34 37 28 16 10 0

%e 0 1 1 0 0 0 0 0 3 0

%o (PARI) /* Example for a(n)<1/10*n^4+48*n^3+1299/10*n^2+4*n.

%o To get the explicit matrix solution call F(n);

%o this also checks if the matrix is a good solution or not. */

%o c(x,y,n)={if(x>1&&x<n&&y>1&&y<n, 0, x==1&&y==1, 31, x==1&&y==n, 61, x==n&&y==n, 77, x==n&&y==1, 55, x==1, 2, y==n, 10, x==n, 15, y==1, 19)}

%o F(n)={A=matrix(n,n,i,j,(n*(i-1)+j-1)\5+ (n%5==0)*((j-1)%5==3)+ (n%5==1)*(((j-1)%5==4)-((j-1)%5==1))+ (n%5==4)*(((j-1)%5==2)-((j-1)%5==4))+ c(i,j,n)*n^2);

%o for(j=2,n-1,A[1,j]+=(j-1)*n;A[n,j]+=(j-1)*n);

%o for(i=2,n-1,A[i,1]+=(i-1)*n;A[i,n]+=(i-1)*n);

%o my( S=matrix(n,n), w=vector(n^2), dx=[0,1,-1,0,0], dy=[0,0,0,1,-1], ans=0);

%o for(i=1,n, for(j=1,n,ans+=A[i,j]; for(h=1,5,x=i+dx[h];y=j+dy[h];

%o if(x>0&&x<=n&&y>0&&y<=n, S[i,j]+=A[x,y])); w[n*(i-1)+j]=S[i,j]));

%o if(length(Set(w))<n^2, 0, print(ans); A)}

%o \\ _Robert Gerbicz_, Jan 15 2021

%o (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. */

%o 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)}

%o /* 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.) */

%o 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])

%o /* 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). */

%o {a(n, verbose=1, N=vN(n), o=0, L=n^2\2+(n==2), T=(n^4-n^2+23)\10+(3<n&&n<6), m=n^4-1+o)= n>1 && forvec(M=vector(#N,i,[o,if(i>n||n==2,min(i,L))]), my(s=score(M,N)); if(s && s<m, m=s; verbose && printf("s%d=%d, ", M, s); m<=T && break)); m} \\ _M. F. Hasler_, Jan 15 2021

%K nonn,more,nice

%O 1,2

%A _Hugo van der Sanden_, Jan 13 2021

%E a(5) confirmed minimal and a(6)-a(7) found by Rob Pratt