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.

Need another hint? Click here.

Click here for the complete solution.