The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

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.foo[email protected]. Please do not write to this address regarding general admissions or course queries.