All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Shapes > Geometry
Partitioning Space (Posted on 2004-09-13) Difficulty: 5 of 5
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.

No Solution Yet Submitted by SilverKnight    
Rating: 4.5000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Parts 1 and 2 | Comment 2 of 13 |

First, let me ask if the part of the plane NOT bounded by any group of circles is considered a circle. For instance, when there are 0 circles, is there still one region of the plane, or 0 regions? And then when you put the first circle down, now are there two regions of the plane (inside the circle and outside the circle) or just one region?

If we consider the unbounded portion of the plane to be a region, then the answer for the n intersecting circles is n^2-n+2. If the unbounded portion is not a region, then the answer is n^2-n+1.

If we consider the unbounded portion of the plane to be a region, then the answer for the n intersecting ellipses is 2n^2 – 2n + 2. If the unbounded portion is not a region, then the answer is 2n^2 – 2n + 1.

How did I get those? Well, first let’s just say the unbounded portion is NOT a region. I simply found the answer for the first 5 circles or ellipses. And the patterns were this:

Circle:
n      regions added      regions
0                                    0
1                1                  1
2                2                  3
3                4                  7
4                6                13
5                8                21

Notice that for n>2, the number of regions added is 2(n-1). So we just have to sum 2(n-1) from 1 to n, and add one for the first circle for n=1. The sum of 2(n-1) = 2*[the sum of (n-1)] = 2*[(n-1)*n/2] = n(n-1)

So the full formula is n(n-1) + 1 = n^2 – n + 1.
And if we decide that the unbounded area is a region, then we just add one because there will always be one more that we didn’t account for, so n^2 – n + 2.

Ellipses:
n      regions added      regions
0                                     0
1               1                   1
2               4                   5
3               8                 13
4             12                  25
5             16                  41

This time for n>2, the number of regions added is 4(n-1). So now we sum 4(n-1) from 1 to n, and again add one for the first circle for n=1. The sum of 4(n-1) = 4*[the sum of (n-1)] = 4*[(n-1)*n/2] = 2n(n-1).

So the full formula is 2n(n-1) + 1 = 2n^2 – 2n + 1.
And again, if we decide that the unbounded area is a region, then we just add one because there will always be one more that we didn’t account for, so 2n^2 – 2n + 2.


  Posted by nikki on 2004-09-13 15:43:03
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information