From: rld@math.ohio-state.edu (Randall Dougherty) Date: 6 Jun 1996 23:22:35 -0400 Newsgroups: sci.math Subject: Re: Question from the classroom: Geometry
In article <steiner-0406961355200001@steiner.bgsu.edu>, Ray Steiner <steiner@math.bgsu.edu> wrote: >Greetings all, > I am teaching a course of mathematics for elementary teachers >and a problem in the text recently asked about some of the possible number >of distinct points in which 4,5,6,7,8 distinct lines could meet. >I extended it a bit farther and we found the following results: >For 4 distinct lines we could get 1,3,4,5 or 6 possible distinct points >For 5, we could get all integers from 4 to 10. >For 6, we could get all integers from 5 to 15. >This led to the following questions: >We know that n distinct lines can meet in at most n(n-1)/2 distinct >points. For which n can we get all the integers from n-1 to n(n-1)/2 >as possible numbers of distinct points of intersection? >How would one attack this problem for general n? This pattern does not continue forever -- for large n, there is no configuration of n lines which gives exactly n+1 intersection points. (I think that this is so for all n > 10, but I have no proof of this stronger statement.) Here is a sketch of the proof; the full proof would be rather long. Suppose we have a configuration of n lines giving n+1 intersection points. What is the largest number of lines in the configuration which are concurrent or parallel? These two cases will come up so often that it will be easier to move to the projective plane, where there is no distinction between them. Of course, this has a cost; instead of just counting intersection points, we have to count the points and then see how many can be removed by arranging to have them lie on the "line at infinity" when converting back to the ordinary plane. Note the restriction that the line at infinity cannot be one of the n lines of the configuration. If all n lines are concurrent, we only get 1 projective intersection point, which may be a finite point or a point on the line at infinity, giving 0 or 1 ordinary intersection points. If n-1 of them meet at one point but the n'th doesn't, then we get n-1 additional points from the n'th line, for a total of n; this gives either n-1 or n finite points. If the largest number of lines at a point is n-2, then the (n-1)'th line gives n-2 additional points, of which one may be infinite, and the n'th line also meets the first n-2 in n-2 points, of which one may be infinite and one may lie on the (n-1)'th line, leaving at least n-4 new finite points. Therefore, there are at least (n-3)+(n-4) = 2n-7 finite points, which is too many. Similarly, if the largest number of lines at a point is n-3, then we get at least (n-4)+(n-5)+(n-6) = 3n-15 finite intersection points. Continuing this downward, we see that, as long as k is large enough that (k-1)(k-2)/2 > n+1, we will get too many finite intersection points if there are k lines meeting at a point. So, in the desired configuration, the largest number of lines through a particular point is at most about sqrt(2n). Next, consider the case where two different points each have at least d lines passing through them. One of these lines might pass through both points, but this still leaves d-1 other lines at each point, which produce (d-1)^2 intersection points. Since at most one of the points on each of the first d-1 lines can be on the line at infinity, we get at least (d-1)(d-2) finite intersection points. Therefore, in the desired configuration, the point with the second-largest number of lines through it has at most about sqrt(n) such lines. If one considers three points which each have at least d lines through them, then, with a substantial amount of extra work, one can show that there must be at least 3d^2/2 - 6d + 3 finite intersection points. (This bound isn't quite sharp, but the leading term is.) Therefore, in the desired configuration, every point with at most two exceptions lies on at most D lines, where D is about sqrt(2n/3). Now, the n lines give n(n-1)/2 pairs of lines, and each such pair has an intersection point (finite or infinite). A point at which d lines meet takes care of d(d-1)/2 of these pairs. There are only n+1 finite intersection points, and these can take care of about (n+1)D(D-1)/2 ~ n^2/3 pairs. (The two possible exceptionally large intersection points would only yield about 5n/3 additional pairs.) How about points on the line at infinity? The sum of the degrees (number of lines meeting there) of these points is at most n, because each configuration line meets the line at infinity only once. And we still have the bound D on the individual degrees. So a simple optimization argument shows that the number of pairs with intersection point on the line at infinity is at most about (n/D)D(D-1)/2 ~ n^(3/2)/sqrt(6). (Again the two exceptional points only change this bound by O(n).) Therefore, the total number of pairs of lines in the configuration is n^2/3 + o(n^2); since this is less than n(n-1)/2 for large n, we have a contradiction. This completes the sketch of proof that no configuration of n lines gives n+1 intersection points if n is large. Actually, the argument shows that no configuration of n lines gives between n+1 and cn intersection points, where c tends to 3/2 for large n. I conjecture that, in fact, for large n, the first attainable number of intersection points after 0, 1, n-1, and n is 2n-6. Randall Dougherty rld@math.ohio-state.edu Department of Mathematics, Ohio State University, Columbus, OH 43210 USA "I have yet to see any problem, however complicated, that when looked at in the right way didn't become still more complicated." Poul Anderson, "Call Me Joe"
From: kjellpe@math.uio.no (Kjell Fredrik Rogstad Pettersen) Newsgroups: sci.math Subject: Re: Question from the classroom: Geometry Date: 7 Jun 1996 07:17:43 GMT Organization: University of Oslo, Norway
[Ray Steiner] > Of course,they can never meet! Again, I want to know if all numbers > of intersection points are possible between n-1 and n(n-1)/2 if > n>3. For example, 5 lines certainly can meet in 0 or 1 point. > But they can also have 4,5,6,7,8,9 or 10 distinct intersection points. > I'm not asking about all possible numbers of intersection points. > I just want to know if all numbers between n-1 and n(n-1)/2 > are POSSIBLE. > Thanks > Ray Steiner I've been looking at this a little bit. It is true for n=3,4,5,6,7,8,9 while it seems as if it is impossible for 10 lines to meet in 11 or in 12 points (but they may meet in 9,10,13,..,45 points). In general, I don't believe it is possible for n lines to meet in n+1 points for n>10. (Which seems simple to proove by induction if it is prooved for n=10). Kjell Fredrik Pettersen
From: Jeff Erickson <jeffe@cs.berkeley.edu> Date: Sun, 16 Jun 1996 18:45:26 -0700 Newsgroups: sci.math Subject: Re: Question from the classroom: Geometry
Jerry Grossman wrote: > Ray Steiner wants to know if all numbers of intersection points are possible > between n-1 and n(n-1)/2 if n>3 lines are arranged (in a plane or more > generally?). I think Erdos (or somebody else with Erdos number less than two) showed that (n(n-1)/2) - 1 is impossible. Some more information about this problem, at least for small n, can be found in Grunbaum's classic treatise on convex polytopes. According to the bibliography of Ziegler's "Lecture Notes on Polytopes", a new edition is in the works. Another relevant source is Grunbaum's monograph "Arrangements and Spreads". > ...a friend of mine showed that you can't get 8 lines from 7 points... A proof of this can be found in Grunbaum. -- Jeff Erickson jeffe@cs.berkeley.edu http://www.cs.berkeley.edu/~jeffe