Problem 4. Let $n$ be a positive integer. The integers from $1$ to $n$ are written in the cells of an $n \times n$ table (one integer per cell) so that each of them appears exactly once in each row and exactly once in each column. Denote by $r_i$ the number of pairs $(a, b)$ of numbers in the $i^\text{th}$ row ($1 \le i \le n$), such that $a > b$, but $a$ is written to the left of $b$ (not necessarily next to it). Denote by $c_j$ the number of pairs $(a, b)$ of numbers in the $j^\text{th}$ column ($1 \le j \le n$), such that $a > b$, but $a$ is written above $b$ (not necessarily next to it). Determine the largest possible value of the sum

\[
r_1 + r_2 + \cdots + r_n + c_1 + c_2 + \cdots + c_n.
\]

Note: In the nxn table we label the rows 1 to n from top to bottom, and we label the columns 1 to n from left to right.

Solution

Suppose $x$ is in position $i$ in some row/column. Then after it there could be at most $\min(n-i,x-1)$ smaller numbers. Having in mind that this bound is separately for the row of $x$ and for the column of $x$, as well as that $i$ is different for the different appearances of $x$ (as no row/column has a number appearing more than once, by the problem condition), we deduce that the contribution of $x$ to the overall sum is at most


$$2\sum_{i=1}^n \min(n-i, x-1) = 2\sum_{i=n-x+1}^n (n-i) + 2\sum_{i=1}^{n-x}(x-1) = 2\sum_{i=0}^{x-1}i + 2(n-x)(x-1) = x(x-1) + 2(n-x)(x-1) = (2n-x)(x-1).$$


Summing through $x=1,\ldots,n$ now gives the following upper bound for the sum:


$$\sum_{x=1}^n (2n-x)(x-1) = (2n+1)\sum_{x=1}^n x - \sum_{x=1}^n x^2 - \sum_{x=1}^n 2n = \frac{n(n+1)(2n+1)}{2} - \frac{n(n+1)(2n+1)}{6} - 2n^2 = \frac{n(n-1)(2n-1)}{3}.$$

Equality holds e.g. for the table in which the $s$-th row is $s, s-1, \ldots, 1, n, n-1, \ldots, s+1$, since for each $x$ in position $i$ in a row or column there are indeed exactly $\min(n-i,x-1)$ smaller numbers after it.

Solution 2 Solution 2
Solution 3 Solution 3