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 1

What happens to the total distance if you shift your chair a little to the left or a little to the right?

Drawing of Round Table and Nasties

Hint 2

It makes a difference where the Nasties are seated relative to your centerline. Divide the problem into several cases.

Drawing of Round Table and Nasties with centerline

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.

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:

all Nasties on left

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.

two Nasties on left, one on the right

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.

one Nasty opposite you

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