No crossing!
On the 2D plane there are \(n\) blue and \(n\) red points, no three of them are co-linear. Then we can always pair a blue point with a red one and draw \(n\) segments between them, one from each pair, such that no two segments cross with each other.
My proof:
Induction is handy here. If the convex hull has points of both colors, we could isolate a red and an adjacent blue one with the rest, and induction will work. Otherwise, say all points on the convex hull are red and we shoot rays from a fixed red points \(u\) on the convex hull. Each ray divides other \(2n-1\) points into two groups, and we count the number of blue points minus the number of red points in each group. At some point these two numbers are \((-1,2)\) and at the other \((2,-1)\). Then one of the rays has one of the numbers \(0\), and the induction will work again.
Another proof:
When there is intersection, we can always replace the two intersecting segments by another two that don't intersect and reduce the total lengths of segment. The process cannot go on infinitely because the total length is bounded from below. Therefore there will be a time when we could not do this replacement anymore, i.e. no segment intersect with another.
My proof:
Induction is handy here. If the convex hull has points of both colors, we could isolate a red and an adjacent blue one with the rest, and induction will work. Otherwise, say all points on the convex hull are red and we shoot rays from a fixed red points \(u\) on the convex hull. Each ray divides other \(2n-1\) points into two groups, and we count the number of blue points minus the number of red points in each group. At some point these two numbers are \((-1,2)\) and at the other \((2,-1)\). Then one of the rays has one of the numbers \(0\), and the induction will work again.
Another proof:
When there is intersection, we can always replace the two intersecting segments by another two that don't intersect and reduce the total lengths of segment. The process cannot go on infinitely because the total length is bounded from below. Therefore there will be a time when we could not do this replacement anymore, i.e. no segment intersect with another.
post by Shen-Fu Tsai