2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Nicol Nov 16 '15 at 15:36
  • $\begingroup$ The answer is false. Start from $a_7$ and you will end up with a different answer which sums up to $27$. $\endgroup$ – Jimmy R. Nov 16 '15 at 15:37
  • $\begingroup$ @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. $\endgroup$ – Varun Iyer Nov 16 '15 at 15:38
  • $\begingroup$ @Stef I realize that too. $\endgroup$ – Varun Iyer Nov 16 '15 at 15:38
  • 1
    $\begingroup$ When you say that some pitfalls exist, do you mean that it's not rigorously proven that the maximum is $28$? $\endgroup$ – Nicol Nov 16 '15 at 16:04
0
$\begingroup$

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$

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.