Problem 6

6. Suppose your worst enemy gives you $n$ red points and $n$ blue points in the plane, no three of them collinear. (Your enemy picked them, so they are not nicely arranged.) Show that it is possible to draw $n$ line segments, each segment joining a red point to a blue point (so that each red point is paired with a unique blue point, and vice versa) in such a way that none of the line segments intersect.

Commentary: This one was quite a labor from beginning to end. At first I put it on the back burners, because I thought it would perhaps be a simple case of induction or intuitive resolution. However, I quickly became lost in my clear conception of why it would hold, and I didn't even want to think about how I'd go about explaining even semi-formally a solution.

I tried to get at it by simple induction for a really long time, trying to force the minimal $n$ counterexample to be as unlikely as possible. I did eventually settle on something; casually explained, if you take a ruler and pull it up from a region of the plane below all of the points and let it catch on a lowest point, then drag it clockwise until it catches another, and so forth until arriving at the original point, it can be reasoned that all of these points caught are of the same color, otherwise one could draw a line between two of these border points and finish the other $n-1$ points by induction without worrying about it interfering with the first line drawn. Essentially, this would mean all the points are trapped in a polygon defined by certain points of the same color.

This result would ultimately pan out to be useless, because of where it guided me: I ended up realizing a situation that implied it might very well be that "naive" induction (a proof of the form, "locate a certain pair of points, draw a line, and finish the rest by induction" as applied above) isn't enough to resolve the problem. This was because of the existence of the diagram below, where every possible green line might be intersected by another green line drawn:

(It being so sloppy because I only realized the significant proportions are those of "shrunken center pentagon" after having drawn it all out)

Long story short I had to make a fresh start. After some more contemplation, later that night I had a sleepy thought that "crosses represent inefficiencies in segment lengths," and after entertaining it for some while I settled on the solution below.

Proof: Lemma: In a quadrilateral where the diagonals intersect, the sum length of these two diagonals exceed the sum length of any two opposite sides. Proof:

When $E$ represents the intersection, it results from basic linear algebra $|u+v| < |u|+|v|$ (when $u$ and $v$ are nonassociate to each other as here) implying $$|\overline{AC}|+|\overline{BD}|=|\overline{AE}|+|\overline{EC}|+|\overline{BE}|+|\overline{ED}| > |\overline{AB}|+|\overline{CD}|$$and similarly for the the other pair of sides.$~\square$

For each possible graph $P$ of line pairings that can be drawn (not necessarily without intersections), let $N(P)$ be the sum of the lengths of every line segment in $P$. Since there are a finite number $n!$ of such graphs, let $L$ be minimal with regard to this norm. Then $L$ has no intersections; otherwise assume $\overline{AB}$ and $\overline{CD}$ intersect. Then let $L'$ be the graph with every other line segment the same as in $L$, but with instead the segments $\overline{AD}$ and $\overline{CB}$. By the lemma applied to the quadrilateral $ADCB$, we thus see $N(L') < N(L)$, violating the minimality of $L$.$~\square$

Since there are only a finite number of graphs, this provides a constructive method of obtaining a nonintersecting line pairing by taking any random graph and successively decreasing its norm until no intersections may remain.