Indian National Mathematical Olympiad

Solution:

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

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

(ii) for $j \neq l$, the lines in $A_{j}$ and $A_{l}$ are not parallel.

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

$$\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

$$\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 $m_{1}, m_{2}, \ldots, m_{k}$ such that

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

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

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

Now we may choose $m_{2} = 5$, $m_{3} = m_{4} = 4$, $m_{5} = m_{6} = \cdots = m_{14} = 1$. Finally, we can take

$$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.