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$

3 Answers 3

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$
10
  • $\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$
    – Adrian
    Nov 16, 2015 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, 2015 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, 2015 at 15:38
  • $\begingroup$ @Stef I realize that too. $\endgroup$
    – Varun Iyer
    Nov 16, 2015 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$
    – Adrian
    Nov 16, 2015 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$
1
  • $\begingroup$ You have an upper bound rather than a maximum. $\endgroup$ Nov 16, 2015 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .