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

Question

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)

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