Suppose the sequence $a_1,a_2,…,a_n$ is a permutation of the sequene $1+2^1,2+2^2,…,n+2^n$. Find the maximum value of $f(a_1,a_2,…,a_n)=\vert a_1-a_2\vert+\vert a_2-a_3\vert+\cdots+\vert a_{n-1}-a_n\vert$.
This is an interesting problem found in a math contest. I used to be a contest math lover when I was a high school student. I know I may solve it by finding the possible regular formula when $n=2,3,4,…$, but the method is not always effective so I hope someone can give me some hints.
By the way, as a student majored in math now, if there exists an advanced method behind it, can anyone share it with me or at least tell me what it may related with. Thanks for your answer.
Best Answer
You are asking to maximize
$$\begin{equation}\begin{aligned} f(a_1,a_2,...,a_n) & = \vert a_1-a_2\vert+\vert a_2-a_3\vert+...+\vert a_{n-1}-a_n\vert \\ & = \sum_{i=1}^{n-1}\vert a_{i} - a_{i+1} \vert \end{aligned}\end{equation}\tag{1}\label{eq1A}$$
If $a_i \ge a_{i+1}$, then $\vert a_i - a_{i+1} \vert = a_i - a_{i+1}$, else $\vert a_{i} - a_{i+1} \vert = a_{i+1} - a_{i}$. In either case, when you remove the absolute value signs to get the corresponding equivalent value, you have one sequence term being added and another one subtracted. Thus, over the $n - 1$ absolute value terms, you would have $n - 1$ sequence terms being added and $n - 1$ sequence terms being subtracted.
Note that $a_1$ and $a_n$ are used just once each. Also, $a_i$, for $i \le 2 \le n - 1$, are being used twice. The maximum possible value of \eqref{eq1A} would occur if all of the $n - 1$ sequence terms being added were the largest ones and with the $n - 1$ sequence terms being subtracted being the smallest ones, and with the special case of the $2$ terms of $a_1$ and $a_n$, as they are used just once, being the $2$ largest terms among those being subtracted.
This can be done. In particular, as stated above, have the $2$ "middle" (with ones at either side if $n$ is even) values be at the start and end of the sequence. Then at the odd indices from the start, i.e., $3,5,7,\ldots$ and the even indices back from the end, i.e., $n-2,n-4,n-6,\ldots$, you alternate back & forth placing the remaining smallest values from the smallest up. Also, at the even indices from the start, i.e., $2,4,6,\ldots$, and the odd indices back from the end, i.e., $n-1,n-3,n-5,\ldots$, you alternate back & forth placing the largest values from the largest down.
The top "half" of the values will always be beside a value from the bottom "half" of the values on either side of them in the expression in \eqref{eq1A} and, thus, the top half values will be the ones added and the bottom half values will be the ones subtracted. I'm using "half" in quotes because the $2$ ones near the middle are handled specially and there's a small issue with odd versus even values of $n$ to deal with.
As you say you used to be a contest math lover as a high school student and have majored in math now, I trust you can finish the rest yourself.