In an $n \times n$ table, we write down the numbers $1,2, \ldots, n^{2}$ in sequence:

$$
\begin{array}{cccc}
1 & 2 & \ldots n \\
n+1 & n+2 & \ldots 2 n \\
\vdots & \vdots & \vdots \\
n^{2}-n+1 & n^{2}-n+2 & \ldots n^{2}
\end{array}
$$

From each row, we select one number such that no two are in the same column. What are the possible values of the sum of the selected numbers?
Solution. The $b$-th element of the $a$-th row in the number table is equal to $(a-1) \cdot n + b$ $(1 \leq a \leq n, 1 \leq b \leq n)$.

If we select one number from each row, we will select a total of $n$ numbers, and since no two of these can be in the same column, we will select exactly one element from each row and column. If we select the $b_{i}$-th element from the $i$-th row, then the sum of the selected elements is

\[
\begin{aligned}
& 0 \cdot n + b_{1} + 1 \cdot n + b_{2} + 2 \cdot n + b_{3} + \cdots + (n-1) \cdot n + b_{n} = \\
& (*) \quad = \frac{(n-1) \cdot n}{2} \cdot n + b_{1} + b_{2} + \cdots + b_{n}
\end{aligned}
\]

We know that $1 \leq b_{i} \leq n$, and each value appears, so their sum is $\frac{n \cdot (n+1)}{2}$. Therefore, the value of $(*)$ is:

\[
\frac{(n-1) \cdot n}{2} \cdot n + \frac{n \cdot (n+1)}{2} = \frac{n^2 (n-1) + n \cdot (n+1)}{2} = \frac{n^3 + n}{2}
\]

and this sum is independent of the selected numbers.

Remark. Using the notation $a_{xy}$ for the $y$-th element of the $x$-th row, it can be shown that $a_{ij} + a_{kl} = a_{il} + a_{kj}$, since

\[
\begin{aligned}
& a_{ij} + a_{kl} = (i-1) \cdot n + j + (k-1) \cdot n + l \\
& a_{il} + a_{kj} = (i-1) \cdot n + l + (k-1) \cdot n + j
\end{aligned}
\]

Accordingly, by adding the selected elements $a_{1j_1}$ and $a_{k_1n}$ and replacing them with $a_{1n}$ and $a_{k_1j_1}$, we get the same result, so we can swap the selected elements. The columns and rows involved will still be the same, so the swap does not affect the other elements.

In the second step, we select $a_{2(n-1)}$ and $a_{k_22}$ instead of $a_{2j_2}$ and $a_{k_2(n-1)}$. We continue this procedure. It is clear that the swap does not change the already selected elements $a_{1n}, a_{2(n-1)}$, etc. Thus, at the end of the procedure, the numbers $a_{1n}$, $a_{2(n-1)}$, $a_{3(n-2)}$, ..., $a_{(n-1)2}$, $a_{n1}$ will appear. These form an arithmetic sequence with the first element $n^2 - n + 1$, the number of elements $n$, and the $n$-th element $n$ (the common difference of the sequence is $-n + 1$). Therefore, the sum is:

\[
\frac{n^2 - n + 1 + n}{2} \cdot n = \frac{n^3 + n}{2}
\]