Maths Olympiad Prep

Library / /66 of 87

Geometry Difficulty 6.8 National Olympiad Prove it Serbia

Problem:

In the plane there are given nn 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
(n1)(n2)10 \left\lfloor\frac{(n-1)(n-2)}{10}\right\rfloor
intersection points (points lying on that line are not counted).

b. For which values of nn 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=(n1)(n2)2 m=\frac{(n-1)(n-2)}{2}
Suppose that, for every line, on one of its sides there are no more than kk intersection points, where kn2k \leqslant \frac{n}{2}. Let us count in two ways the triples (p,A,B)(p, A, B), where AA and BB are intersection points on different sides of the line pp. By the assumption, for each line pp there are no more than k(mk)k(m-k) such triples, so their total number is Nnk(mk)N \leqslant n k(m-k).

Let us now consider two types of such triples:
type 1, when the points AA and BB 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(n4)4\binom{n}{4} 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(n5)5\binom{n}{5}. This can be checked directly: there are six different arrangements of five lines in general position, as in the figure.

Figure 1

Therefore, N4(n4)+5(n5)=n(n4)N \geqslant 4\binom{n}{4}+5\binom{n}{5}=n\binom{n}{4}.
It follows that k(mk)(n4)=m(m1)6k(m-k) \geqslant\binom{n}{4}=\frac{m(m-1)}{6}. From this one obtains
kk0=12(mm2+2m3) k \geqslant k_{0}=\frac{1}{2}\left(m-\sqrt{\frac{m^{2}+2 m}{3}}\right)
Since the inequality k0>m5=(n1)(n2)10k_{0}>\frac{m}{5}=\frac{(n-1)(n-2)}{10} reduces to m>25m>25, which holds for n9n \geqslant 9, while for n=8n=8 we have k0>[m5]=4k_{0}>\left[\frac{m}{5}\right]=4, it remains to examine the cases n7n \leqslant 7.

For n4n \leqslant 4 the statement is trivial, as is the attainment of equality, since then k0=[m5]=0k_{0}=\left[\frac{m}{5}\right]=0. For n=5,6,7n=5,6,7 we have, respectively, k0=[m5]=1,2,3\left\lceil k_{0}\right\rceil=\left[\frac{m}{5}\right]=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.

Figure 2

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.