How can this sum be maximized?

Question

Suppose that $a_1, a_2, a_3, a_4, a_5, a_6, a_7$ are distinct integers from $1$ to $7$. What is, then, the maximum value of the sum $$|a_1-a_2|+|a_2-a_3|+|a_3-a_4|+|a_4-a_5|+|a_5-a_6|+|a_6-a_7|+a_7$$?

Answer 1

Given the first $7$ integers:

$$1, 2, 3, 4, 5, 6, 7$$

We want to first maximum the quantity $a_7$

Therefore, logically, let us set $a_7 = 7$.

Now, let's work backwards.

We need to maximum the sum $|a_7 - a_6|$

Therefore, we set $a_6 = 1$.

Similarly, we $a_5 = 6$ to maximum the quantity $|a_6 - a_5|$

Following this pattern, we get that $a_1 = 4$, $a_2 = 3$, $a_3 = 5$, $a_4 = 2$, $a_5 = 6$, $a_6 = 1$ and $a_7 = 7$.

Therefore, our maximum value is:

$$|a_1-a_2|+|a_2-a_3|+|a_3-a_4|+|a_4-a_5|+|a_5-a_6|+|a_6-a_7|+a_7$$ $$ = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28$$

Comment if you have any questions.

Answer 2

By using the triangle inequality $$|x+y|\leq|x|+|y|$$

$\left|a_1-a_2\right|+|a_2-a_3|+|a_3-a_4|+...+|a_6-a_7|+a_7$

$\leq |a_1|+|a_2|+|a_2|+...+|a_7|+|a_7|$

$=a_1+2(a_2+a_3+a_4+...+a_7)$

$=2(a_1+a_2+a_3+...+a_7)-a_1$

$=2(1+2+3+4+5+6+7)-a_1$

$\because$ it fully depends on $a_1$

Choose $a_1=1$,

$\therefore$Maximum$\, =2(28)-1=55$

Answer 3

While the final answer posted above is true, the logic is flawed. Maximizing a sum is not equivalent to maximizing each term. I am sure one can give plenty of counter examples to that claim.

To prove the estimate 28 more rigorously I give the following hints:

First note that $a_k + |a_k-a_{k-1}| = a_{k-1} + b_k$ where $b_k = 0$ if $a_k < a_{k-1}$ and $b_k = 2 ( a_k - a_{k-1}) $ if $a_k > a_{k-1}$

This allows us to write the sum as

$ b_7 + b_6 + ... + b_2 + a_1 $

I believe you will have very little difficulty now in maximizing this sum. For one thing note that if forexample both $b_7$ and $b_6$ are nonzero then such a scenario will not be optimal as their sum will can always be increased by a reordering of sequence.

In short you see that the maximum is

2 ( 6 + 4 + 2) + 4 = 28