A and B are disjoint sets of n points in the plane. No three points of A ∪ B are collinear. Can we always label the points of A as A_{1}, A_{2}, ... , A_{n}, and the points of B as B_{1}, B_{2}, ... , B_{n} so that no two of the n segments A_{i}B_{i} intersect?

**Solution**

Answer: yes.

*Hard.*

It is easy to waste a lot of time failing to find inductive arguments (can we find a line with the same number of A-points and B-points on one side of it etc).

The trick is to find another property which cannot be satisfied if two segments intersect. Take the labeling which minimises the total length of the segments (obviously exists, since there are only finitely many labelings). If A_{i}B_{i} intersects A_{j}B_{j} at X. Then A_{i}B_{j} < A_{i}X + XB_{j}, A_{j}B_{i} < A_{j}X + XB_{i}. So A_{i}B_{j} + A_{j}B_{i} < A_{i}B_{i} + A_{j}B_{j}. So the labeling was not minimal. Contradiction. Hence no pair of segments can intersect.

© John Scholes

jscholes@kalva.demon.co.uk

4 Dec 1999