What is the minimum value of the following? $$A = |x| + |2x+1|+|3x+2|+\cdots+|99x+98|$$
What I've tried so far:
I'm quite sure it's not the right way to go, but that's what I've tried so far. Thanks in advance.
On
Hint: try to solve it for the first two terms. Then add the third term. You should see a pattern emerging.
On
If a sequence $a_1\le a_2\le \cdots\le 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}$.
On
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
$$\sum\limits_{i=m+1}^{99}i - \sum\limits_{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 $$A\left(\frac{1}{69}-1\right) = \sum\limits_{i=70}^{99}\left(\frac{i}{69} -1\right) + \sum\limits_{j=1}^{69}\left(1-\frac{i}{69}\right)=\frac{937}{23}\approx 40.739\mbox{, and}$$ $$A\left(\frac{1}{70}-1\right) = \sum\limits_{i=71}^{99}\left(\frac{i}{70}-1\right)+\sum\limits_{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}$.
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$.