Maths Olympiad Prep

Library / /16 of 121

Geometry Difficulty 5.3 AIME, harder Prove it India

Problem:

Do there exist 100 lines in the plane, no three of them concurrent, such that they intersect exactly in 2002 points?

Solution

Solution:

Any set of 100 lines in the plane can be partitioned into a finite number of disjoint sets, say A1,A2,A3,,AkA_{1}, A_{2}, A_{3}, \ldots, A_{k}, such that

(i) Any two lines in each AjA_{j} are parallel to each other, for 1jk1 \leq j \leq k (provided, of course, Aj2|A_{j}| \geq 2);

(ii) for jlj \neq l, the lines in AjA_{j} and AlA_{l} are not parallel.

If Aj=mj|A_{j}| = m_{j}, 1jk1 \leq j \leq k, then the total number of points of intersection is given by 1j<lkmjml\sum_{1 \leq j < l \leq k} m_{j} m_{l}, as no three lines are concurrent. Thus we have to find positive integers m1,m2,,mkm_{1}, m_{2}, \ldots, m_{k} such that

j=1kmj=100,1j<lkmjml=2002 \sum_{j=1}^{k} m_{j} = 100, \quad \sum_{1 \leq j < l \leq k} m_{j} m_{l} = 2002

for an affirmative answer to the given question.

We observe that

j=1kmj2=(j=1kmj)22(1j<lkmjml)=10022(2002)=5996 \begin{aligned} \sum_{j=1}^{k} m_{j}^{2} &= \left(\sum_{j=1}^{k} m_{j}\right)^{2} - 2\left(\sum_{1 \leq j < l \leq k} m_{j} m_{l}\right) \\ &= 100^{2} - 2(2002) = 5996 \end{aligned}

Thus we have to choose m1,m2,,mkm_{1}, m_{2}, \ldots, m_{k} such that

j=1kmj=100,j=1kmj2=5996 \sum_{j=1}^{k} m_{j} = 100, \quad \sum_{j=1}^{k} m_{j}^{2} = 5996

We observe that [5996]=77[\sqrt{5996}] = 77. So we may take m1=77m_{1} = 77, so that

j=2kmj=23,j=2kmj2=67 \sum_{j=2}^{k} m_{j} = 23, \quad \sum_{j=2}^{k} m_{j}^{2} = 67

Now we may choose m2=5m_{2} = 5, m3=m4=4m_{3} = m_{4} = 4, m5=m6==m14=1m_{5} = m_{6} = \cdots = m_{14} = 1. Finally, we can take

k=14,(m1,m2,,m14)=(77,5,4,4,1,1,1,1,1,1,1,1,1,1) k = 14, \quad (m_{1}, m_{2}, \ldots, m_{14}) = (77, 5, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

proving the existence of 100 lines with exactly 2002 points of intersection.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.