If a finite set of n>2 points in the plane are not all on one line, then prove that there exists a line through exactly two of the points.

Its seems to me that a recursive argument should work.

I will use the word "lines" to mean "lines through exactly two points"

It clearly works for three points - there are three lines. 

For four points there are two possibilities:

• no points collinear - 6 lines
• one set of three collinear - 3 lines

For five points there seem to be four possibilities:

• no points collinear - 10 lines
• one set of three collinear - 7 lines
• two sets of three collinear - 4 lines
• one set of 4 collinear - 4 lines

It appears at first that we are guaranteed at least n-1 lines for n points and this minimum occurs when all but one of them are collinear.

But then I found a counterexample with 7 points and only 3 lines:
3 points form a equilateral triangle, 3 more at the midpoints, and 1 at the center.

Posted by Jer on 2011-03-27 23:56:40