# Residence at an Optimal Distance

An interesting optimization problem is described - somewhat volubly - by Paul Nahin

Suppose we have a real line before us (labeled as the $x$-axis), stretching from $-\infty$ to $+\infty$. On this line there are marked $n$ points labeled in increasing value as $x_1 \lt x_2 \lt \ldots \lt x_n$. Let's assume that all the $x_i$ are finite (in particular $x_1$ and $x_n$), and so the interval of the $x$-axis that contains all $n$ points is finite in length. Now, somewhere (anywhere) on the finite $x$-axis we mark one more point (let's call it $x$). We wish to pick $x$ so that the sum of the distances between $x$ and and the original points is minimized. That is, we wish to pick $x$ so that

$S = |x - x_{1}| +|x - x_{2}| + \ldots + |x - x_{n}|$

is minimized.

Simply put, we seek to minimize function $S(x) = |x - x_{1}| +|x - x_{2}| + \ldots + |x - x_{n}|$, where $x_1 \lt x_2 \lt \ldots \lt x_n$ are given points on the $x$-axis.

(I have a persistent recollection that Martin Gardner also mentioned this problem as a quandary of a college girl looking for a dormitory so as to be optimally close to all her friends residing in several buildings along the same straight road. At the moment, I am unable to locate the reference.)

Solution

## References

1. P. J. Nahin, When Least Is Best, Princeton University Press, 2004

Minimize function $S(x) = |x - x_{1}| +|x - x_{2}| + \ldots + |x - x_{n}|$, where $x_1 \lt x_2 \lt \ldots \lt x_n$ are given points on the $x$-axis.

The problem admits an ingenious solution that starts with the simplified configuration. So, let's start with a small number of points, say $n=2$. In this case, $S(x) = |x-x_{1}|+|x-x_{2}|=x_{2}-x_{1}$, provided $x$ is between $x_1$ and $x_2$; it is greater than that otherwise.

The important observation is that, for $n=2$, function $S(x)$ is constant everywhere in the interval $x_{1},x_{2}$. This is important because therein lies the solution to the more general problem.

Indeed, the sum $|x-x_{1}|+|x-x_{n}|$ is constant everywhere in the interval $x_{1},x_{n}$. The sum $|x-x_{2}|+|x-x_{n-1}|$ is constant everywhere in the interval $x_{2},x_{n-1}$. The two sums are constant in the inner interval $x_{2},x_{n-1}$, implying that so is the sum $|x-x_{1}|+|x-x_{2}|+ |x-x_{n-1}|+|x-x_{n}|$.

Now we pass to the next pair of points and find that the sum of 6 distances is constant in the innermost interval; and the process is readily continued. When does it stop? The are two possibilities: either $n=2k$ is even or $n=2k+1$ is odd. For $n=2k$, when we reach the interval $(x_{k},x_{k+1})$ no more points remain. We may claim that the entire sum $S(x)$ is constant in that interval; it achieves its minimum for any point inside it.

If $n=2k+1$, after we consider the pair $x_{k}$ and $x_{k+2}$, there remain an unmatched point $x_{k+1}$. Function $S(x)$ would be constant in the interval $(x_{k},x_{k+2})$ if it were not for the term $|x-x_{k+1}|$. So by choosing $x=x_{k+1}$, we minimize that term and along the way the whole sum $S(x)$.

### A Sample of Optimization Problems III

• Mathematicians Like to Optimize
• Mathematics in Pizzeria
• The Distance to Look Your Best
• Building a Bridge
• Linear Programming
• Distance Between Projections
• Huygens' Problem
• Optimization in a Crooked Trapezoid
• Greatest Difference in Arithmetic Progression
• Area Optimization in Trapezoid
• Minimum under Two Constraints
• Optimization with Many Variables
• Minimum of a Cyclic Sum with Logarithms
• A Problem with a Magical Solution from Secrets in Inequalities
• Leo Giugiuc's Optimization with Constraint