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 1. Solution 1
Solution 2. Solution 2
Solution 3. Solution 3