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)

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

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)$.

  • $\begingroup$ Sorry, I've missed that $a_i$, $b_i$ are integers. Now it's fixed, as far as I can see. $\endgroup$ – Sasha Kozachinskiy Oct 21 '18 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 '18 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.