Thursday, April 01, 2004

Erdos and proofs 'from the Book' (cont..)

Yesterday I talked about Erdos's beautiful idea of proofs from the Book, and mentioned an example problem whose proof could be viewed as being a 'Book proof'.
Here is the proof, (due to L. M. Kelly)

Theorem. There is no way to arrange n points in the plane (not on a line) so that a line through any two points will always pass through a third.

Suppose the theorem is false. Let P be the given set of points, and let L be the set of all lines that pass through at least two points of P. Over all pairs (p, l) where p is in P and l is in L, and p does not lie on l, pick the pair (pp, ll) such that the distance from pp to ll is the smallest. By assumption, all lines pass thru at least three points, and so there are three points on ll, two of which (call them q1, q2) must lie on one side of the perpendicular from pp to ll.

Say q1 is closer to the perpendicular and q2 is further. Consider the pair (q1, lll), where lll is the line joining pp and q2. A simple drawing shows that q1 is closer to lll than pp is to ll, contradicting the minimality of the pair (pp,ll). Hence the theorem is proved.
end proof.

Bonus Points
You might notice that the above proof uses metric properties of the Euclidean plane (i.e the notion of distance), and order axioms (the notion of betweenness). It is possible to prove the above result without using metric properties (merely using order axioms), but it is not possible to drop the order axioms themselves. The reason is a topic for another note, on the limitations of combinatorics in geometry. Stay tuned....

No comments:

Post a Comment

Disqus for The Geomblog