INMO 2002 Problem 6

Suppose the $n^{2}$ numbers $1,2,3, \ldots, n^{2}$ are arranged to form an $n$ by $n$ array consisting of $n$ rows and $n$ columns such that the numbers in each row(from left to right) and each column(from top to bottom) are in increasing order. Denote by $a_{j k}$ the number in $j$-th row and $k$-th column. Suppose $b_{j}$ is the maximum possible number of entries that can occur as $a_{j j}, 1 \leq j \leq n$. Prove that

$$b_{1}+b_{2}+b_{3}+\cdots b_{n} \leq \frac{n}{3}\left(n^{2}-3 n+5\right)$$

(Example: In the case $n=3$, the only numbers which can occur as $a_{22}$ are 4,5 or 6 so that $b_{2}=3$.)