Yesterday I learned that there can be at most $n^2-n+2$ plane divisions by $n$ circles.
Can someone help me understand why if I have $k$ circles on the plane, that divide it into $k^2-k+2$ parts, and draw another circle, then the maximum number of divisions it will add is $2k$? I can't seem to comprehend it.
I have seen proofs that just say:"It's obvious that this circle will intersect with each one of the others in at most $2$ points, so we get $2k$ new parts from $k$ circles". The fact that there are $2$ intersections for each circle don't make it obvious to me, that $2k$ new divisions will be added.
Best Answer
Assume that you have $k$ circles which divide the plane into at most $k^2 - k + 2$ parts. Add a new circle. Consider intersections of this new circle with old circles. There are at most $2k$ such intersections. These points divide a new circle into at most $2k$ consecutive arcs. Each of these arcs divides at most $1$ old part into $2$ parts. Formally, you can also have more than one (say, $s$) arcs inside some old part. But these arcs are disjoint (except for endpoints) so the old part will be divided into at most $s + 1$ slices --- this means that there will be at most $s$ new parts. In total we can have at most $2k$ new parts. Thus after adding a new circle we can have at most $k^2 - k + 2 + 2k = (k + 1)^2 - (k + 1) + 2$ parts.