$N$ circles in a plane all intersect each other such that every circle intersects every other circle at exactly 2 points. Find in terms of $N$ the minimum and maximum number of disjoint closed regions that can be formed. Hint: You may wish to check your answers (visually) for greater $N,$ e.g. $N=4.$
-
- Given that
$a_1=1$and$a_n=2a_{n-1}$find$a_{20}.$
- Given that
-
Try to think about adding circles one at a time.
-
Consider the number of different points at which circles intersect.
-
Try to achieve the maximum and the minimum number of intersection points.
-
How many existing regions can a newly added circle pass through?
-
Note that a newly added circle does not (necessarily) pass through every previous region. In fact, after the
$3^{rd}$circle that’s impossible. -
How does the number of new intersection points relate to the number of new regions?
-
Denote with
$N_k$the number of disjoint regions after$k$circles have been added. The base case is$N_1=1.$The minimum occurs when the 2 points are the same for all pairs of circles, and each new circle is bigger than the last one added. Adding a new circle slices one internal region in two and adds a new region outside of the previous union. Thus we have
$N_{k+1} = N_k+2.$Hence$N_{k}=2k-1.$
The maximum occurs when each new added circle intersects each existing circle at two different points for every circle (maximum number of intersection points). Note that a newly added circle does not necessarily pass through every previous region; in fact, after the 3rd circle that’s impossible. In this case, adding a new circle will add as many new regions as twice the number of existing circles. In other words,
$N_{k+1}=N_k+2k.$We have$N_{k+1}=1+2\sum_{i=1}^{k}i=1+k(k+1)$or$N_k=1+k(k-1).$