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

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)

• You can introduce new variables $c_i = a_i - b_i$, constrained only by $\lvert c_i\rvert < M$, and then look for the maximum value of $\sum_i \lvert c_i\rvert$, which is clearly $n(M - 1)$. – LSpice Oct 21 '18 at 15:30
• Sorry, I should have said that there is also the constraint $\sum_i c_i = 0$. The bound that I proposed is still achieved for $n$ even, but the correct bound for $n$ odd is smaller, as in @IosefPinelis's answer. – LSpice Oct 21 '18 at 15:36

2 Answers

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, 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 $$$$S=j(A_1-B_1)+(n-j)(B_2-A_2)=2j(A_1-B_1)\le2mM.$$$$

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

• The integers are required to be positive. I think that you must have meant your bound to be just $2m M = 2\lfloor n/2\rfloor M$, not $2n M$. – LSpice Oct 21 '18 at 15:31
• Sorry, one more thing. You say to replace various $a$'s and $b$'s by certain arithmetic means, but how do you know that those means are integers? – LSpice Oct 21 '18 at 15:34
• @LSpice : Thank you for your comments. Here are my responses to them: $2nM$ was a typo, and it is now replaced by $2mM$. I have also addressed the integrality and positivity conditions. – Iosif Pinelis Oct 21 '18 at 16:17
• @LSpice and losif Pinelis: Thank you for your answer. However, I have edited the question. I forgot that $a_i$ should be distinct integers, sorry. – apple Oct 21 '18 at 16:38

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

• Your answer should not be formatted as a giant displayed equation. TeX (and mathematical work in general) is meant for bits of math interspersed with text, not bits of text in the midst of a math display. – LSpice Oct 22 '18 at 14:42
• I have edited, I think without changing any meaning. Your answer appears to be the same as my comments (1 2). Notice that, in the odd case, you have only shown a lower bound on the maximum value of $S$. – LSpice Oct 23 '18 at 15:47