13
$\begingroup$

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

I think the link maxumum $30720$ it's right,because I found when $$\{a_{1},a_{2},\cdots,a_{31}\}=\{1,2,3,\cdots,16,2001,2002,\cdots,2015\}$$,and $$\{b_{1},b_{2},\cdots,b_{31}\}=\{961,962,\cdots,991\}$$ then $$S=|a_1-b_1|+|a_2-b_2|+\cdots+|a_{31}-b_{31}|=30720$$ But　Ｉ can't prove

It's from:2015 CMO

$\endgroup$
6
  • $\begingroup$ I think the link $30720$ it's right,because I found when $\{a_{1},a_{2},\cdots,a_{31}\}=\{1,2,3,\cdots,16,2001,2002,\cdots,2015\}$,and $\{b_{1},b_{2},\cdots,b_{31}\}=\{961,962,\cdots,991\}$ $\endgroup$
    – user253631
    Dec 18, 2015 at 13:05
  • $\begingroup$ Is $a_i \ne b_i \space \forall i$? $\endgroup$
    – Deepak Gupta
    Dec 18, 2015 at 13:16
  • $\begingroup$ this problem can't have this condtion. But I think when maximum can't $a_{i}\neq b_{i}$ $\endgroup$
    – user253631
    Dec 18, 2015 at 13:17
  • $\begingroup$ Sorry, I had to remove my answer because I found one mistake with it where I did not enforce the "strictly rising" constraint on the $a_i$ and $b_i$ series. $\endgroup$
    – Deepak Gupta
    Dec 18, 2015 at 14:23
  • $\begingroup$ what is the link to 2015 CMO supposed to point to: I didn't see anything related there? I find interesting that $31\cdot(2015-31)/2=30752$ comes close to the proposed answer, though I don't see how to use or modify this to perhaps come with an argument that finds the exact answer. Also, $30720=1024\cdot30=2^{10}\cdot30$, and $30720=1024\cdot30=(31\cdot33+1)\cdot30$. I wonder if this could provide any hints. $\endgroup$
    – Mirko
    Dec 24, 2015 at 17:45

1 Answer 1

Reset to default
3
+50
$\begingroup$

This is an outline of my solution.

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.

$\endgroup$
1
  • $\begingroup$ My solution in CMO was 2 pages long, this was just a sketch. I left out some details about how to construct $c_i,d_i$. $\endgroup$
    – Element118
    Dec 25, 2015 at 23:58

You must log in to answer this question.