If I have an even number $n$ of points in a plane (no $3$ of them colinear), half of them red and half of them blue, is there always a way to draw $\frac{n}{2}$ lines to join each red with a blue and each blue with a red in such a way that none of the lines between them intersect?
This was extra credit on an exam and I have no clue where to start. We've done exercises where we counted the number of ways to join red and blue points on a circle, but never something like this. How can I prove/disprove this claim?
Choose a point $P$ in the plane which is in the convex hull of the given points, but is not on any of the (finitely many) lines determined by the given points. Draw a line through $P$ which does not contain any given point. Consider $S$, one of the half planes determined by the line. Let $r(S)$ and $b(S)$ be the number of red and blue points in $S$ and suppose $r(S)-b(S)=m$.
Now rotate $S$ about $P$. Note that $S$ will always contain some, but never all, of the given points. When $S$ has been rotated by $180^{\rm o}$ it will contain precisely the points it didn't contain initially, so we have $r(S)-b(S)=-m$. But $r(S)-b(S)$ can only change by one unit at a time as $S$ rotates, so there must be a specific half plane $S_0$ for which $r(S_0)=b(S_0)$.
Now by induction we may assume that the points in $S_0$ may be connected as desired; also the points not in $S_0$; and lines in the two halves cannot intersect; so we are done.