1
$\begingroup$

How to find minimum value of $$|x-1| + |x-2| + |x-31| + |x-24| + |x-5| + |x-6| + |x-17| + |x-8| + \\|x-9| + |x-10| + |x-11| + |x-12|$$ and also where it occurs ?

I know the procedure for find answer for small problems like the following

what is the minimum value of |x-2| + |x+3 | + |x-5| and where it occurs ?

Here it is easy to visualise and give answer or even possible mathematically using equations as

Let the point be at distance c from $x = -3$ so the sum of the distances from the $3$ points $x =2$ , $x=-3$ , $x=5$ are $5-c$ , $8-c$ and $c$ respectively ,so total distance is minimum when it is 8 as $x=-3$ and $x=5$ are the farthest and they are $8$ units away so the required point must lie within this region so

$$ 5-c + 8-c + c = 8 $$ $$ c = 5 $$ so the point where minimum value occurs is at $x =2$

to find the minimum value substitute it in equation to get value as 8.

But In this problem it is hard to do it this way as there are more points .

Is there any easy way to find the answer .

Thanks

$\endgroup$
  • $\begingroup$ What grade are you in? If possible, just download any graph software, and graph some simple functions of that form, like $|x - 1| + |x - 2| + |x - 3|$, or $|x - 1| + |x - 2| + |x - 3| + |x - 4|$, ... Then try to reason the way those graphs behave by splitting the original functions in to piecewise ones. $\endgroup$ – user49685 Jul 24 '13 at 17:35
  • $\begingroup$ Hi @user49685 , I tried in wolframalpfa bit.ly/135npTz . I am able to reason it , as this has to be done the way my example in above post goes , I am searching for an easier way to do it .If you know some easier way please suggest .This is clear in the question I posted . $\endgroup$ – Harish Kayarohanam Jul 24 '13 at 17:47
2
$\begingroup$

As you pointed out, the expression gives the sum of the distances of $x$ from the various points.

Imagine that you are somewhere to the left of all the points, and start walking to the right. For every tiny step you take, say of length $s$, the sum of your distances to the points decreases by $12s$.

This is true until you reach the point $x=1$. Then for a while, if you take a tiny step $s$, your distance from $1$ increases by $s$, but your distance from each of the other $11$ points decreases by $s$, so the sum of the distances decreases by $11s-s=10s$.

This continues until you hit $x=2$. After that, for a while, every tiny step of length $s$ increases your distances from $1$ and $2$ by $s$ each, and decreases your distances from each of the others by $s$, for a total decrease of $8s$.

Keep walking. When you reach the next point in the list, which is $5$, each tiny step of length $s$ gives you a net decrease of $6s$. Continue. When you reach $6$ and take a small step, the sum decreases by $4s$. When you reach $8$ an move right, the decrease is $2s$.

Finally, when you reach $9$, and take a small step, the distance from each of the $6$ points to your left increases by $s$, but the distance from each point to your right decreases by $s$, so there is no change in the sum.

Finally, when you reach $10$ and continue walking to the right, the sum of the distances starts to increase.

So the minimum sum is reached at all points between $x=9$ and $x=10$. To find the minimum sum, evaluate at say $x=9$.

Remark: We used a lot of words in order to try to describe what was going on. But basically you move right until half the points are to your left and half are to your right. If we have instead points $a_1,a_2,\dots,a_n$, where $n$ is odd, the minimum is reached at the median of the points $a_i$. The answer is the same if $n$ is even, but there will be an interval of medians.

$\endgroup$
  • $\begingroup$ Ya but the procedure to predict is easy for the case of even distribution , but here the points are not , namely x = 31 , x=17 $\endgroup$ – Harish Kayarohanam Jul 24 '13 at 17:39
  • $\begingroup$ I did not notice the switches! $\endgroup$ – André Nicolas Jul 24 '13 at 18:02
  • $\begingroup$ ya,nice answer. it is not matter what $a_{i}$ is. $\endgroup$ – chenbai Jul 25 '13 at 13:07
1
$\begingroup$

Let's make it generic, you want to minimise

$$f(x) = \sum_{k = 1}^n \lvert x - p_k\rvert,$$

where, without loss of generality, $p_1 \leqslant p_2 \leqslant \ldots \leqslant p_n$.

How does the value of $f(x)$ change if you move $x$

  • left of $p_1$,
  • between $p_k$ and $p_{k+1}$,
  • right of $p_n$?

A simple counting argument finds the location of the minimum.

$\endgroup$
  • $\begingroup$ Hi , Can you please work out and show the solution . I did not get your point "A simple counting argument". Sorry for the inconvenience . $\endgroup$ – Harish Kayarohanam Jul 24 '13 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.