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 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 at 15:36

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

  • 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 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 at 15:34
  • 1
    @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 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 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)$.

  • 3
    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 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 at 15:47

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.