We write the numbers $1,2, \ldots, n$ in some order, then we take the sum of the absolute values of the differences of adjacent numbers. What is the largest possible value of this sum for $n=3,4,5,6$?
The first three natural numbers can be written in six different orders:
$1,2,3$
$(2)$
$2,1,3$
$(3)$
$3,1,2$
$(3)$
$1,3,2$
$(3)$
$2,3,1$
$(3)$
$3,2,1$
$(2)$.

The sum of the absolute values of the differences between adjacent numbers is noted in parentheses next to each order. If we generally denote the sought sum as $S_{n}$, then $S_{3}=3$.

The differences for the permutations of the numbers 1, 2, 3, 4 are contained in the following schema:
![](https://cdn.mathpix.com/cropped/2024_05_02_491233ea8510867b7a39g-1.jpg?height=532&width=656&top_left_y=536&top_left_x=734)

Thus, the sum of the three differences from a single order can be at most $3+2+2=7$, which is achievable: this sum belongs to the order $3,1,4,2$, and its reverse. Therefore, $S_{4}=7$.

Similarly, we find that the largest difference among the numbers 1, 2, 3, 4, 5 is $5-1=4$, and the next value of 3 appears between two pairs of numbers: $5-2=4-1=3$. The sum associated with a single order is therefore at most $4+3+3+2=12$. However, this cannot be achieved, since the first three differences only occur if the pairs $(5,1)$, $(4,1)$, and $(5,2)$ are adjacent, or in other words, if the order includes $4,1,5,2$ or $2,5,1,4$. However, if we place the remaining 3 at either end of this block, the fourth difference will be 1. The sum of 11, which is one less, is achievable, for example, in the order $3,4,1,5,2$. Therefore, $S_{5}=11$.

For the case $n=6$, the method above gives an upper limit of $5+4+4+3+3=19$ for the sum of the five differences. However, even the 18, which is one less, cannot be achieved. If the difference of 5 does not occur, the sum can only be $4+4+3+3+3=17$. If the difference of 5 does occur, the numbers 1 and 6 must be adjacent. If both differences of 4 also occur, the block $5,1,6,2$ (or its reverse) must appear in the order, but then the remaining two differences can be at most 2. If only one difference of 4 occurs, the sum would need to be 17, with each of the other differences being 3; thus, the block $4,1,6,3$ would be part of the order, which already excludes the difference of 4. If no difference of 4 occurs, the sum cannot be 18. The sum of 17, however, does occur, for example, in the orders $3,5,1,6,2,4$ and $3,6,2,5,1,4$. Therefore, $S_{6}=17$.

Szendrei Mária (Szeged, Ságvári E. Gyak. Gimn., II. o. t.) Sashegyi László (Tatabánya, Árpád Gimn., II. o. t.)