2-D: Max/Min Sums From Permutations

Leroy Quet qq-quet at mindspring.com
Mon Jan 31 20:16:42 CET 2005


I have some interest in this 2-d version of the first problem.

Place the integers 1 through n^2 into a n-by-n grid, one distinct integer 
per grid-square.

If a row of the grid is <g(1,m), g(2,m), g(3,m),...g(n,m)>
and a column is <g(m,1), g(m,2), g(m,3),...g(m,n)>,
then we can have the sums:

R = sum{m=1 to n} (g(1,m)*g(2,m) +g(2,m)*g(3,m) +...g(n-1,m)*g(n,m))

C = sum{m=1 to n} (g(m,1)*g(m,2) +g(m,2)*g(m,3) +...g(m,n-1)*g(m,n))

2 sequences come to mind.

What is the maximum |R - C| for any given n?

How many ways for each n are there of arranging 1 through n^2 in the grid 
so R = C?
(For example, we can have:
5 3 9
2 6 4
1 8 7
And R = C = 142.)

And we can ask about the circular version of this problem too,
where g(n,m)*g(1,m) is added to the R sum, and
g(m,n)*g(m,1) is added to the C sum.


thanks,
Leroy Quet





More information about the SeqFan mailing list