Prove that if $2n$ points are colored red or blue, then we can always connect the red points to the blue points with non-intersecting line segments.

Question

Take any set of 2n points in the plane with no three collinear, and then arbitrarily color each point red or blue. Prove that it is always possible to pair up the red points with the blue points by drawing line segments connecting them so that no two of the line segments intersect.

This problem is provided in Richard A. Brauldi's book on Introductory Combinatorics. I believe it is implied that the number of red points is equal to the number of blue points. I tried to reason as follows: it seems like it's always possible to divide the plane into two regions, such that each region contains an equal number of red and blue points. Further, subdivide those regions into subregions with equal numbers of red and blue points; and continue the process until all the regions contain exactly one red and one blue point. Then we can simply connect the two points of every region with a line; and since all pairs lie in distinct regions, it seems obvious that no lines will intersect.

However, I don't know how exactly to prove this. That is, how do I gaurantee that it is in fact possible to divide any region of red and blue points into subregions of equal numbers of red and blue points? Or how would the problem be approached by a more professional. Thank you in advance.

Answer 1

Suppose there are $2n$ points in the plane, where $n$ of them are blue and $n$ of them are red. Arbitrarily match up the pairs of blue points and red points by drawing a line between them. So, you will end up drawing $n$ line segments, where one end is blue and the other end is red.

Of course, some lines may intersect since our initial pairing was arbitrary. Show that if two lines intersect (i.e. you have an X shape), then you can modify the pairing so that they don't intersect, which will result in the total sum of the distances between the line segments becoming smaller. Now, repeat this process until there is no crossings (this process must end because the total sum of the line segments joining blue and red points cannot be arbitrarily small).

Answer 2

For any pairing $P$ of the red and blue dots, let $s(P)$ denote the sum of all line segments in the pairing. Let $C$ be the set of all sums $s(P)$ as $P$ varies over all possible pairings of the line segments. Since $C$ is finite and nonempty, $C$ has a least element $\alpha$. Then there exists a pairing $P_0$ for which $s(P_0) = \alpha$. Then there cannot be any crossing of segments in $P_0$, otherwise we can take any pair of crossing segments and redraw them without crossing which results in a smaller total sum for the resulting pairing. (The crucial fact used here is that the sum of two sides of a triangle is greater than the third side.) Then $P_0$ is the desired pairing.

Note that the sum of a pairing is always non-negative, so by well ordering principle their always exists a pairing with minimum cost.

Answer 3

To prove your claim of

Given an equal number of red and blue points, we can divide the plane into two regions, such that each region contains an equal number of red and blue points.

• As you realized, we can approach this by (strong) induction.
• So let's consider the case of $ n$ red points and $n$ blue points.
• Pick a dot D that is not collinear with 2 other red/blue points (IE Draw up all lines of 2 points, and pick D that isn't on any of these lines) , and in the convex hull of the points.
• Draw a line through D, and count the number of red - the number of blue points on the region to it's left. Say this value is $N$.
• Consider what happens as we rotate this line. In particular, show that the count changes by +1 or -1 if and only if we "sweep" across a point.
• Consider what happens as we rotate this line by $180^\circ$. In particular, the difference is now $-N$.
• Conclude that as we rotate the line, there will be a position when the difference is exactly 0. This is when the number of red/blue dots to the left are equal, and hence the number of red/blue dots to the right are equal.
• In order to actually apply induction, we do need the the number of dots to the right and left to be non-zero. How can we ensure this?