9. Find the maximum number of figures (or bodies) that can be formed

(a) by placing $n$ lines in $\mathbb{R}^{2}$;

(b) by placing $n$ planes in $\mathbb{R}^{3}$;

(c) by placing $n$ circles in $\mathbb{R}^{2}$;

(d) by placing $n$ spheres in $\mathbb{R}^{3}$.
Solution. Let $x_{n}$ be the maximum number of figures in parts (a)-(d). We have $x_{1}=2$. We will find the recurrence equations for $x_{n}, n \geqslant 2$. Suppose we already have an arrangement $A_{n-1}$ giving $x_{n-1}$ figures. A new object (i.e., a line, plane, circle, or sphere) will add as many figures as the number of parts this object is divided into by the objects in $A_{n-1}$.

(a) A new line intersecting the lines in $A_{n-1}$ at $n-1$ distinct points will give $n$ figures. No more figures can appear. Therefore, $x_{n}=x_{n-1}+n$ and, hence,

$$
x_{n}=x_{1}+2+\ldots+n=\frac{n(n+1)}{2}+1
$$

(b) According to part (a), a new plane will give no more than $n(n-1) / 2+1$ figures. It can be shown that a plane giving exactly this many figures always exists. Thus, $x_{n}=x_{n-1}+n(n-1) / 2+1$, from which we find $x_{n}=\left(n^{3}+5 n\right) / 6+1$.

(c) A new circle will give no more than $2(n-1)$ figures (two circles intersect in no more than 2 points). If the circles are drawn so that they all have a common interior neighborhood, then a new circle passing through this neighborhood will intersect each of them in 2 points. From this, it is not difficult to derive that $x_{n}=x_{n-1}+2(n-1)$ and, therefore, $x_{n}=(n-1) n+2$.
(d) Reasoning as in part (c), we can show that the maximum number of parts into which $n$ circles on a sphere in $\mathbb{R}^{3}$ divide the sphere is $(n-1) n+2$. Therefore, analogously to part (b), we get $x_{n}=x_{n-1}+(n-2)(n-1)+2$, or $x_{n}=n\left(n^{2}-3 n+8\right) / 3$.