Let $a_1,a_2,\cdots, a_{31} ;b_1,b_2, \cdots, b_{31}$ be positive integers such that $a_1< a_2<\cdots< a_{31}\leq2015$ , $ b_1< b_2<\cdots<b_{31}\leq2015$ and $a_1+a_2+\cdots+a_{31}=b_1+b_2+\cdots+b_{31}.$ Find the maximum value of $S=|a_1-b_1|+|a_2-b_2|+\cdots+|a_{31}-b_{31}|.$
Problem
Source: China Yingtan ,Dec 16, 2015
Tags: inequalities, Sequences
16.12.2015 17:05
Is there a lower bound on the $a_i$ and $b_i$? Because if we take $a_1=a$, $a_2=a_3=\ldots=a_{31}=2015$, $b_1=b_2=\ldots=b_{31}=\frac{a+2015\cdot30}{31}$, the expression can be arbitrarily large by taking $a$ arbitrarily negative.
16.12.2015 23:49
If I am not mistaken $a_i$ and $b_i$ are positive integers.
17.12.2015 03:16
$a_1+a_2+a_3+\ldots+a_{31}=b_1+b_2+b_3+\ldots+b_{31} $
17.12.2015 03:31
fattypiggy123 wrote: If I am not mistaken $a_i$ and $b_i$ are positive integers. Yeah. Sorry. I correct.
17.12.2015 08:56
$S_{max}=30720.$
28.12.2015 18:33
Since there is no answer in this thread yet, here is the solution on Math StackExchange.
29.12.2015 05:13
rkm0959 wrote: Since there is no answer in this thread yet, here is the solution on Math StackExchange. Thank rkm0959. solution on Math StackExchange: Suppose $a_1<a_2<a_3<\dots<a_{31},b_1<b_2<b_3<\dots<b_{31}$ satisfies all conditions and maximises the expression. We sort the ordered pairs $(a_i,b_i)$ in non-decreasing $a_i-b_i$. Let the sorted sequence be relabelled $(a_{\sigma(i)},b_{\sigma(i)})$ Then we generate another sequence $c_1<c_2<c_3<\dots<c_{31},d_1<d_2<d_3<\dots<d_{31}$, such that $c_i-d_i=a_{\sigma(i)}-b_{\sigma(i)}$, and this new sequence satisfies all conditions. To generate this sequence, we impose the extra condition that $d$ is an arithmetic progression with common difference $1$. Clearly, the value of the expression has not changed. Let's manipulate the expressions now. $$\sum_{a_i>b_i}(a_i-b_i)=\sum_{a_i>b_i}(a_i-b_i)-\sum a_i+\sum b_i=\sum_{a_i\leq b_i}(b_i-a_i)$$The original sum is now: $$S=\sum_{a_i>b_i}(a_i-b_i)+\sum_{a_i\leq b_i}(b_i-a_i)=\sum_{c_i>d_i}(c_i-d_i)+\sum_{c_i\leq d_i}(d_i-c_i)$$Since both sums are the same, we can take $(2-\lambda)$ of the first sum and $\lambda$ of the second sum and the sum will still be the same. Let $k$ be the number of terms in the second sum. $c_i$ has the nice property such that $c_1$ to $c_k$ are in the second sum. Here, choose $\lambda=\frac{2(31-k)}{31}$. The motivation for this is that we want to take them in a way such that terms cancel nicely later, so we take the sums in the ratio $k:31-k$. $$S=\frac{2k}{31}\sum_{k<i\leq31}(c_i-d_i)+\frac{2(31-k)}{31}\sum_{i\leq k}(d_i-c_i)$$Let's combine the $2$ sums. $$S=\frac{2}{31}\left(k\sum_{k<i\leq31}(c_i-d_i)+(31-k)\sum_{i\leq k}(d_i-c_i)\right)$$Magic double summation time! $$S=\frac{2}{31}\left(\sum_{k<i\leq31}\sum_{j\leq k}((d_j-c_j)+(c_i-d_i))\right)$$Let's use the properties of $c_i$ and $d_i$. We know $c_i\leq2015-31+i$ and $c_j\geq j$. Also, we know $d_j-d_i=j-i$. $$S\leq\frac{2}{31}\left(\sum_{k<i\leq31}\sum_{j\leq k}(j-i+2015-31+i-j)\right)$$$$S\leq\frac{2}{31}\left(\sum_{k<i\leq31}\sum_{j\leq k}1984\right)$$Now the summation is just multiplication. $$S\leq\frac{2}{31}(31-k)k\times1984$$This quadratic is maximised when $k=15$ or $k=16$. $$S\leq30720$$With the construction, we are done. (Element118)
29.11.2018 06:29
What does squing mean by Quote: We sort the ordered pairs $(a_i,b_i)$ in non-decreasing $a_i-b_i$. Let the sorted sequence be relabelled $(a_{\sigma(i)},b_{\sigma(i)})$ Then we generate another sequence $c_1<c_2<c_3<\dots<c_{31},d_1<d_2<d_3<\dots<d_{31}$, such that $c_i-d_i=a_{\sigma(i)}-b_{\sigma(i)}$, and this new sequence satisfies all conditions. To generate this sequence, we impose the extra condition that $d$ is an arithmetic progression with common difference $1$.