6
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you! By "lines determined by the given points", do you mean drawing a line through every pair of points, or the connections in the problem? $\endgroup$ – NMister Mar 20 '18 at 11:15
  • $\begingroup$ I also don't understand how we can say "by induction we may assume that the points in $S_0$ may be connected as desired". Isn't it just as hard of a problem to connect that half set? Or are we doing some sort of infinite regress thing where you then apply the proof to that half plane? $\endgroup$ – NMister Mar 20 '18 at 11:18
  • $\begingroup$ "Lines determined by the given points" means through every pair of points. For induction see here. $\endgroup$ – David Mar 20 '18 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.