From Pizza Cut, we know the formula for maximum partitioning (pieces) of the circle, given n straight lines (cuts).
______________________________________

1. Determine the maximum number of regions of the plane produced by n intersecting circles.

2. Determine the maximum number of regions of the plane produced by n intersecting ellipses.

3. Determine the maximum number of regions of space produced by n intersecting spheres.

The maximum number of regions is n^2-n+2.  We prove this by proving a stronger statement:

Claim:  The maximum number of regions produced by n intersecting circles is n^2-n+2.  Furthermore, this number can be produced by a configuration where one of the regions is in the interior of all n circles.

Proof:  By induction on n.

When n=1, the claim is trivial.

Suppose the claim is true for n=k.  Note that the (k+1)st circle C can add at most 2k regions, since any region split by C must be intersected along two points on its boundary.  If more than 2k regions were added, then one of the k existing circles has been intersected more than 2 times by C, which is impossible since two circles can intersect at at most 2 points.

On the other hand, a circle can be added to add exactly 2k regions as follows:  first draw a straight line passing through the region contained in the interior of all k existing circles (which exists by the induction hypothesis) such that it does not pass through any of the other intersection points between those k circles.  Then, "bend" this line into a circle (or, as pointed out in my earlier post, perform an inversion to map this line to a circle).  This circle then intersects every other circle 2 times, for a total of 2k new intersections.  Furthermore, looking at every pair of adjacent intersections (adjacent along the newly added circle), we find that they are on the boundary of a previous region.  Thus, 2k regions have been split as desired. 

This new configuration of (k+1) circles produces (k^2-k+2)+2k = (k+1)^2-(k+1)+2 regions as desired.  Furthermore, since the newly added circle splits the region contained in the interior of all k previous circles, one of the two newly formed regions from the split is also in the interior of the newly added circle, upholding the induction hypothesis. 

This proves the claim and hence validates nikki's formula. 

Posted by David Shin on 2004-09-15 00:18:00