Show that given any finite set of points P₁, P₁, ..., P_n in the plane (with n>1), either all the points lie on the same line, or there is a pair P_i, P_j such that the line through P_i and P_j meets no other point of the set.

This problem seems intuitively obvious and you probably think it's easy to solve, but....

Hint 1

If you work out some examples, you will see that there are many lines that contain only two points, but how can you prove in general that there is at least one? In a sense we have an "embarrassment of riches," with many more lines than we actually need. Think of some way to distinguish one of the two-point lines (some unique property that it has) and then prove that conversely any line with this special property is a two-point line.

Hint 2

Let S be the set of lines that go through at least two of the given points. Then the set S is finite. Consider the set of pairs (L, P_i), where L is in S, and P_i is one of the given points that does not lie on L. There are only finitely many such pairs. Choose one such pair for which the distance between L and P_i is as small as possible. Then L is our "distinguished" line; show that L cannot contain more than two points.

Hint 3

See the figure. We can renumber the points if needed such that P₁ is the point nearest to L. Write Q for the point on L closest to P₁. Suppose L does not have the desired property, and so there are at least three points on L. Then at least two of them are on the same side of Q. We can renumber these two points if needed so they are P₂ and P₃ (note that P₂ might coincide with Q). Then draw the line through P₁ and P₃. Show that P₂ is nearer to the new line than P₁ is to L, which contradicts the choice of P₁ and L.

The Rest of the Solution

See the figure. We have that P₂B is shorter than P₂A because the former is one side and the latter is the hypotenuse of a right triangle. We have that P₂A either coincides with QP₁ or is shorter than it because they are corresponding sides of the similar triangles P₃P₂A and P₃QP₁.

construction showing L is not the nearest line

References

Our solution comes from the book Proofs from the Book, 2nd edition, by Martin Aigner and Günter M. Ziegler, Springer-Verlag, 2001. This result is known as the Sylvester-Gallai theorem; our proof is due to L. M. Kelly and comes from Chapter 8 of the book. There is a completely different proof in Chapter 10, based on Euler's formula for polyhedra.