Slicing of sphere maths problem?

tech77

You slice a sphere (apple etc) 10 times (without removing pieces).
The minimum number of slices generated is 11 (with none of the slices intersecting).
But what's the maximum number of pieces you can generate from 10 slices through a sphere (without removing sliced pieces of course)?

Saw this problem a while ago and could never got my head around it.

I'd appreciate if someone could give me an answer and more importantly explain it to me?

OK for 1 slice it can only be 2 pieces.
For a second slice through those 2 pieces it has to be 4.
For a third slice through all this the maximum generated is 8.
For a 4th slice through all that it seems to be only 14 (as the 4th slice can only pass through 6 of the 8 pieces (i think) leaving the remaining 2 intact.
After that my mind starts to hurt trying to visualise the ways a 5th and
6th slice etc can "maximally" pass through these pieces.

I'm sure it's a matter of developing a formula from the first few iterations rather than actually visualising it per se.

So can one of the resident geniuses here put me out of my misery.
I'd be especially impressed if someone who never encountered the problem could solve it from scratch. (something i definitely can't do).

MathsManiac

I think you'll find that the 4th slice can go through 7 of the 8 pieces, giving 15 regions.

Answer is, I think, (n^3+5n+6)/6. I'm on my way out, but I'll try and get time for an explanation later, if I can manage one!

Fallen Seraph

tech77 wrote: »

You slice a sphere (apple etc) 10 times (without removing pieces).

Might I ask a clarification question? Does "without removing pieces" mean that the sphere must always remain spherical?

tech77

Fallen Seraph wrote: »

Might I ask a clarification question? Does "without removing pieces" mean that the sphere must always remain spherical?

Yes.
Like cutting an apple repeatedly but not leaving it lose shape/fall apart while doing so.

So can anyone explain it to me please.

tech77

MathsManiac wrote: »

I think you'll find that the 4th slice can go through 7 of the 8 pieces, giving 15 regions.

Answer is, I think, (n^3+5n+6)/6. I'm on my way out, but I'll try and get time for an explanation later, if I can manage one!

Interesting.
I just can't visualise a plane passing thru' 7 out of 8 pieces for some reason. I can visualise 6 out of 8 alright.
I think i'd have to physically do it to convince myself of this.

MathsManiac

First of all, consider the corresponding problem in the plane. What's the maximum number of regions you can cut a circular region into with n straight lines? Note that this is the same as asking how many regions you can cut the entire plane into. (To see this, imagine having done it with the plane, and then making the circle sufficiently large so that it contains all of the points of intersection of the lines, of which there are only a finite number.)

0 lines: 1 region
1 line: 2 regions
2 lines: 4 regions
3 lines: 7 regions
4 lines: 11 regions
etc.

Note that when you draw a new line, all you have to do is make sure that it is not parallel with any existing line, and that it does not pass through any existing point of intersection. Your nth new line crosses all (n-1) of the existing lines. It therefore crosses n pre-existing regions, cutting each of them in two, and therefore adding n new regions.

That is, if f(n) represents the maximum number of regions created with n cuts f(n)=f(n-1)+n. You can solve this recurrence relation to get f(n)=(n^2+n+2)/2.

Similarly in 3-space, the problem of how many pieces you can cut the sphere into with n planes is the same as how many regions you can divide all of space into with n planes. (Again imagine doing the dissection of space, and then imagine the sphere being sufficiently large to contain the finitely many points of intersection of three planes.)

Now, to create a maximal number of regions in space with n planes, all you need to do is make sure that (1) no two planes are parallel, (2) that no three share the same line of intersection, (3) that none of them is parallel to the line of intersection of two others, and (4) that no four share the same point of intersection. (These condidtions can be met, since in creating each new plane, there is only a finite number of such constraints, and infinitely many locations and orientations to choose from - that is, if you're in trouble with the new one, just tilt it and/or translate it.)

Since no two planes are parallel, each new plane drawn will intersect every pre-existing plane. That is, each of the pre-existing planes cuts a line on the new plane, and these lines are separate (since otherwise constraint 1 has been violated). No two of these lines will be parallel, (since otherwise constraint 2 or 3 is violated) and no three of them concurrent (since otherwise constraint 4 is violated.) Thus, the pattern drawn on this new plane satisfies the requirements of the 2D problem already analysed. Accordingly, the n-1 lines drawn on this plane divide it into [(n-1)^2+(n-1)+2]/2 planar regions. But every such planar region on this new plane is cutting a pre-exising region of space in two, creating that many new regions.

Now we have a recurrrence relation g(n)=g(n-1)+[(n-1)^2+(n-1)+2]/2.
You can solve this to get g(n)=(n^3+5n+6)/6, or just verify by induction.

tech77

MathsManiac wrote: »

First of all, consider the corresponding problem in the plane. What's the maximum number of regions you can cut a circular region into with n straight lines? Note that this is the same as asking how many regions you can cut the entire plane into. (To see this, imagine having done it with the plane, and then making the circle sufficiently large so that it contains all of the points of intersection of the lines, of which there are only a finite number.)

0 lines: 1 region
1 line: 2 regions
2 lines: 4 regions
3 lines: 7 regions
4 lines: 11 regions
etc.

Note that when you draw a new line, all you have to do is make sure that it is not parallel with any existing line, and that it does not pass through any existing point of intersection. Your nth new line crosses all (n-1) of the existing lines. It therefore crosses n pre-existing regions, cutting each of them in two, and therefore adding n new regions.

That is, if f(n) represents the maximum number of regions created with n cuts f(n)=f(n-1)+n. You can solve this recurrence relation to get f(n)=(n^2+n+2)/2.

Similarly in 3-space, the problem of how many pieces you can cut the sphere into with n planes is the same as how many regions you can divide all of space into with n planes. (Again imagine doing the dissection of space, and then imagine the sphere being sufficiently large to contain the finitely many points of intersection of three planes.)

Now, to create a maximal number of regions in space with n planes, all you need to do is make sure that (1) no two planes are parallel, (2) that no three share the same line of intersection, (3) that none of them is parallel to the line of intersection of two others, and (4) that no four share the same point of intersection. (These condidtions can be met, since in creating each new plane, there is only a finite number of such constraints, and infinitely many locations and orientations to choose from - that is, if you're in trouble with the new one, just tilt it and/or translate it.)

Since no two planes are parallel, each new plane drawn will intersect every pre-existing plane. That is, each of the pre-existing planes cuts a line on the new plane, and these lines are separate (since otherwise constraint 1 has been violated). No two of these lines will be parallel, (since otherwise constraint 2 or 3 is violated) and no three of them concurrent (since otherwise constraint 4 is violated.) Thus, the pattern drawn on this new plane satisfies the requirements of the 2D problem already analysed. Accordingly, the n-1 lines drawn on this plane divide it into [(n-1)^2+(n-1)+2]/2 planar regions. But every such planar region on this new plane is cutting a pre-exising region of space in two, creating that many new regions.

Now we have a recurrrence relation g(n)=g(n-1)+[(n-1)^2+(n-1)+2]/2.
You can solve this to get g(n)=(n^3+5n+6)/6, or just verify by induction.

Thanks for that.
I'm sure it's correct but I'm still having difficulty understanding it fully.

I have a couple of queries:

Could you prove why if you cross (n-1) lines with an nth line you get a maximum of n new regions.

If I understand that I understand the 2D part of the solution.

Secondly how do you get f(n)= [n^2 + n +2]/2 from f(n)= f(n-1)+n.
I didn't do maths in college (only LC higher A2) so I never did recurrence relations.

Most importantly I don't understand how you went from 2D to 3D. Could you please explain how you did that a bit more.

Also can you actually visualise in your mind a 4th plane creating 7 pieces (and then a 5th plane creating however many..) or do you just rely on the maths.

Thanks.

MathsManiac

Will try to answer your queries one at a time:

tech77 wrote: »

Could you prove why if you cross (n-1) lines with an nth line you get a maximum of n new regions..

You can only create a new region by cutting an existing region in two. Imagine moving along the line from infinitely far away. As soon as you encounter (cross) another line, you've just completed cutting the region that you were in, and you're starting to cut the region you're entering. The total number of regions you cross is 1 more than the number of lines you cross. (Think of this with actual numbers, not n's - if you cross only one other line you've visited 2 regions, [the one before and the one after], if you cross 2 lines, you've visited 3 regions [the one before, the one between and the one after], etc.)

tech77 wrote: »

Secondly how do you get f(n)= [n^2 + n +2]/2 from f(n)= f(n-1)+n.
I didn't do maths in college (only LC higher A2) so I never did recurrence relations.

If you did LC after 1994, then you may remember a thing called "difference equations" Recurrence relations are basically the same thing. (If you did LC before '94, then you won't have met these.)

I probably should have illustrated better how to add this sequence. One way is to note the pattern and try to break down the numbers. The sequence 1,2,4,7,11,... is growing by adding 1 then 2 then 3 then 4 etc. From this you can write:
f(0) = 1 = 1
f(1) = 2 = 1+1
f(2) = 4 = 1+1+2
f(3) = 7 = 1+1+2+3
f(4) = 11 = 1+1+2+3+4
...
Now you can see that, apart from the extra "1" at the start of each sum, f(n) is just the sum of the first n natural numbers. There's a formula for this that you might remember from LC days: n(n+1)/2. Adding on the extra 1 gives f(n) = n(n+1)/2 + 1, which can be rearranged if required to give [n^2 + n +2]/2

tech77 wrote: »

Most importantly I don't understand how you went from 2D to 3D. Could you please explain how you did that a bit more.

Not sure if I really can. Could I suggest that you mess around with the 2D version more until you're really on top of it, and then come back and try thinking about the 3D case again? Planes take on the role that lines had in the 2D case. Just as in the 2D case you have to satisfy yourself that each new line (provided it satisfies the constraints) will eventually cross every other line and cut all the regions that it visits in two, so in the 3D case you need to satisfy yourself that every plane will intersect with all of the previous planes, and will slice through the same number of spacial regions as the number of plane regions that get drawn on it.

tech77 wrote: »

Also can you actually visualise in your mind a 4th plane creating 7 pieces (and then a 5th plane creating however many..) or do you just rely on the maths.
Thanks.

Well I wasn't planning on having to do the artwork, but here goes. I've attached two images. The first is meant to represent three mutually perpendicular planes. There are, as you say, eight regions. You can see directly into seven of these, while the eighth is hidden at the bottom back.
3planes.jpg
On the the second diagram I've drawn in a new plane, more or less facing you flat-on, and positioned a bit closer to you than the "origin" (the point of intersection of the first three planes) so that the origin lies behind it. This new planes cuts through all seven of the visible regions, (but doesn't cut through the hidden one at the back.)
4planes.jpg
So, how are we doing now???

tech77

MathsManiac wrote: »

Will try to answer your queries one at a time:



You can only create a new region by cutting an existing region in two. Imagine moving along the line from infinitely far away. As soon as you encounter (cross) another line, you've just completed cutting the region that you were in, and you're starting to cut the region you're entering. The total number of regions you cross is 1 more than the number of lines you cross. (Think of this with actual numbers, not n's - if you cross only one other line you've visited 2 regions, [the one before and the one after], if you cross 2 lines, you've visited 3 regions [the one before, the one between and the one after], etc.)



If you did LC after 1994, then you may remember a thing called "difference equations" Recurrence relations are basically the same thing. (If you did LC before '94, then you won't have met these.)

I probably should have illustrated better how to add this sequence. One way is to note the pattern and try to break down the numbers. The sequence 1,2,4,7,11,... is growing by adding 1 then 2 then 3 then 4 etc. From this you can write:
f(0) = 1 = 1
f(1) = 2 = 1+1
f(2) = 4 = 1+1+2
f(3) = 7 = 1+1+2+3
f(4) = 11 = 1+1+2+3+4
...
Now you can see that, apart from the extra "1" at the start of each sum, f(n) is just the sum of the first n natural numbers. There's a formula for this that you might remember from LC days: n(n+1)/2. Adding on the extra 1 gives f(n) = n(n+1)/2 + 1, which can be rearranged if required to give [n^2 + n +2]/2


Not sure if I really can. Could I suggest that you mess around with the 2D version more until you're really on top of it, and then come back and try thinking about the 3D case again? Planes take on the role that lines had in the 2D case. Just as in the 2D case you have to satisfy yourself that each new line (provided it satisfies the constraints) will eventually cross every other line and cut all the regions that it visits in two, so in the 3D case you need to satisfy yourself that every plane will intersect with all of the previous planes, and will slice through the same number of spacial regions as the number of plane regions that get drawn on it.



Well I wasn't planning on having to do the artwork, but here goes. I've attached two images. The first is meant to represent three mutually perpendicular planes. There are, as you say, eight regions. You can see directly into seven of these, while the eighth is hidden at the bottom back.
3planes.jpg
On the the second diagram I've drawn in a new plane, more or less facing you flat-on, and positioned a bit closer to you than the "origin" (the point of intersection of the first three planes) so that the origin lies behind it. This new planes cuts through all seven of the visible regions, (but doesn't cut through the hidden one at the back.)
4planes.jpg
So, how are we doing now???

Ok thanks.
I understand the 2D part.
Even though as you start crossing more and more lines I keep wondering if each region crossed is MORE than just doubling and not tripling etc. It's irrational I know.

The recurrence relation
bit threw me a bit initially...
I probably should've easily seen it as 1 + the addition of the first n natural numbers as you say.

As for the 3D part I know what you're saying but i'll have to keep thinking about it TBH.

Given that one plane intersects all other planes you say a pattern akin to the 2D example is set up on the new plane and each region thus created divides a space.
That is the bit i'm having trouble envisaging and have to think more about.

Anyway if I accept this concept the new number of spaces this time is the f(n) of the 2D version rather than n.

So only thing now is how do you get g(n) from the addition of the f(n)s.

Did you ever come across this problem before?
If not do you mind me asking are you a maths Prof. or something.
And would you regard such a problem as easy or difficult?

Anyway until I can honestly say i would've had the intuition to use the 2D model to solve the 3D version I don't think I've fully got a hold on it.

But i'll keep looking at your explanation in more detail and it'll eventually click.
Thanks.

MathsManiac

tech77 wrote: »

Even though as you start crossing more and more lines I keep wondering if each region crossed is MORE than just doubling and not tripling etc. It's irrational I know.

Is it that you think the new line might be dipping in and out of region, cutting it more than once? If so, note that the regions are what's called "convex"; they don't have any inward-sticking corners. And if you draw a straight line across a convex region, you can't cut it into more than two pieces.

tech77 wrote: »

Anyway if I accept this concept the new number of spaces this time is the f(n) of the 2D version rather than n.

Yep.

tech77 wrote: »

So only thing now is how do you get g(n) from the addition of the f(n)s.

In general, suppose you have, as we do here, g(n)=g(n-1)+[some expression in n].
Let's call it g(n)=g(n-1)+h(n), where h(n) is an expression in n.
Then, you can say g(n-1)=g(n-2)+h(n-1), and sub that it to get g(n)=g(n-2)+h(n-1)+h(n).
Do it again and get g(n)=g(n-3)+h(n-2)+h(n-1)+h(n).
Keep going all the way down till you get:
g(n)=g(0)+h(1)+h(2)+h(3)+...h(n).
Now if h(n) is an expression such that you're able to sum h(r) from 1 to n, you're in business.
In the 2D case, h(n) was just n, so I summed it as n(n+1)/2, as indicated earlier.
In the 3D case, h(n) is [(n-1)^2+(n-1)+2]/2. This can be simplified to n^2/2 + n/2 + 1. Thus, h(r) can be summed from 1 to n by using the well-established results that: sum of first n numbers is n(n+1)/2, sum of first n squares is n(n+1)(2n+1)/6, and sum of a constant is n times the constant. When you do this and add on the g(0)=1 and tidy it up you get g(n)=(n^3+5n+6)/6.

tech77 wrote: »

Did you ever come across this problem before?

I'd come across the 2D puzzle before (in the guise of cutting a pizza into a maximum number of pieces using staright cuts). I'm sure I had probably heard of the correponding problem in 3-space but hadn't considered it in detail before.

tech77 wrote: »

If not do you mind me asking are you a maths Prof. or something.

No, I used to be a maths teacher, but now I'm working in a different area. I still enjoy doing "recreational maths", and so this was good fun!

tech77 wrote: »

And would you regard such a problem as easy or difficult?

I guess all problems of any interest are hard before you solve them, (and easy afterwards!) It strikes me as a bit of a tuffie for anyone who doesn't spend a fair bit of time doing maths problems. And anything involving 3D visualisation can be tricky for a lot of people.

Now here's a hard problem: to create a properly defined and objective measure of the difficulty of maths problems, in such a way that the question: "was this a hard problem" has an unambiguously correct answer!!!

tech77 wrote: »

Anyway until I can honestly say i would've had the intuition to use the 2D model to solve the 3D version I don't think I've fully got a hold on it.

In general, if you can't solve a hard problem, try to solve a similar but easier one first.

Wow, I've just googled "solve an easier one first" to try and confirm by belief that it was Polya who first enunciated that principle for solving problems, and the second link that appeared was this: http://www.math.toronto.edu/mccann/assignments/204/cuttingplanes.pdf which is about the very problem we've been discussing! Have a look and see if it helps you further.

tech77

MathsManiac wrote: »

Is it that you think the new line might be dipping in and out of region, cutting it more than once? If so, note that the regions are what's called "convex"; they don't have any inward-sticking corners. And if you draw a straight line across a convex region, you can't cut it into more than two pieces.


Yep.

In general, suppose you have, as we do here, g(n)=g(n-1)+[some expression in n].
Let's call it g(n)=g(n-1)+h(n), where h(n) is an expression in n.
Then, you can say g(n-1)=g(n-2)+h(n-1), and sub that it to get g(n)=g(n-2)+h(n-1)+h(n).
Do it again and get g(n)=g(n-3)+h(n-2)+h(n-1)+h(n).
Keep going all the way down till you get:
g(n)=g(0)+h(1)+h(2)+h(3)+...h(n).
Now if h(n) is an expression such that you're able to sum h(r) from 1 to n, you're in business.
In the 2D case, h(n) was just n, so I summed it as n(n+1)/2, as indicated earlier.
In the 3D case, h(n) is [(n-1)^2+(n-1)+2]/2. This can be simplified to n^2/2 + n/2 + 1. Thus, h(r) can be summed from 1 to n by using the well-established results that: sum of first n numbers is n(n+1)/2, sum of first n squares is n(n+1)(2n+1)/6, and sum of a constant is n times the constant. When you do this and add on the g(0)=1 and tidy it up you get g(n)=(n^3+5n+6)/6.


I'd come across the 2D puzzle before (in the guise of cutting a pizza into a maximum number of pieces using staright cuts). I'm sure I had probably heard of the correponding problem in 3-space but hadn't considered it in detail before.

No, I used to be a maths teacher, but now I'm working in a different area. I still enjoy doing "recreational maths", and so this was good fun!

I guess all problems of any interest are hard before you solve them, (and easy afterwards!) It strikes me as a bit of a tuffie for anyone who doesn't spend a fair bit of time doing maths problems. And anything involving 3D visualisation can be tricky for a lot of people.

Now here's a hard problem: to create a properly defined and objective measure of the difficulty of maths problems, in such a way that the question: "was this a hard problem" has an unambiguously correct answer!!!



In general, if you can't solve a hard problem, try to solve a similar but easier one first.

Wow, I've just googled "solve an easier one first" to try and confirm by belief that it was Polya who first enunciated that principle for solving problems, and the second link that appeared was this: http://www.math.toronto.edu/mccann/assignments/204/cuttingplanes.pdf which is about the very problem we've been discussing! Have a look and see if it helps you further.

OK thanks.
Again now that I think of it I probably should've been able to express g(n) purely in terms of h(n) myself but I can't remember doing maths like that for LC (or else i've just forgotten it all..).
Thanks for that.

Yeah that irrational feeling of a line cutting a region into more than 2 may be related to a falsely perceived concavity of the regions.

It also has to do with the fact that the regions that you eventually end up cutting are themselves bounded by other drawn lines rather than the original circumference of the circle (even though that shouldn't make a difference I know).

Incidentally would you be stuck if h(n) wasn't so amenable to summation?
Or are there rules for summing any expression?

The thinking that prompts you to go from 3D to 2D i'm guessing is presumably the fact that you can visualise the lines etched on the nth plane by previous planes fairly well (and then to obviously maximise their intersections).

My difficulty visualising this is probably the reason I wouldn't have intuitively employed the 2D model and then have had some chance of solving the problem.

Also in that link it discusses hyperplanes thru' a theoretical 4th dimension.
Let's see you throw together an image of that.

Thanks again.

MathsManiac

tech77 wrote: »

OK thanks.
Incidentally would you be stuck if h(n) wasn't so amenable to summation?
Or are there rules for summing any expression?

It depends, I think. There is a formula for summing any power, (a different formula for each power, but there's a general technique for getting a formula for any power using the formulas for lower powers). Other types of h(n) might have other techniques - like summing a geometric series, etc. I'm sure, though, that there are also lots of h(n)'s that aren't readily summable.

tech77 wrote: »

Also in that link it discusses hyperplanes thru' a theoretical 4th dimension.
Let's see you throw together an image of that.
Thanks again.

Sure. Just send me a 4-dimensional pencil and I'll run it up for you!

Fremen

This is only tangentially related to the thread topic, but I couldn't resist, since I'm pretty bored at the moment.

The Banach-Tarski paradox is one of the freakiest theorems ever discovered. It basically says you can take a sphere the size of a pea, make a finite number of cuts into it, then rearrange the pieces using only rotation, translation and reflection, to make a sphere the size of, say, the sun.

Pretty weird, no?