# Connect $n$ white and $n$ black points

$n$ black and $n$ white points are drawn on plane, so that no three of them lay on one line. How to prove that we can connect each white point to some black point by straight segment so that no two segments intersect? Each black point should be connected to exactly one white point.

-
not necessarily by straight lines, correct? – nbubis Feb 6 '13 at 19:50
Can you think of a counter-example where straight lines are not enough, @nbubis? – Thomas Andrews Feb 6 '13 at 19:59
An inductive approach would be to find a line where the number of black and white points on one side of the line is equal. Then you can solve for each side. – Thomas Andrews Feb 6 '13 at 20:04
I think a possible way to go is to show that you can separate your set of n whites and n blacks into a set of k whites and k blacks and one of (n-k) whites and (n-k) blacks (k > 0) by a straight line, and then proceed by induction. – Daniel Robert-Nicoud Feb 6 '13 at 20:05
@DanielRobert-Nicoud Hah, I just wrote exactly the same thing. :) – Thomas Andrews Feb 6 '13 at 20:05

Consider the vertices of the convex hull of the set. If it contains both black and white points, it also contains two consecutive black and white points that we can connect and then proceed by induction on the rest of the set.

So suppose that all the vertices are black. By rotation, we may assume that the $x$-coordinates of the points are all different. Now the left-most point is black and so is the right-most point. If we pick points in order from left to right, and let $w_k$ be the number of white points among the first $k$ points and $b_k$ be the number of black points among the first $k$ points, then $w_1 = 0$, $b_1 = 1$, $b_{n-1} = n-1$ and $w_{n-1} = n$. Thus the difference $b_k - w_{k}$ goes from $1$ to $-1$, and it must be $0$ in between. Thus there exists a separating line, and we can proceed by induction.

-
Where you write "convex hull," you seem to mean the boundary of the convex hull. – Thomas Andrews Feb 6 '13 at 20:20
@Thomas Andrews: Thanks, corrected. – J. J. Feb 6 '13 at 20:22

Use the extremal principle.

Consider all $n!$ the ways that we can connect the white dots to the black dots. Because this is finite, there exists a way which has minimal total length. I claim that this set satisfies the condition. (Note: Assuming that the problem statement is true, This set is a natural candidate to satisfy the conditions.)

Proof: Suppose not, then there is some pair of line segments which intersect at a point $P$. Let the corresponding dots be $W_N, W_M$ and $B_N, B_M$, where $W_NB_N$ are connected and $W_MB_M$ are connected. By the triangle inequality,

$$W_NB_N + W_MB_M \\ = (W_NP + PB_N) + (W_M P + P B_M) \\ = W_NP + PB_M + W_M P + PB_N \\> W_N B_M + W_M B_N$$

The inequality is strict since no three points lie on a line. This contradicts the assumption that the line segments had minimal total length.

-