Some 2n points in the plane are chosen so that no three are collinear, and then half are colored red and half blue.

Will it always be possible to connect every red point with a blue one so that none of the connecting lines intersect?

Please justify your answer.

It is possible. If two lines b1-r1 and b2-r2 cross, just wipe them out and replace them by b1-r2 and b2-r1. It is easy to see that this reduces the total length of all lines segments (draw diagram and use triangle inequality). Since the total length cannot shrink forever, this process leads to a connection without any crossings.

Posted by JLo on 2020-01-22 12:49:31