In the plane there are given n lines, no two of which are parallel and no three of which meet at one point. By intersection points we mean all the points at which some two of these lines meet.
a. Prove that among the given lines there exists one such that on each side of it there are at least ⌊10(n−1)(n−2)⌋ intersection points (points lying on that line are not counted).
b. For which values of n can the estimate from part (a) not be improved?
Solution
Solution:
For each of the given lines, the number of intersection points lying off it is m=2(n−1)(n−2) Suppose that, for every line, on one of its sides there are no more than k intersection points, where k⩽2n. Let us count in two ways the triples (p,A,B), where A and B are intersection points on different sides of the line p. By the assumption, for each line p there are no more than k(m−k) such triples, so their total number is N⩽nk(m−k).
Let us now consider two types of such triples: type 1, when the points A and B lie on the same one of the given lines, and type 2, when they do not. Every quadruple of given lines, together with the intersection points they determine, determines exactly 4 triples of type 1, and every triple is determined by exactly one quadruple of lines. It follows that there are 4(4n) triples of type 1. Also, every quintuple of given lines together with the intersection points they determine, determines at least 5 triples of type 2, so the number of triples of type 2 is at least 5(5n). This can be checked directly: there are six different arrangements of five lines in general position, as in the figure.
Therefore, N⩾4(4n)+5(5n)=n(4n). It follows that k(m−k)⩾(4n)=6m(m−1). From this one obtains k⩾k0=21(m−3m2+2m) Since the inequality k0>5m=10(n−1)(n−2) reduces to m>25, which holds for n⩾9, while for n=8 we have k0>[5m]=4, it remains to examine the cases n⩽7.
For n⩽4 the statement is trivial, as is the attainment of equality, since then k0=[5m]=0. For n=5,6,7 we have, respectively, ⌈k0⌉=[5m]=1,2,3, so the statement of the problem holds in these cases as well, and equality is also attained in the cases shown in the figure.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement translated into English from sr; metadata (topic, difficulty) added by this project.