## PROBLEM 3. REGIONS IN A CIRCLE

Place $n$ points on a circle and connect them pairwise with chords. Assume that no three chords have a common point inside the circle. Into how many regions will the circle be divided by these chords?
Solution. Suppose we draw the chords one by one sequentially. A new chord divides different regions, increasing the number of parts (Fig. 2). The additional number of regions is equal to the number of segments into which the new chord is divided by the chords it intersects. Therefore, this number is one more than the number of such intersection points. From this observation, it is easy to prove the remarkable formula expressing the number of regions in a circle resulting from drawing $L$ chords, no three of which intersect at internal points of the circle and have $P$ intersection points within this circle. The number of regions is

$$
P+L+1
$$

For $L=1$ we have $P+L+1=0+1+1=2$ (Fig. 3). A new line intersecting the first gives

$$
P+L+1=1+2+1=4
$$

and a line not intersecting the first gives

$$
P+L+1=0+2+1=3
$$

Suppose the value $P+L+1$ is valid for some $L \geqslant 2$. Let an additional line give $k$ new intersection points. By intersecting $k$ other lines, it passes through $k+1$ regions, increasing their number by $k+1$. Thus, for $L+1$ lines and $P+k$ intersection points, the total number of regions is

$$
(P+L+1)+(k+1)=(P+k)+(L+1)+1
$$

This is the proof of the formula by induction.

It is clear that there is a one-to-one correspondence between the intersection points $X$ and quadruples ( $A, B, C, D$ ) of $n$ points taken on the circumference (Fig. 4). Thus, the number of intersection points is $C_{n}^{4}$, the number of quadruples. Since the number of chords is $C_{n}^{2}$, the number of regions obtained

![](https://cdn.mathpix.com/cropped/2024_05_21_2f4fa61a46fbb276c744g-11.jpg?height=514&width=491&top_left_y=1648&top_left_x=380)

Fig. 4 by all possible pairwise connections of $n$ points is

$$
P+L+1=C_{n}^{2}+C_{n}^{4}+1
$$

(We observe that this result applies to any convex region on the plane and this approach generalizes to higher dimensions. A set $S$ of points is called convex if for every pair of points $A$ and $B$ in $S$, the segment $A B$ is entirely contained in $S$.)

The number expressing the number of regions can be beautifully derived by tracing the number of regions that decrease in our partition if we erase lines one by one. Each segment of a line separates two regions, which merge into one when this line is erased. The number of disappeared regions will be one more than the number of intersection points on this line. Since each intersection point lies on two lines, when one of them is erased, it also disappears from the other. Therefore, each intersection point appears exactly once during the process of erasing segments, and for each line, the number of disappeared regions is

(number of disappeared intersection points on the line) +1. After erasing all $L$ lines, we see that the total number of regions is $P$ plus one for each of the $L$ lines. Therefore, $P+L$ regions will disappear. Since only the interior of the circle remains in the end, there were initially $P+L+1$ regions.