# How can this sum be maximized?

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$$?

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.

• Won't we get 28 if $a_1=4, a_2=3, a_3=5, a_4=2, a_5=6, a_6=1, a_7=7$? – Nicol Nov 16 '15 at 15:36
• The answer is false. Start from $a_7$ and you will end up with a different answer which sums up to $27$. – Jimmy R. Nov 16 '15 at 15:37
• @Nicol I realize now that I have made a mistake. I forget to note the very last part of the question $a_7$. Thanks for pointing it out. I'll update my answer. – Varun Iyer Nov 16 '15 at 15:38
• @Stef I realize that too. – Varun Iyer Nov 16 '15 at 15:38
• When you say that some pitfalls exist, do you mean that it's not rigorously proven that the maximum is $28$? – Nicol Nov 16 '15 at 16:04

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$

• You have an upper bound rather than a maximum. – JP McCarthy Nov 16 '15 at 19:19

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