You arrive for a meeting and have to sit at a large round table at which
three people you violently dislike are already seated. Where should you
place your chair so that, when you add up the shortest distances round the
edge of the table from yourself to each of these "nasties", the total
distance you get is as large as possible? (Of course since the nasties are
already seated you have no control over their location.)
Hint 3
In this drawing, the total of the distances to N1 and N3 does not
change when you shift
your chair. If you move a little to the left, you are a little closer to
N1 but the same amount farther from N3, so these changes cancel out.
If you shift a little to the right, you are a little closer to N3 but
the same amount farther from N1, so these changes also cancel out. The
only distance that makes a difference is the distance to N2.
Assuming that you don't shift past N1 or N3, what is the best position
for you to sit in?
Hint 4
The best position is directly opposite N2. Remember that we measure the
shortest distance around the table, so if you move a little to the left
you are getting closer to N2 (because you are measuring along the left),
and similarly if you move a little to the right you also get closer to N2.
Therefore the best position is exactly in the middle, regardless of where
N1 and N3 are.
Click here for rest of the solution.
The Rest of the Solution
In the general problem there are three cases according to how many
Nasties are on each side of your centerline:
If all Nasties are on one side of the centerline, then by moving a little to
the other side we increase the total distance. Therefore we have not
reached the optimum point yet.
If two Nasties are on one side, then by moving a little to the other side we increase the
total distance, because if we move one "unit" then we add two units of
distance from those on the left and lose only one unit from the one
on the right. We are not at the optimum yet.
If one Nasty is directly opposite you, then small movements to either
side decrease the total distance, because they move you nearer the opposite
Nasty; although you are moving farther from one of the side Nasties, you
are moving an equal distance nearer the other side Nasty, so these changes
cancel and only the distance to the opposite Nasty matters.
Therefore you might be at an optimum (you know that you are
at least at a "local maximum" for distance, because any change decreases
the distance).
Conclusion:
Only positions directly opposite a Nasty can be optimal. Since
there are a finite number (namely three) of such positions, you can tell by
comparing the three distances which is the true optimum ("global maximum").
Variational Principles
Nearly all kinds of optimization problems depend on considering a small
variation in the current condition, such as the one we used here of
sliding the chair a little to one side or the other. If you know calculus
you probably remember the check for a local minimum or maximum:
look for points where
f'(x)=0.
This is just a formula expressing
the variational principle: if the derivative is not zero, then by
shifting a little to the left or right you can get a bigger or smaller
value for the function.
There's a whole branch of mathematics called the Calculus of Variations
that exploits this very principle to find optimums; it deals specifically
with quantities that are defined by integrals, for example,
areas of plane figures and lengths of curves.
The Simplex method in linear programming also uses a variational principle.
We know from the geometry of the problems that the optimum will occur
at a vertex of the permissible set, and the Simplex tableau is a systematic
method for examining other nearby vertices to see if one produces a better
result.
References
- Donald A. Pierre,
Optimization Theory With Applications,
Dover reprint, 1986.
- Click
here to view the original problem submitted by Al.
