Drawing the Line

Show that given any finite set of points P_1, P_2, ..., 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....

Need a hint? Click here.

Click here for the complete solution.

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_1 is the point nearest to L. Write Q for the point on L closest to P_1. 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_2 and P_3 (note that P_2 might coincide with Q). Then draw the line through P_1 and P_3. Show that P_2 is nearer to the new line than P_1 is to L, which contradicts the choice of P_1 and L.

The Rest of the Solution

See the figure. We have that P_2B is shorter than P_2A because the former is one side and the latter is the hypotenuse of a right triangle. We have that P_2A either coincides with QP_1 or is shorter than it because they are corresponding sides of the similar triangles P_3P_2A and P_3QP_1.

References

• Martin Aigner and Günter M. Ziegler, Proofs From The Book , 4th edition, Springer-Verlag, 2010. Chapter 10, "Lines in the plane and decompositions of graphs" (pp. 63-67). This is the source of our proof, which is by L. M. Kelly. This result is known as the Sylvester-Gallai theorem. There is a completely different proof in Chapter 12, "The applications of Euler's formula" (for polyhedra), pp. 75-80.
• See also the Wikipedia article Sylvester-Gallai theorem.