29-я Балканская математическая олимпиада среди юниоров. Македония, 2025 год

Пусть $n$ — натуральное число. Целые числа от $1$ до $n$ записаны в клетках таблицы размера $n \times n$ (по одному числу в клетке) так, что каждое число встречается ровно один раз в каждой строке и ровно один раз в каждом столбце. Обозначим через $r_i$ количество пар $(a, b)$ чисел в $i$-й строке ($1 \le i \le n$), таких что $a > b$, но $a$ записано левее $b$ (необязательно непосредственно рядом). Аналогично, обозначим через $c_j$ количество пар $(a, b)$ чисел в $j$-м столбце ($1 \le j \le n$), таких что $a > b$, но $a$ записано выше $b$ (необязательно непосредственно над ним). Определите наибольшее возможное значение суммы $$ r_1 + r_2 + \cdots + r_n + c_1 + c_2 + \cdots + c_n. $$ Замечание: В таблице $n \times n$ строки пронумерованы от $1$ до $n$ сверху вниз, а столбцы — слева направо. ( Болгария )

Комментарий/решение

Если число $1 \leq k \leq n$ стоит на i-й позиции в строке, то правее $k$ может быть не более $min(n-i, k-1)$ чисел меньших $k$. Значит вся сумма для определенного $k$ не больше $2\sum \limits_{i=1}{n}{min(n-i, k-1)}=2(k-1)(n-k)+

2\sum \limits_{i=n-k+1}{n}{n-i}=2(k-1)(n-k)+2(0+1+2+…+k-1)=2(k-1)(n-k)+k(k-1)=(k-1)(2n-k)=-k^2+(2n+1)k-2n$

Значит вся сумма не превышает $(2n+1)(1+2+…+n)-2n^2-(1^2+2^2+…+n^2)=(2n+1)\frac{n(n+1)}{2}-2n^2-\frac{n(n+1)(2n+1)}{6}=\frac{n(n+1)(2n+1)}{3}-2n^2=\frac{2n^3+3n^2+n-6n^2}{3}=\frac{2n^3-3n^2+n}{3}.$

Пример расстановки чисел:

n n-1 n-2 … 1

n-1 n-2 n-3 … 1 n

n-2 n-3 … 1 n n-1

…

1 n n-1 … 2