Let $a_{1}, a_{2}, \ldots, a_{n}$ be the natural numbers $1,2, \ldots, n$ arranged in some order. Determine the maximum value of the sum

$$
\left|a_{1}-1\right|+\left|a_{2}-2\right|+\ldots+\left|a_{n}-n\right|
$$

when all possible arrangements are considered.
In the examined sum, we can omit the absolute value signs if we change the sign of the terms where the absolute value of a negative number appeared. In this way, we arrive at a sum of $2n$ terms, where each of the numbers $1,2, \ldots, n$ appears twice, and among the $2n$ terms, $n$ have a negative sign. The value we are examining thus arises from the sum of the numbers $1, 1, 2, 2, \ldots, n, n$ by reducing its value by twice the sum of the numbers that appear with a negative sign. Therefore, the obtained value will be maximal if the sum of the numbers that appear with a negative sign is minimal. This latter sum has $n$ terms, and its value cannot be smaller than the sum of the first $n$ elements of the sequence $1, 1, 2, 2, \ldots, n, n$.

If we start from an appropriate sequence of numbers, it follows that precisely the first $n$ elements mentioned will appear with a negative sign. This is demonstrated by the example of the sequence $n, n-1, \ldots, 1$, as we can immediately read from the resulting

\[
|n-1|+|(n-1)-2|+\ldots+|1-n|
\]

sum.

Our task now is only to calculate this sum. The terms of this sum, whether we take them from left to right or from right to left, form an arithmetic progression with a difference of 2, starting from $(n-1)$. The terms of these progressions decrease until we reach the middle of the sum. Here, we find either two 1-valued terms or a single 0-valued term.

If $n$ is even, then the examined sum is twice the sum of an arithmetic progression with a difference of 2, starting from 1 to $(n-1)$, and having $\frac{n}{2}$ terms, which is $\frac{n^2}{2}$. If, however, $n$ is odd, then we get twice the sum of an arithmetic progression with a difference of 2, starting from 2 to $(n-1)$, and having $\frac{n-1}{2}$ terms, which is $\frac{n-1}{2}(n+1)=\frac{n^2-1}{2}$.

We can write the result in both cases as $\left[\frac{n^2}{2}\right]$, where the square brackets denote the largest integer contained in the number.

Remark. We can also achieve our goal without summing the arithmetic progression if we start from a suitably chosen sequence of numbers.

If $n=2k$, we can start from the sequence $k+1, k+2, \ldots, 2k, 1, 2, \ldots, k$. The smaller terms of the differences that appear here are the numbers $1, 2, \ldots, k$, and each appears twice. Based on the reasoning of our solution, we can state that the chosen sequence leads to the maximum sum. The absolute value of each difference is $k$, so the sum of the absolute values is $2k^2$.

If, however, $n=2k+1$, the sequence $k+2, k+3, \ldots, 2k+1, k+1, 1, 2, \ldots, k$ leads to the goal. The smaller terms of the differences that appear are again the same numbers as before, but in the middle difference, both the minuend and the subtrahend are $k+1$. From this, we can again conclude that we arrive at the maximum sum. The middle difference is 0, and the absolute value of the others is $k+1$. In this way, the sum $2k(k+1)$ results.

We can conclude that the result in both cases is the largest integer contained in $\frac{n^2}{2}$.