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 A1, A2, ... , An, and the points of B as B1, B2, ... , Bn so that no two of the n segments AiBi 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 AiBi intersects AjBj at X. Then AiBj < AiX + XBj, AjBi < AjX + XBi. So AiBj + AjBi < AiBi + AjBj. So the labeling was not minimal. Contradiction. Hence no pair of segments can intersect.
© John Scholes
jscholes@kalva.demon.co.uk
4 Dec 1999