An interesting contest math problem: find the maximum value of $f(a_1,a_2,...,a_n)$

Question

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.

Answer 1

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.

Answer 2

Inspired by John Omielan's answer,here is my attempt.

Our goal is to find the maximum value of \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}

We can regard $f(a_1,a_2,...,a_n)$ as the foumula with coefficients$$f(a_1,a_2,...,a_n)=x_1a_1+x_2a_2+...+x_na_n$$

An important observation is that the sum of the coefficients $x_1+x_2+...+x_n$ has to be $0$.On the other hand, $a_1$ and $a_n$ appear only once and the other terms $a_i,(0\leqslant i \leqslant n-1)$ appear twice, so we get $x_1,x_n \in \{-1,1\}$, and $x_i\in\{-2,0,2\}$, $(0\leqslant i \leqslant n-1)$.

Now the problem seems to get clear.It's time to discuss $n$ is even or odd now.We first let $b_i=i+2^i,1\leqslant i \leqslant n$

$(1)$ When $n$ is even:

The coefficients $2$ appear ${n\over 2}$ times,the coefficients $-2$ appear ${n\over 2}$ times either.And the coefficients $1$ and $-1$ both appear once.

Suppose $n=2k,k\geqslant 2$

\begin{align} f(a_1,a_2,...,a_n)&=2(b_{2k}+...+b_{k+2})+b_{k+1}-b_k-2(b_{k-1}+...+b_1)\\ &=2[(2k)+...+(k+1)-k-...-1]+k-(k+1)\\ &+2[2^{2k}+...+2^{2k-1}-2^k-...-2]+2^k-2^{k+1}\\ &=2k^2-1+2^{2k+2}-2^{k+3}-2^k+4\\ &=\frac 12 n^2+4\cdot 2^{n}-9\cdot 2^{\frac n2}+3 \end{align}

$(2)$ When $n$ is odd: The situation is a bit different but actually both $[1]$ and $[2]$ are the same.

$[1]$ The coefficients $2$ may appear ${n-1\over 2}$ times,while $-2$ appear ${n-3\over 2}$ times,$1$ appear twice and no $-1$.

$[2]$ The coefficients $2$ appear ${n-3\over 2}$ times,while $-2$ appear ${n-1\over 2}$ times,$-1$ appear twice and no $1$.

Suppose $n=2k+1,k\geqslant 1$

\begin{align} f(a_1,a_2,...,a_n)&=2(b_{2k+1}+...+b_{k+2})-b_{k+1}-b_k-2(b_{k-1}+...+b_1)\\ &=2[(2k+1)+...+(k+2)-(k+1)-k-...-1]+(k+1)+k\\ &+2[2^{2k+1}+...+2^{k+2}-2^{k+1}-...-2]+2^k+2^{k+1}\\ &=2k^2+2k-1+2^{2k+3}-13\cdot 2^{k+1}+4\\ &=\frac 12 n^2+4\cdot2^{n}-13\cdot 2^{n-1 \over 2}+\frac52 \end{align}

So we find the maximal value of it.