## Problem 6.

The plane is divided into a finite number of regions $\mathrm{N}$ by three families of parallel lines. No three lines pass through the same point.

What is the minimum number of lines needed for N > 1999?
Solution:

Suppose there are $x$ lines in the first family, $y$ in the second, and $z$ in the third. The $x$ lines of the first family determine $x+1$ regions. The first line of the second family determines in the plane $(x+1) \cdot 2$ regions, the second $(x+1) \cdot 3 \ldots$. the $y$-th determines $(x+1)(y+1)$ regions.

The first line of the third family is cut by the $x+y$ existing lines into $x+y+1$ parts, and each of these parts divides each existing region into two, so the number of regions increases by $x+y+1$ regions. Each line of the third family increases the existing regions by the same amount; thus, the total number of regions $N$ is:

$$
N=(x+1)(y+1)+z(x+y+1)=x+y+z+xy+xz+yz+1=n+m+1
$$

with $n=x+y+z$ and $m=xy+xz+yz$.

We have:

$m=x^{2}+y^{2}+z^{2}-\frac{1}{2}\left((y-z)^{2}+(z-x)^{2}+(x-y)^{2}\right) \leq x^{2}+y^{2}+z^{2}$, then

$n^{2}=x^{2}+y^{2}+z^{2}-2m \geq 3m \Leftrightarrow m \leq \frac{n^{2}}{3}$ and $N=n+m+1 \leq n+\frac{n^{2}}{3}+1$.

For $n=76, n^{2}+\frac{n^{2}}{3}+1>2002$. Thus, if $n=76=x+y+z$ with $x=26, y=25, z=25$, it results: $m=1925$ and $N=2002$.