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.

Need another hint? Click here.

Click here for the complete solution.