# How can we find the maximum value of $S=|a_1-b_1|+|a_2-b_2|+…+|a_n-b_n|\ ?$

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

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)

• What has this to do woth linear-algebra? Or with abstract-algebra? – José Carlos Santos Oct 21 '18 at 14:22
• Hint: Use that $$|x|\geq 0$$ for all real $x$ – Dr. Sonnhard Graubner Oct 21 '18 at 14:24
• There is very little to maximize after you let $a_i,b_i$ be given. – 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)$$.
• Sorry, I've missed that $a_i$, $b_i$ are integers. Now it's fixed, as far as I can see. – Sasha Kozachinskiy Oct 21 '18 at 15:50
• 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 ? – apple Oct 21 '18 at 16:24