题目
平面上有\(n\)个红点和\(n\)个蓝点，任意三点不共线。证明：存在红点与蓝点之间的一一匹配，使得连接每对匹配点的线段互不相交。
分析
考虑所有\(n!\)种红蓝之间的双射（匹配）。对每一种匹配，计算所有\(n\)条线段的总长度。由于匹配种数有限，必存在一种匹配使得总长度最小。我们断言：总长度最小的匹配中，线段必然两两不交。
用反证法。假设在总长度最小的匹配中存在两条相交的线段\(AB\)和\(CD\)（其中\(A,C\)为红点，\(B,D\)为蓝点），设交点为\(X\)。
在\(\triangle AXC\)中，由三角形不等式：
\[ AC < AX + XC\]
在\(\triangle BXD\)中同理：
\[ BD < BX + XD\]
两式相加：
\[ AC + BD < (AX + XC) + (BX + XD) = (AX + BX) + (CX + DX) = AB + CD\]
这里等号成立是因为\(X\)同时在\(AB\)和\(CD\)上，所以\(AX + BX = AB\)，\(CX + DX = CD\)。
这意味着，若将匹配中的两条边\(AB\)和\(CD\)替换为\(AC\)和\(BD\)，则得到的新匹配的总长度严格小于原匹配，与"总长度最小"的假设矛盾。
因此，总长度最小的匹配中不存在相交线段，命题得证。
参见：问题098「Pairs at Maximum Distance」——该题同样用三角形不等式处理平面线段的相交/不相交问题，两题可互为对照。