Is it possible to find the maximum value of a sum of absolute differences?

Question

Let $a_1$, $a_2$, …, $a_n$ and $b_1$, $b_2$, …, $b_n$ be $2n$ strictly positive integers not greater than $M$, with $M$ a given positive integer, such that $$a_1+ a_2+ \dotsb+ a_n=b_1+ b_2+ \dotsb+ b_n.$$ What is the maximum value of $$S=|a_1-b_1|+|a_2-b_2|+\dotsb+|a_n-b_n|\ ?$$

If $a_i \neq a_j$ for $i\neq j$ and $b_k \neq b_l$ for $k \neq l$ ($a_x$ can be equal to $b_y$ with any $x$, $y$), would the maximum value of $S$ remain the same? If not, what is the new maximum value of $S$?

(Sorry, English is my second language)

Answer 1

Let $J_1:=\{i\in[n]\colon a_i\ge b_i\}$ and $J_2:=[n]\setminus J_1$, where $[n]:=\{1,\dots,n\}$. Without loss of generality (wlog), $M$ is a nonnegative integer; otherwise, $M$ can be replaced by $0\vee\lfloor M\rfloor$.

Let us temporarily remove the constraint that the $a_i$'s and $b_i$'s be integers; then the maximum value of $S$ may only increase (we shall see that it actually remains the same). The values of $S$, $a_1+\dots+a_n$, $b_1+\dots+b_n$ will not change if we replace each of the $a_i$'s for $i\in J_1$ and each of the $b_i$'s for $i\in J_1$ by their respective arithmetic means over $i\in J_1$. Similarly, for $i\in J_2$. So, wlog $a_i=A_k$ and $b_i=B_k$ for $k=1,2$, some $A_k,B_k$ in $[0,M]$ such that $A_1\ge B_1$ and $A_2<B_2$, and all $i\in J_k$. Also, wlog $j:=|J_1|\le|J_2|=n-j$, so that $j\le m:=\lfloor n/2\rfloor$; here, $|\cdot|$ denotes the cardinality; the condition $a_1+\dots+a_n=b_1+\dots+b_n$ then becomes $j(A_1-B_1)=(n-j)(B_2-A_2)$, and we have \begin{equation} S=j(A_1-B_1)+(n-j)(B_2-A_2)=2j(A_1-B_1)\le2mM. \end{equation}

The bound $2mM$ is attained if $a_1=\cdots=a_m=M$, $b_1=\cdots=b_m=0$, $a_{m+1}=\cdots=a_{2m}=0$, $b_{m+1}=\cdots=b_{2m}=M$, and $a_{2m+1}=b_{2m+1}=0$ in the case when $n$ is odd.

So, the maximum value of $S$ (both with and without the constraint that the $a_i$'s and $b_i$'s be integers) is $2mM=2\lfloor n/2\rfloor M$.

Remark. This solution holds if "positive integers" is understood as "nonnegative integers". If "positive integers" is understood as "strictly positive integers", then we can replace $a_i$, $b_i$, and $M$ by $a_i-1$, $b_i-1$, and $M-1$, respectively, to get nonnegative integers $a_i-1\in[0,M-1]$ and $b_i-1\in[0,M-1]$. In that case, the maximum will therefore be $2m(M-1)=2\lfloor n/2\rfloor(M-1)$; here it is assumed that $M$ is a strictly positive integer; otherwise, $M$ has to be replaced by $1\vee\lfloor M\rfloor$.

Answer 2

$\def\abs#1{\lvert#1\rvert}$Let $c_i=a_i-b_i$ for all $1 \le i \le n$. Then $c_1+c_2+\cdots+c_n=0$ and $S=\abs{c_1}+\abs{c_2}+\cdots+\abs{c_n}$. Since $1 \le a_i \le M$ and $1 \le b_i \le M$, we have $1 - M \le a_i - b_i = c_i \le M - 1$, so $\abs{c_i} \le M - 1$, so $S = \sum_{i = 0}^{n - 1} \abs{c_i} \le n(M - 1)$.

If $n = 2m$ is even, then let $c_1=c_2=\cdots=c_m=M-1$ and $c_{m+1}=\cdots=c_{2m}=1-M$. Then $S=2m(M-1)=n(M-1)$.

If $n = 2m + 1$ is odd, then let $c_1=c_2=\cdots=c_m=M-1$, $c_{m+2}=c_{m+3}=\cdots=c_{2m+1}=1-M$, and $c_{m+1}=0$. Then $S=2m(M-1)=(n-1)(M-1)$.

The maximum value of $S$ is $(n- n \bmod 2)(M-1)$.