Encuentra un número que tenga la suma mínima de distancias entre un conjunto de números

Question

Supongamos que tenemos un conjunto de números de $\{ 5, 7, 1, 2, 5, 100 \}$. Quiero encontrar un número de $x$ tal que la suma de las distancias de cada número del conjunto a $x$ es mínima.

Mi primer pensamiento fue que $x$ es el promedio de todos los elementos del conjunto: $\frac{5+7+1+2+5+100}{6}$, pero no es cierto, no es el ejemplo de arriba.

Cualquier ayuda o sugerencia será appriciated, gracias.

Answer 1

Busca minimizar $$\sum_{y \in A} |y - x|$ $ con respecto a $x$, donde $A$ es su conjunto.

Se puede probar que cualquier mediana minimiza este problema. En su caso, la única mediana es $5$ , así que ese es el resultado.

Answer 2

Primero ordenar su [multi]: $\{1, 2, 5, 5, 7, 100\}$. El número al que desea es $5$. La suma es $4 + 3 + 0 + 0 + 2 + 95 = 104.$

Prueba: supongamos que usted tiene otro número $n \neq 5$.

Tenga en cuenta que para cualquier número $x$, $|x - a| + |x - b| \le |a - b|$. Por lo tanto, se debe sostener que la suma de sus distancias a los dos $5$s, es decir, $$|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.$$

Usted no puede tener la distancia total más bajo. Q. E. D.

En general, primero ordenar su conjunto, entonces cualquier número entre (incluyendo) el centro de los dos números va a hacer. Por ejemplo, para establecer ${1, 2, 3, 4, 5, 6}$cualquier $x$ tal que $3 \le x \le 4$ .