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.

Very similar to the previous solution:

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

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

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 ellipse E can add at most 4k regions, since any region split by E must be intersected along two points on its boundary.  If more than 4k regions were added, then one of the k existing ellipses has been intersected more than 4 times by E, which is impossible since two ellipses can intersect at at most 4 points.

On the other hand, an ellipse can be added to add exactly 4k regions as follows:  first draw two parallel straight lines passing through the region contained in the interior of all k existing ellipses (which exists by the induction hypothesis) such that none of the previous intersection points lie in the closed "slab" determined by these two parallel lines.  Then, "bend" these two lines into an ellipse.  This ellipse then intersects every other ellipse 4 times, for a total of 4k new intersections.  Furthermore, looking at every pair of adjacent intersections (adjacent along the newly added ellipse), we find that they are on the boundary of a previous region.  Thus, 4k regions have been split as desired. 

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

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

Edited on September 15, 2004, 12:28 am

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