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

|Contact| |Front page| |Contents| |Geometry|

Copyright © 1996-2017 Alexander Bogomolny

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)\).

Related material
Read more...

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
  • Problem 4033 from Crux Mathematicorum
  • An Unusual Problem by Leo Giugiuc
  • A Cyclic Inequality With Constraint in Two Triples of Variables
  • Two Problems by Kunihiko Chikaya
  • |Contact| |Front page| |Contents| |Geometry|

    Copyright © 1996-2017 Alexander Bogomolny

     62679722

    Search by google: