Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!princeton!wpt
From: wpt@princeton.UUCP (William Thurston)
Newsgroups: sci.math
Subject: Lines and points in the plane
Message-ID: <2439@princeton.UUCP>
Date: Thu, 6-Nov-86 09:43:58 EST
Article-I.D.: princeto.2439
Posted: Thu Nov  6 09:43:58 1986
Date-Received: Fri, 7-Nov-86 09:22:19 EST
Distribution: net
Organization: Dept. of Computer Science, Princeton University
Lines: 47
Keywords: Sylvester's problem

There is an old problem, first posed by Sylvester in the 1890's and
solved in the late 1940's, concerning lines and points in the plane:

1.	Let F be a finite set of points in the plane, such that every
	line which passes through at least two points of F passes
	through at least three.  Is F contained in a line?

As evidenced by the gap between the date it was posed and the date it
was first solved, it is not as easy as it might first sound.
However, there is a neat simple solution, as we rediscovered at lunch yesterday.
I think lots more people have heard the problem than have heard the solution,
so I'm posting it.  There are some related unsolved problems, which
I'll post later.

The problem has a dual:
	
2.	Let f be a finite set of lines in the plane, such that every
	intersection point of two lines from f is an intersection
	point of three or more.  Show that the lines of f meet in
	a single point.

Problems 1 and 2 are equivalent, by a standard construction:
think of the plane as the plane z=1 in 3-space {(x,y,z)}.  Each line
determines a unique plane through the origin, and each point determines
a line through the origin.  Given the configuration F of points in the
plane, you get a configuration of F' of lines in space.  We may assume
that the z-axis is not in F', by moving the plane z=1 sideways a
bit if necesary.  Let f' be the set of perpendiculars at the origin to
members of F', and let f be the intersections with the plane z=1.
Collinearity for a set of elements of F is equivalent to the corresponding
set of f meeting at a point.

Solution to Problem 2:

Consider the great circles where planes of f' intersects the unit sphere.
These create a subdivision of the sphere into spherical polygons.
If not all elements of f meet in a single point, then the each polygon has
three or more sides. Since at least three lines cross at every vertex,
the number of vertices is not more than 1/6 the number of ends of edges,
or 1/3 the number of edges.  Similarly, if the lines do not all meet at a
single point, then the number of cells is not more than 1/3 the number of
sides of edges, or 2/3 the number of edges.  But this contradicts Euler's
formula for the sphere, which says
	|vertices| - |edges| + |2-dimensional cells| = 2 > 0
(where |vertices| is the number of vertices, etc.)

Bill Thurston		princeton!wpt  Princeton math department.