Vtgyjfy

What is the minimum value of the following?
$$A = |x| + |2x+1|+|3x+2|+cdots+|99x+98|$$

What I've tried so far:

• Since $|x| = |-x| $ it is clear that $|3x + 2|$ = $|-3x - 2|$, $|5x + 4| = |-5x-4|$ and so on.


• Therefore $A geq -x + 2x+1-3x-2+4x+3-5x-4+cdots-99x-98 = -50x - 49$ and I'm stuck here.

I'm quite sure it's not the right way to go, but that's what I've tried so far. Thanks in advance.

The general term is of the form $f_n = |(n+1)x + n|$. For $x > -frac{n}{n+1} = c_n$ we have $f_n = (n+1)x + n$, for $x le -frac{n}{n+1}$ we have $f_n = -(n+1)x - n$. The terms $c_0 = 0 > c_n > c_{98} = -frac{98}{99}$.

So clearly $A$ will get large if $x>0$ or $x <-frac{98}{99}$.

So choose some $0 > x > -frac{98}{99}$. Then $c_{n-1} > x > c_n$ and
$$A = sum_{k=n}^{98} [(k+1)x + k] - sum_{k=0}^{n-1} [(k+1)x + k]\
= (98 - 2n)x + (frac12 98 cdot 99 - n (n+1))(x+1) \
= -(98 - 2n)frac{n}{n+1} + (49 cdot 99 - n (n+1))(-frac{n}{n+1} +1) \
=
frac{1}{n+1} left( -n (98 - 2n) + (49 cdot 99 - n (n+1))right) \
=
frac{n^2 - 99 n + 4851}{n+1}$$
and at $n =sqrt{4951} - 1 simeq 69.3$ this attains its local minimum $2 sqrt{4951} - 101 simeq 40 $.

So we should look at the neighbouring values to find the exact minimum of $A$ which will occur at some boundary.

For $n = 69$ and with the sum above we have that $A=frac{937}{23}simeq 40.739$.

For $n = 70$ we have that $A=frac{285}{7} simeq 40.714$ which is the lowest value, taken at $x = -frac{69}{70} simeq -0.9857$.

Hint: try to solve it for the first two terms. Then add the third term. You should see a pattern emerging.

Since the function is piecewise linear, the minimum value, if it exists, must occur at one of the transition points (and it's straightforward to notice that for large values of $|x|$, the sum is large, so indeed the minimum value does occur).

Thus, the minimum value is achieved at $x = frac{1}{n} - 1$ for some $n in B = {1,ldots, 99}$.

Now, at some $x in (frac{1}{m+1} - 1,frac{1}{m} - 1)$ for some integer $m$ between $1$ and $98$ inclusive, the derivative of $A$ is given by

$$sumlimits_{i=m+1}^{99}i - sumlimits_{j=1}^{m}j = dfrac{(99-m)(100+m) - m(m+1)}{2} = 4950 - m - m^2,$$
which is $0$ when $m = frac{-1 pm sqrt{19801}}{2}$. One of the solutions is negative, the other is between 69 and 70. Thus, $A$ is decreasing on all of $(-infty, frac{1}{70}-1)$ and increasing on all of $(frac{1}{69}-1,infty)$, so our minimum is at either $x = frac{1}{69}-1$ or $x = frac{1}{70}-1$. Evaluating these two, we find that $$Aleft(frac{1}{69}-1right) = sumlimits_{i=70}^{99}left(frac{i}{69} -1right) + sumlimits_{j=1}^{69}left(1-frac{i}{69}right)=frac{937}{23}approx 40.739mbox{, and}$$
$$Aleft(frac{1}{70}-1right) = sumlimits_{i=71}^{99}left(frac{i}{70}-1right)+sumlimits_{j=1}^{70}left(1-frac{i}{70}right) = frac{285}{7} approx 40.714,$$

hence our minimum is at $x = frac{1}{70}-1$, with a value of $frac{285}{7}$.

If a sequence $a_1le a_2le cdotsle a_N$ is given, it is known (and we can also prove) that
$$
sum_{i=1}^N|x-a_i|
$$ is minimized at the median of the sequence $(a_i)_{i=1}^N$. (Put differently, the least mean absolute deviation estimator is given by the median.) The median is defined to be $a_{frac{N+1}{2}}$ if $N$ is odd and is equal to any value in $[a_{frac{N}{2}},a_{frac{N}{2}+1}]$ if $N$ is even.

In this case, by substituting $x=-z$, the objective function is
$$
sum_{i=1}^N|z-a_i|
$$ where ${a_i}={0,frac{1}{2},frac{1}{2},frac{2}{3},frac{2}{3},frac{2}{3},frac{3}{4},frac{3}{4},ldots,frac{98}{99}}$. Since $N=1+2+cdots +99 = 4950$, we should look for $2475$-th and $2476$-th term. Since there are $1+2+cdots +j=frac{j(j+1)}{2}$ terms in $${0,frac{1}{2},frac{1}{2},frac{2}{3},frac{2}{3},frac{2}{3},frac{3}{4},ldots,frac{j-1}{j},frac{j-1}{j}},$$ we know that there are $2485$ terms in
$$
{0,frac{1}{2},frac{1}{2},frac{2}{3},frac{2}{3},frac{2}{3},frac{3}{4},ldots,frac{69}{70},frac{69}{70}}.
$$ This shows that $2475$-th and $2476$-th terms are $frac{69}{70}$, and hence the minimum is attained by $x=-z=-frac{69}{70}$.