Minimizing a Maximum Row/Column/Diagonal Sum of Arrangement of $\{1, \cdots, n^2\}$?

54 Views Asked by At

Consider an arrangement of $\{1, \cdots, n^2\}$ into an $n \times n$ square. Let $r$ be the maximum row sum, $c$ be the maximum column sum, and $d$ be the maximum of the main diagonal and antidiagonal sums.

We want to minimize the maximum $m$ of $r$, $c$, and $d$ over all such arrangements.

For example, if we arranged $\{1, 2, 3, 4\}$ into a $2 \times 2$ square as:

$$ \begin{matrix} 1 & 2\\ 3 & 4\\ \end{matrix} $$

then $r = 7, c = 6, d = 5$, so $m = 7$, which is optimal in this case (since the 4 entry must be paired with the 3 entry).

If we instead considered $3 \times 3$, an arrangement could be:

$$ \begin{matrix} 1 & 9 & 2\\ 8 & 3 & 4\\ 5 & 6 & 7 \end{matrix} $$

In this one, we have $r = 18, c = 18, d = 11$, so $m \le 18$.

Is there a name for this problem?

1

There are 1 best solutions below

1
On BEST ANSWER

For any size of at least $3 \times 3$ you can make a magic square. All the sums will be the same, $\frac 12n(n^2+1)$. This is clearly optimal because the sum of the row sums is the sum of all the numbers in the grid. If one gets smaller, another must get larger. For $3 \times 3$ it is $$\begin{matrix} 8 & 1 & 6\\ 3 & 5 & 7\\ 4 & 9 & 2 \end{matrix}$$ with all the sums being $15$. For $3 \times 3$ this is unique up to rotation and reflection. For larger sizes there are many.