[seqfan] Re: distinct sums in a square
Rainer Rosenthal
r.rosenthal at web.de
Mon Jan 11 19:54:46 CET 2021
Hi Hugo
Congratulations, what a wonderful puzzle!
Solutions seem far from any ready-made pattern and look very sophisticated.
n=3: one can get a matrix with sum 10 easily by putting 0, 1, 2, 3, 4 on
the 5 diagonal points.
At first this looks like a real champion, but then comes your solution
with sum 9. Astonishing.
n = 4: elements seem to need at least maximum size 6 in order to find
proper places. I was able to find a solution with max 6 and sum 34, but
better results exist for sure. It is another surprise that with larger
maximum size 7 we can get smaller sums. Your record solution with max 7
is beautiful, because the element-sums are exactly all the numbers from
0 to 15.
n = 5 and n = 6: fascinating to see the borders of the square filled
with many zeroes and one zero in the middle. Everything very irregular
and without symmetry - wonderful.
Thanks for this beautiful puzzle, and a happy New Year 2021 for you all,
Rainer
Am 11.01.2021 um 01:47 schrieb hv at crypt.org:
> Define a(n) as the least k such that an n x n grid of non-negative
> integers summing to k can be found, in which each element when added
> to its orthogonal neighbours yields a distinct sum.
>
> I believe the sequence starts 0, 6, 9, 27 which is not in the OEIS.
>
> I have (not necessarily minimal) candidates for a(5) and a(6), and no
> candidate for n > 6. I'd appreciate confirmation of at least a(1) .. a(4)
> before I submit to the OEIS - I have at best medium confidence in the
> correctness of the code I've written to get these values.
>
> For n > 4, I believe [1] we need a(n) >= (n^4 - n^2 + 14) / 10, giving
> a(5) > 61.4 and a(6) > 127.4, so my candidates approach but do not hit
> the theoretical optimum. The only upper bound I have is the relatively
> useless a(n) <= 2^(n^2) - 1.
>
> Examples (need fixed font!):
>
> a(1) = 0: element sums
> 0 0
>
> a(2) = 6:
> 0 1 3 4
> 2 3 5 6
>
> a(3) = 9:
> 0 0 0 0 1 3
> 0 1 3 2 8 4
> 1 4 0 5 6 7
>
> a(4) = 27:
> 0 0 0 0 0 1 3 7
> 0 1 3 7 4 10 14 11
> 3 6 3 1 9 15 13 12
> 0 2 0 1 11 8 6 2
>
> a(5) <= 63:
> 0 0 0 0 0 0 9 4 13 1
> 0 9 4 13 1 10 19 26 22 14
> 1 6 0 4 0 7 21 17 25 5
> 0 5 3 8 0 6 16 20 18 8
> 0 2 4 3 0 2 11 12 15 3
>
> a(6) <= 134:
> 0 0 0 0 0 0 0 4 6 7 12 1
> 0 4 6 7 12 1 5 23 21 26 29 13
> 1 13 4 1 9 0 14 30 24 22 33 10
> 0 8 0 1 11 0 9 37 19 25 38 11
> 0 16 6 12 17 0 16 32 34 36 43 17
> 0 2 0 0 3 0 2 18 8 15 20 3
>
>
> Ideas, constructions, better constraints or more values all welcome.
>
> Hugo
>
> ---
>
> [1] Justification of lower bound: letting S_c be the sum of the corner
> elements and S_e the sum of the non-corner edge elements, then the total
> of all the element sums is 5a(n) - S_e - 2S_c. However they are required
> to be n^2 distinct non-negative integers, which must sum to at least
> T(n^2 - 1) = n^2 (n^2 - 1) / 2.
>
> For n > 4, making the element sums at the corners distinct 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 have their other
> adjacent edge differ by at least 1, so we have S_e + 2S_c >= 7.
>
> Thus a(n) >= (T(n^2 - 1) + 7) / 5 = (n^4 - n^2 + 14) / 10.
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list