The Computer Laboratory

Practice Paper 3 Question 10

\(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.\)

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. Given that \(a_1=1\) and \(a_n=2a_{n-1}\) find \(a_{20}.\)

Hints

  • Hint 1
    Try to think about adding circles one at a time.
  • Hint 2
    Consider the number of different points at which circles intersect.
  • Hint 3
    Try to achieve the maximum and the minimum number of intersection points.
  • Hint 4
    How many existing regions can a newly added circle pass through?
  • Hint 5
    Note that a newly added circle does not (necessarily) pass through every previous region. In fact, after the \(3^{rd}\) circle that's impossible.
  • Hint 6
    How does the number of new intersection points relate to the number of new regions?

Solution

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).\)

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.footasc@sulp.ecitcarp. Please do not write to this address regarding general admissions or course queries.