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


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

You must log in to answer this question.

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