Tuesday, December 21, 2010

Merry Christmas! (Solution to the Optimization Game)

December 21st! Well, it's winter, and once again America turns its collective thoughts to the Winter Biathlon.

Hah - just kidding.

But I confess I was thinking of the winter biathlon the other day, the reason being that it's an optimization problem of sorts. Winter biathlon is the sport in which an athlete's score depends on speed (cross-country skiing) as well as accuracy (rifle marksmanship). So, just as in other optimization problems, you won't do your best by maximizing over each variable separately. If you ski too fast, your heart rate will spike and your marksmanship will suffer; but skiing too slowly, or taking too much time with your aim, will hurt your skiing time as well. An optimum approach balances competing factors.

The same is true for the optimization game I posted a while back. Recall that in order to play the game, you choose four distinct points on the unit circle. Your score is the area of your quadrilateral, plus the area of the largest triangle that may be formed by deleting one of your points.

Supposing for a moment that you wanted to maximize the area of the quadrilateral, then you would choose four points to form a square, for a score of 3. But this would mean settling for a fairly small triangle (area 1). Alternatively, if you wanted to maximize the area of the triangle, then you would choose three of the points to form an equilateral triangle; but this would mean settling for a fairly small quadrilateral. So, just as in the winter biathlon, the optimum approach requires that we sacrifice a little of the quadrilateral score and a little of the triangle score for the good of the sum.

My own intuitive solution to the area puzzle was as follows. Begin with a square, oriented as a diamond (with points at the four cardinal points North, South, East and West). Given four points in this configuration, the score is 3. Now imagine grabbing hold of the points at East and West, and nudging them both slightly northward. Will the score increase or decrease?

* Because the original square was a maximal-area quadrilateral, when you nudge the two points northward, the area of the quadrilateral will not change, to first order. (We say that the area is "stationary.")

* Meanwhile, the area of the triangle based at the south pole will increase to first order, because the altitude of the triangle will increase to first order, while the base remains unchanged to first order. (The tangent to the circle is vertical at the East and West cardinal points.)

* So altogether, when we nudge the East and West points slightly northward, our score increases, to first order. Hence, this nudging is a good way to improve on the square configuration.

* Of course, if we nudge the points too far toward the north pole, then our score will suffer, because ultimately the score approaches zero as the points reach the north pole. Thus, there is a local optimum configuration, in the shape of a kite, that improves upon the square configuration.

A little geometry, together with some first-semester calculus, suffices to find the optimal shape in this family:

This shape scores about 3.1488, or to be exact

Anyway, this is as much thinking as I did before posting the puzzle. I was confident that the kite was best, but I didn't want to prove it because I hoped it would be at least theoretically possible for someone to beat my score. But I'm afraid that the intuitive solution presented above turns out to be the best. A sketch for a workmanlike proof follows.

In the meantime, Merry Christmas all! Best wishes for a healthy and happy 2011.


Consider any four distinct points on the unit circle. Label the points P,A,B,C as follows: first choose a point so that the remaining three points form a triangle of maximal area in the configuration; label the chosen point B. Then label the points adjacent to B by A and C in such a way that A,B,C are traversed counter-clockwise around the circle. Label the remaining point P. If necessary, rotate the configuration so that P has coordinates (1,0) - here shown at the south pole - understanding the unit circle to be x^2 + y^2 = 1. Then points A,B,C have coordinates given respectively by (cos a, sin a), (cos b, sin b), (cos c, sin c), where 0 < a < b < c < 2 pi:

By construction, triangle PAC is a triangle of maximal area in the configuration, so the score for the configuration can be expressed as twice the area of triangle PAC plus the area of triangle CBA. Using vector cross products, the score can be expressed in terms of a,b,c as

2S = 2 sin(a) - 2 sin(c) - sin(a-c) + sin(c-b) + sin(b-a).

At this point, it is a relatively straightforward exercise in third-semester calculus to show that the optimal configuration, unique up to rigid motions of the circle, is the kite we arrived at by intuition.

No comments: