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.)
References
- P. J. Nahin, When Least Is Best, Princeton University Press, 2004
|Contact| |Front page| |Contents| |Geometry|
Copyright © 1996-2018 Alexander BogomolnyMinimize 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)\).
|Contact| |Front page| |Contents| |Geometry|
Copyright © 1996-2018 Alexander Bogomolny71547270