HOME

Sylvester’s theorem used (see EWD1016)

Show original manuscript

Sylvester’s theorem used (see EWD1016)

On Tuesday 2 January 1996, Ronald W. Bulterman told me the following theorem.

Consider, for n ≥ 2, n distinct points in the plane; let k be the number of all distinct lines such that each of them contains at least 2 of those points. Then   k = 1  kn   .

*         *         *

Proof   The proof is by mathematical induction on n. There are two reasons for trying this proof structure, firstly the shape of the disjunct k ≥ n in the demonstrandum and secondly the fact that (Euclid’s Axiom)   n = 2  k = 1   immediately establishes the base.

With   nʹ = n +1, we consider for the induction step nʹ distinct points, giving rise to   lines. We have to show   = 1   ≥ nʹ, where we may use k = 1 kn “ex hypothese”. In view of our demonstrandum being a disjunction, we introduce a case analysis, viz. =1 versus ≠1.

= 1

In this case, the demonstrandum   = 1  nʹ   follows directly (i.e. by predicate calculus alone).

≠ 1

In this case, the demonstrandum   = 1  nʹ   simplifies directly to nʹ. The remainder of the proof is devoted to showing how, for nʹ noncollinear points, n follows from the induction hypothesis.

In order to be able to appeal to the induction hypothesis, we single out one of the nʹ points —let us call that point “A”— and consider the remaining n points and the k lines they give rise to all by themselves. Ex hypothese we may use k = 1 kn; we exploit the two disjuncts separately.

In the case k = 1, the n (distinct) points lie on a single line, and, because the nʹ points are noncollinear, that line does not contain A. Hence = n + 1, and since nʹ = n + 1, nʹ has been established.

In the remaining case kn —or, since nʹ = n + 1, equivalently k + 1 ≥ nʹ — , our demonstrandum nʹ follows from k + 1 or, equivalently,   > k. How do we establish   > k? Or, in other words, how can we conclude that the removal of A reduces the number of lines? Well, since a line has to go through at least 2 points of the set, such a line disappears if A is one of the only 2 points it goes through. Hence we can assert  > k by a proper choice of A provided:

“For any number of distinct, noncollinear points in the plane, there exists a line through exactly 2 of them.”

But this was Sylvester’s conjecture, which since then became a theorem, so we are done.

(End of Proof.)

Austin, 13 January 1996

 

prof.dr. Edsger W.Dijkstra
Department of Computer Sciences
The University of Texas at Austin
Austin, TX 78712–1188
USA