Understanding a step in: find the minimum value of $f(x)=\left|x-1\right| + \left|2x-1\right| + \left|3x-1\right| + \cdots + \left|119x - 1 \right|$.

Question

Problem statement: What is the minimum value of $f(x)=\left|x-1\right| + \left|2x-1\right| + \left|3x-1\right| + \cdots + \left|119x - 1 \right|$?

Quoted portion of a solution I am not understanding: "If we graph each term separately, we will notice that all of the zeros occur at $\frac{1}{m}$, where $m$ is any integer from $1$ to $119$, inclusive: $|mx-1|=0\implies mx=1\implies x=\frac{1}{m}$.

The minimum value of $f(x)$ occurs where the absolute value of the sum of the slopes is at a minimum $\ge 0$, since it is easy to see that the value will be increasing on either side. That means the minimum must happen at some $\frac{1}{m}$."

Question: Is the above clearly explained? I am not understanding it. Can someone break it down for me?

Source: https://artofproblemsolving.com/wiki/index.php/2010_AMC_12A_Problems/Problem_22

Answer 1

As presented, the argument is indeed not completely clear. What we can say, maybe more clearly, is that:

• $f$ is countinuous (sum of countinuous functions)
• $f$ is a piecewise linear/affine function (sum of piecewise linear/affine functions)
• $f$ is decreasing for $x\le \frac1{119}$ and increasing for $x\ge 1$

therefore, by EVT, minimum value occurs at some breakpoints $x=\frac1{119},\frac1{118},\ldots,\frac12,1 $.

From here, we can obtain a solution in a number of different ways.

For example, we can observe that going from $x\le \frac1{119}$ to $x\ge 1$ slope progressively increases from negative to positive value, thus the minimum occurs when the slope changes from negative to positive or when it is zero.

Suppose then that exists an integer $N$ with $1\le N\le 119$ such that

$$\sum_{k=1}^N k = \sum_{k=N+1}^{119}k \iff \frac{N(N+1)}2=\frac{119(119+1)}2-\frac{N(N+1)}2 \iff N=84$$

that is for $\frac1{85}<x_0<\frac1{84}$ the slope becomes zero and the function is constant with

$$f(x_0)=\overbrace{-(x-1) -(2x-1) - \ldots - (84x-1)}^{\text{84 terms}}+ \overbrace{(85x-1)+ \ldots + (119x-1)}^{\text{35 terms}}=$$

$$\require{cancel}=\cancel{-3570 x}+84\cancel{+3570x}-35=49$$

which is the minimum value.

Answer 2

Hint: $$ -x \leq |x| \implies -\sum_{m=1}^{119}({mx -1}) \leq \sum_{m=1}^{119}|mx -1|$$

Answer 3

Use the concept of median minimizing the mean deviation $(MD)_x$:

$f(x)=\sum_{k=1}^{119} k|x_k-x|=119*(MD)_x$, $(MD)_x$ mean deviation of $x_k=\frac{1}{k}$ with frequency $f_k=k$. The total no. of data points are $N=\sum_{k=1}^{119} k=119 \times 60=7140.$ So the median $x_m$ will be $x_m=1/84$ as $3570= \frac{84*85}{2}$. Finally, $$\text{Mon}(f(x))=f(x_m)=\sum_{k=1}^{119}|1-k x_m|=\sum_{k=1}^{119}|k/84-1]=\frac{1}{84} \sum_{k=1}^{119}|k-84|=49.$$

Answer 4

With

$$ f_a(x)= |a x-1| $$

we have

$$ \frac{d}{dx}f_a(x) = -a+2a\theta\left(x-\frac 1a\right),\ \ \ \text{undefined at}\ \ \ x = \frac 1a $$

with $\theta(\cdot)$ the heaviside unit step function then

$$ \frac{d}{dx}\sum_{k=1}^n f_k(x) = -\sum_{k=1}^n k + 2\sum_{k=1}^n k\theta\left(x-\frac 1k\right) $$

so we need to determine $m$ such that

$$ -\sum_{k=1}^n k + 2\sum_{k=1}^m k \approx 0 $$

For this case we have

$$ -\sum_{k=1}^{119} k + 2\sum_{k=1}^{84} k = 0 $$

hence the minimum occurs at $x = \frac{1}{84}$