42*. What is the greatest number of parts into which:

a) $n$ lines can divide a plane?

b) $n$ circles can divide a plane?

43**. What is the greatest number of parts into which:

a) $n$ planes can divide space?

b) $n$ spheres can divide space?
42. a) It is clear that $n$ lines will divide the plane into the maximum number of parts if all these lines intersect (i.e., no two of them are parallel) and no three of them intersect at the same point. Therefore, we only need to determine how many parts $n$ pairwise non-parallel lines, no three of which intersect at the same point, divide the plane.

${ }^{1}$ ) This result can also be derived from the fact that $n$ lines emanating from vertex $B$ divide each of the previously obtained $n+1$ parts of the triangle into $n+1$ smaller parts. However, the reasoning presented in the text is more convenient because it is also applicable in a number of subsequent problems.
lines, no three of which intersect at the same point ${ }^{1}$ ).

Suppose that $k$ lines have already been drawn on the plane; let us draw the $(k+1)$-th line and see how much the number of parts into which the lines divide the plane will increase. The $(k+1)$-th line intersects the existing $k$ lines at $k$ points, which divide it into $k+1$ segments. Therefore, the $(k+1)$-th line will cut exactly $k+1$ of the previously existing parts of the plane. Since it divides each of these parts into two, the total number of parts increases by $k+1$ after drawing the $(k+1)$-th line. If only one line is drawn, the plane is divided into two parts. Therefore, after drawing $n$ lines, the plane will be divided into

$$
2+2+3+4+\ldots+n
$$

parts (drawing the second line adds two more parts, drawing the third adds three more, drawing the fourth adds four more, and so on). Therefore, the maximum number of parts into which $n$ lines can divide the plane is

$$
\begin{aligned}
2+2+3+\ldots+n & =(1+2+3+\ldots+n)+1= \\
& =\frac{n(n+1)}{2}+1=\frac{n^{2}+n+2}{2}
\end{aligned}
$$

b) $n$ circles will divide the plane into the maximum number of parts if all these circles intersect each other (i.e., no two of them are tangent and none is entirely outside or inside another) and no three of them intersect at the same point.

Reasoning as in problem a), we will prove that the $(k+1)$-th circle increases the number of existing parts of the plane by $2k$ (the $(k+1)$-th circle intersects the $k$ already drawn circles at $2k$ points; these $2k$ points divide it into $2k$ segments). Since one circle divides the plane into two parts, the total number of parts after drawing $n$ circles will be

$$
\begin{aligned}
& 2+2+4+6+8+\ldots+2(n-1)= \\
& =2+2[1+2+3+\ldots+(n-1)]= \\
& =2+2 \frac{n(n-1)}{2}=n^{2}-n+2
\end{aligned}
$$

1) One might think that the number of parts still depends on the arrangement of the lines even if all these conditions are met. However, it will follow from our solution that this number is uniquely determined by the value of $n$ and, therefore, does not depend on the arrangement of the lines.