
Re: Lines in the plane
Posted:
Apr 26, 2001 1:21 PM


In article <3ae8467b.54491158@news.newsguy.com>, Randy Poe <randyp@visionplace.com> wrote: >On 26 Apr 2001 08:54:44 0400, mikeschub2@iol.com (Mike Schubert) >wrote: > >>How it can be proved that for n>=3, n distinct points in the plane, >>not all on a single line, determine at least n distinct lines ? > >Sounds like a natural for induction, with a little twist. Work it out >for n=3. Then try n=4. > >The twist is that for general n, it seems to me you have to take two >different cases: (1) n1 points are colinear, and you are adding one >more, or (2) there are no sets of n1 points which are colinear, in >which case the induction hypothesis holds.
But in case (2) you would like to know that the extra point isn't on any of the existing lines, so that at least one more line is being added. You can ensure this by choosing to take away a point from the set of n which is one of those on a line with only two points on it  which exists by the SylvesterGallai theorem.
For several different proofs of the result, see Chapter 8 of Aigner & Ziegler, "Proofs from THE BOOK" [Springer, ISBN 30540636986]
Chris Thompson Email: cet1 [at] cam.ac.uk

