0
$\begingroup$

Let $M$ be a positive integer such that $M>2$. Choose $2n$ positive integers $a_1, a_2, ..., a_n$ and $b_1, b_2, ... b_n$ not greater than $M$ such that $a_1< a_2< ...< a_n \leq M$, $b_1< b_2< ... <b_n \leq M$ and $$a_1+a_2+...+a_n=b_1+b_2+...+b_n$$

What is the maximum value of $$S=|a_1-b_1|+|a_2-b_2|+...+|a_n-b_n|$$ that $S$ could get ?

If the condition

$a_1< a_2< ...< a_n \leq M$, $b_1< b_2< ... <b_n \leq M$

is replaced by the condition

$a_i \neq a_j$ with $i\neq j$ and $b_k \neq b_l$ with $k \neq l$ ($a_i$'s doesn't have to be different from $b_j$'s with any $i, j$)

would the maximum value of $S$ remain the same ?

I tried to use the inequality $|a|+|b| \geq |a+b|$ but it didn't work. Is it possible to find the maximum value of $S$ ?

(Edit: Thank you Sasha Kozachinskiy for your answer in the case $a_1, a_2,...,a_n$ weren't distinct integers, I have edited the question)

(sorry, English is my second language)

$\endgroup$
3
  • $\begingroup$ What has this to do woth linear-algebra? Or with abstract-algebra? $\endgroup$ Oct 21, 2018 at 14:22
  • 2
    $\begingroup$ Hint: Use that $$|x|\geq 0$$ for all real $x$ $\endgroup$ Oct 21, 2018 at 14:24
  • $\begingroup$ There is very little to maximize after you let $a_i,b_i$ be given. $\endgroup$
    – LinAlg
    Oct 21, 2018 at 14:28

1 Answer 1

1
$\begingroup$

Of course the following upper bound holds: $S \le n (M - 1)$.

This upper bound is tight when $n$ is even. Indeed, you can take: \begin{align*} &a_1 = \ldots = a_{n/2} = M, \qquad &&a_{n/2 + 1} = \ldots = a_n = 1,\\ &b_1 = \ldots = b_{n/2} = 1, \qquad &&b_{n/2 + 1} = \ldots = b_n = M. \end{align*}

When $n$ is odd the maximal possible value of $S$ is $(n - 1) (M - 1)$. It is easy to come up with an example achieving this bound (modify the previous example). Now we have to show that $S_n \le (n - 1)(M - 1)$. Assume that $n = 2k + 1$. Define $$U = \{i\in\{1, 2, \ldots, n\} : a_i \ge b_i\}, \qquad V = \{i\in\{1, 2, \ldots, n\} : a_i < b_i\}.$$ Note that $$S = \sum\limits_{i\in U} a_i + \sum\limits_{i\in V} b_i - \sum\limits_{i\in U} b_i - \sum\limits_{i\in V} a_i.$$ Using the fact that $$a_1 + \ldots + a_n = b_1 + \ldots + b_n,$$ we can rewrite $S$ as follows: \begin{align*} S &= \sum\limits_{i\in U} a_i + \sum\limits_{i\in V} b_i - \sum\limits_{i\in U} b_i - \sum\limits_{i\in V} a_i = \sum\limits_{i\in U} a_i + (\sum\limits_{i\in U} a_i + \sum\limits_{i\in V} a_i - \sum\limits_{i\in U} b_i) - \sum\limits_{i\in U} b_i - \sum\limits_{i\in V} a_i \\ &= 2 \sum\limits_{i\in U} (a_i - b_i) \le 2 |U| \cdot (M - 1). \end{align*} Also you can write \begin{align*} S &= \sum\limits_{i\in U} a_i + \sum\limits_{i\in V} b_i - \sum\limits_{i\in U} b_i - \sum\limits_{i\in V} a_i = (\sum\limits_{i\in U} b_i + \sum\limits_{i\in V} b_i - \sum\limits_{i\in V} a_i) + \sum\limits_{i\in V} b_i - \sum\limits_{i\in U} b_i - \sum\limits_{i\in V} a_i \\ &\le 2 \sum\limits_{i\in V} (b_i - a_i) \le 2 |V| \cdot (M - 1). \end{align*} By noticing that either $|U|$ or $|V|$ is at most $k$, we obtain $|S| \le 2k(M - 1) = (n - 1)(M - 1)$.

$\endgroup$
2
  • $\begingroup$ Sorry, I've missed that $a_i$, $b_i$ are integers. Now it's fixed, as far as I can see. $\endgroup$ Oct 21, 2018 at 15:50
  • $\begingroup$ Thank you for your answer. However I have edited the question, $a_i$'s must be distinct positive integers, $b_i$'s must be distinct ($a_i$ can be equal to $b_j$) Can you find the maximum value of $S$ in this case ? $\endgroup$
    – apple
    Oct 21, 2018 at 16:24

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.