Lets say we have a set of numbers $\{ 5, 7, 1, 2, 5, 100 \}$. I want to find a number $x$ such that the sum of distances of every number from the set to $x$ is minimal.
My first thought was that $x$ is the average of all elements of the set: $\frac{5+7+1+2+5+100}{6}$, but it is not true, it fails the above example.
Any help or hint will be appriciated, thanks.
On
First sort your [multi]set: $\{1, 2, 5, 5, 7, 100\}$. The number you want is $5$. The sum is $4 + 3 + 0 + 0 + 2 + 95 = 104.$
Proof: suppose you have another number $n \neq 5$.
Note that for any number $x$, $|x - a| + |x - b| \ge |a - b|$ by the triangle inequality, where equality holds if and only if $x$ is between $a$ and $b$ (inclusive). Hence, it must hold that the sum of its distances to the two $5$s, i.e. $$|n - 5| + |n - 5| \ge |5 - 5| + |5 - 5| = 0.$$ Similarly, $$|n - 2| + |n - 7| \ge |5 - 2| + |5 - 7| = 5,$$ $$|n - 1| + |n - 100| \ge |5 - 1| + |5 - 100| = 99.$$
You can't have the total distance any lower. Q.E.D.
In general, first sort your set, then any number between (including) the middle two numbers will do. For example, for set ${1, 2, 3, 4, 5, 6}$, any $x$ such that $3 \le x \le 4$ does.
You are looking to minimize $$\sum_{y \in A} |y - x|$$ with respect to $x$ where $A$ is your set.
It can be proved that any median minimizes this problem. In your case, the only median is $5$, so that's the result.