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.

Assume the contrary.        
1. Since a line can always be drawn across any two points, there can be no 'singleton point'        
2. It follows at once that every point in the plane is collinear with at least two others, or to put it another way,(since a line can always be drawn across any two points) that every set of 3 points in the plane is collinear.
        
3. Since this must apply to every pair of lines, we may assume WLOG

(a) two such lines, ABC and DEF, that have no point in common.        
But then two-point lines (tpl) can be drawn between each of {A,B,C} and {D,E,F}; now assume
(b) that ABC and DEF have one point in common, say A=D        
But still tpls can be drawn between each of {B,C} and {E,F};now assume
(c) that ABC and DEF have two points in common, say A=D, B=E: then all the points are collinear.
       
4. So  any given pair of lines either is collinear, or has at least 4 tpls.
       
5. The only way this 'score' can be improved is to have say A=D, AND place a 6th point, say G, at the intersection of BF and CE giving a 'score' of 6 points with 2 tpls {CF,AG}. But now the next point can be added without (e.g. H on the crossing of AG and CF) without creating at least 2 new tpls {BH,EH}

6. Note that we now have a 3-line system in the form of triangle ACF with line AGH running through it. All subsequent points must either
(i) be inside, or
(ii) be outside, or
(iii) on
this triangle.
      
If the point is outside the triangle, or inside the triangle but not on an existing intersection, then it can be on ony one line, for the creation of (n-3) tpls per point. This rate increases much more quickly than our ability to create new 3-point lines.

If the point is inside the triangle, AND on an intersection of 2 tpls (which as noted above is the best we can do) then it also creates 2 new tpls for no net gain. But at the same time it also creates a new point, so that the next point so placed will create 3 tpls, and the third will create 4 tpls, again increasing much more rapidly than our ability to create new 3-point lines. Call such points 'inside points'

Thw last possibility is to place a point on a side of the triangle. Any such point forms a 2-point line with (a) one original vertex, and (b) at least 1 inside point (c) two original side points, and (d) every other side point which is not either (i) on the same side or (ii) collinear with an existing line between 2 inside points or (iii) collinear with another side point and an inside point. So the best possible placement of a side point creates (1+1+2)=4 tpls (since we already know that G is an optimal placement). So placing a point on a side is not as 'good' as placing it as an inside point.

So any placement after the 6th point either (i) increases the total number of tpls by 2, or (ii) (since the points can be placed in any order) cannot reduce the total number of tpls below 2.

Edited on March 28, 2011, 3:26 am

Posted by broll on 2011-03-28 03:07:28