18. A collection of 2011 circles divide the plane into $N$ regions in such a way that any pair of circles intersects at two points and no point lies on three circles. Find the last four digits of $N$.
18. Answer. 2112
Solution. We denote the numbers of regions divided by $n$ circles by $P(n)$. We have $P(1)=2, P(2)=4, P(3)=8, P(4)=14, \ldots$ and from this we notice that
$$
\begin{array}{l} 
P(1)= 2 \\
P(2)=P(1)+2 \\
P(3)= P(2)+4 \\
P(4)=P(3)+6 \\
\cdots \cdots \\
P(n)=P(n-1)+2(n-1)
\end{array}
$$

Summing these equations, we obtain
$$
P(n)=2+2+4+\ldots+2(n-1)=2+n(n-1) .
$$

This formula can be shown by induction on $n$ to hold true.
Base case: $n=1$ is obvious.
Inductive step: Assume that the formula holds for $n=k \geq 1$, i.e., $P(k)=2+k(k-1)$. Consider $k+1$ circles, the $(k+1)$-th circle intersects $k$ other circles at $2 k$ points (for each one, it cuts twice), which means that this circle is divided into $2 k$ arcs, each of which divides the region it passes into two sub-regions. Therefore, we have in addition $2 k$ regions, and so
$$
P(k+1)=P(k)+2 k=2+k(k-1)+2 k=2+k(k+1) .
$$

The proof by induction is thus complete.
Using this result, put $n=2011$, the number of regions $N=2+2011 \cdot(2011-1)=4042112$. So, the last 4 digits are 2112 .