Source

I got this problem from Rustan Leino, who was told it by Radu Grigore. Rustan may have heard it 20 years earlier from Jan van de Snepscheut. I modified it slightly.

I solved it and wrote up my solution.

Problem

Given an even number of distinct points on a plane, can you partition the points into pairs and connect the two points of each pair with a single straight line segment such that the line segments don't overlap?

Solution
Reveal

Yes, as follows.

Create a Cartesian coordinate system on the plane so that you can determine Cartesian coordinates $(x, y)$ for each point. Define an ordering $\prec$ on points as follows: $(x_1, y_1) \prec (x_2, y_2)$ if $y_1 < y_2$ or if both $y_1 = y_2$ and $x_1 < x_2.$

Order all the points with $\prec.$ In other words, order them from bottom to top, left to right. Pair up the first two points in that ordering, then the next two, and so on.

The reason this works is as follows. Suppose two of the line segments overlap. Then, there are four points $(x_1, y_1) \prec (x_2, y_2) \prec (x_3, y_3) \prec (x_4, y_4)$ such that the line segment between the first two points overlaps the line segment between the last two points. So, there is some point $q$ that's along both line segments.

Observe that any point $p$ on a line segment between points $p_1$ and $p_2$ must satisfy $p_1 \preceq p \preceq p_2.$ So, we must have $(x_1, y_1) \preceq q \preceq (x_2, y_2) \prec (x_3, y_3) \preceq q \preceq (x_4, y_4),$ whch means that $q \prec q,$ which is impossible. This contradicts our earlier supposition, so we see that no two line segments overlap.