可以找到 $n$ 条不相交线段，每条线段的端点一红一蓝

hbghlyj

Shmuel Weinberger 著《Computers, rigidity, and moduli. The large-scale fractal geometry of Riemannian moduli space》引言第 5 页
平面上有 $2n$ 个点，其中没有三点共线，$n$ 个点是蓝色，$n$ 个点是红色。
证明：可以找到 $n$ 条不相交线段，每条线段的端点一红一蓝。

abababa

以前做过这个，端点颜色为蓝和白：
将一个白点与一个蓝点相连，只有有限多种连法，使得每条线段的两个端点异色。设所有连法中，使得线段总长度最小的一种为连结$A_iB_i$，其中$A_i$为白点，$B_i$为蓝点。下面证明在这种连法中，任意两条线段彼此不相交：

假设存在相交的线段，不妨设$A_1B_1$和$A_2B_2$相交于$P$，则$PA_1+PB_2>A_1B_2, PA_2+PB_1>A_2B_1$，相加有$(PA_1+PB_2)+(PA_2+PB_1)>A_1B_2+A_2B_1$，即$A_1B_1+A_2B_2>A_1B_2+A_2B_1$，从而只要连结$A_1B_2, A_2B_1$，即得到线段总长度更小的连法，与$A_i,B_i$的取法矛盾。因此这种连法中不存在相交的线段。

hbghlyj