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

$n$ — натурал сан болсын. $1$-ден $n$-ге дейінгі бүтін сандар $n \times n$ өлшемдегі кестенің ұяшықтарына (әр ұяшыққа бір сан) жазылған, мұнда әр сан әрбір қатарда және әрбір бағанда дәл бір рет кездеседі. $r_i$ деп — $i$-ші қатардағы ($1 \le i \le n$) $(a, b)$ жұптарының саны, мұнда $a > b$, бірақ $a$ саны $b$-дан сол жақта орналасқан (көрші тұруы міндетті емес). Сол сияқты, $c_j$ — $j$-ші бағандағы ($1 \le j \le n$) $(a, b)$ жұптарының саны, мұнда $a > b$, бірақ $a$ саны $b$-дан жоғары орналасқан (көрші тұруы міндетті емес). $$ r_1 + r_2 + \cdots + r_n + c_1 + c_2 + \cdots + c_n$$ қосындының мүмкін болатын ең үлкен мәнін табыңыз. Ескерту: $n \times n$ кестесінде қатарлар жоғарыдан төмен қарай $1$-ден $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