Greatest number of parts in which n planes can divide the space

Question

Find the greatest number of parts including unbounded in which n planes can divide the space.

I am trying like this, since it is very hard to visualize( or draw in paper).

Equation of plane in 3 space could be ax + by + cz +d = 0. If I could get an equation for number of regions I could use derivative to maximize it.

We will get a region when ax + by + cz + d < 0 or > 0 in all n planes. I am unable to find a equation for number of regions.

Answer 1

Too long for a comment.

To get started, try to solve the problem for $n$ lines in the plane, in general position (so no parallel lines, and no three lines meeting in a point). There you can draw the pictures. Start with 2, then 3, then 4 lines. You may see a pattern if you think about what happens when you add a new line to $n-1$ lines already in place.

Then move on to three dimensions. Use ideas from two dimensions - linear algebra isn't likely to help.

This is a special case of a very well studied idea.

https://en.wikipedia.org/wiki/Arrangement_of_hyperplanes#Real_arrangements

http://www.sciencedirect.com/science/article/pii/0012365X81900029

Answer 2

Your question is equivalent to the following:

What is the greatest number of parts a cake (cylinder/cube/any other convex shape) can be divided into with n straight cuts?

Appropriately these are called the cake numbers $C(n)$, and are indexed as A000125 in Sloane's OEIS.

The proof of this starts from two dimensions with the lazy caterer's sequence (A000124), the two-dimensional equivalent of the cake number (with a pizza). To achieve the maximum number of pieces $L(n)$ with n cuts, each new cut after the first ($L(1)=2$) must cross all previous cuts and no intersections, thereby adding n pieces at cut n. It is easy to see that the total number of pieces with n cuts is the n‌th triangular number plus one: $L(n)=\frac{n^2+n}2+1$.

Now go to three dimensions. After the first cut ($C(1)=2$), cut n crosses all previous cuts and no (triple) intersections; the intersections of the other planes with this latest cut form a division of the plane into the greatest number of pieces with $n-1$ cuts. So cut n adds $L(n-1)$ pieces, and after we solve the recursive equation we get $$C(n)=\frac{n^3+5n+6}6$$

Answer 3

On 2d

Question: What is the maximum number of regions that can be formed with n lines?

The main idea: A line can cut another line in at most 1 point.

As we want to form maximum number of regions, we are not going to allow any parallel lines.

Let $L_n$ = maximum number of regions that can be formed with $n$ lines

Clearly,

$L_0 = 1$, as there is no line

$L_1 = 2$, one line cuts the region into two half

$L_2 = 4$, cut the previous line with the new line

$L_3 = 7$, we can cut each two previous lines in two different points to achieve maximum number of regions

This indeed provides maximum number of regions, because while cutting a line and forming a point we are going to other regions to cut those regions into half. If we don't cut a line, we won't be visiting new regions to cut those. That means we need to form as many points on the 2-D space as possible while cutting the regions.

So while drawing $nth$ line on the region, we can form $(n - 1)$ points by cutting each of the $(n - 1)$ previously drawn lines. It turns out while forming $p$ points we are making $p + 1$ new regions. That means the $nth$ line will make $n + 1$ new regions.

Therefore the recurrence would be $$ L_n = \begin{cases} 1, & \text{if $n = 0$} \\ L_{n - 1} + n, & \text{if $n > 0$} \end{cases} $$

The solution for the above recurrence is $$ L_n = 1 + S_n, \text{where $n \ge 0$}$$ where $S_n$ = triangular number $$S_n = \frac{n(n+1)}{2}$$

Now let's go to 3D

On 3d

Question: What is the maximum number of regions that can be formed with n planes?

The main idea: A plane can cut another plane in at most 1 line.

Let $P_n$ = maximum number of regions that can be formed with n planes

Clearly,

$P_0 = 1$, as there is no plane

$P_1 = 2$, as the single plane cuts the whole region into half

$P_2 = 4$, cut the previous plane with the new plane thereby forming a new line

$P_3 = 8$, We can cut the two previous planes in two different new lines so we are forming two new lines this time which will add $L_2$ regions at maximum

In a similar argument, the $nth$ plane will cut each $n - 1$ planes in $n - 1$ lines at max. So it will create $n - 1$ new lines. But we already know the $n - 1$ new lines will add at max $L_{n - 1}$ regions.

Therefore the recurrence would be

$$ P_n = \begin{cases} 1, & \text{if $n = 0$} \\ P_{n - 1} + L_{n - 1}, & \text{if $n > 0$} \end{cases} $$

The solution for the above recurrence is

$$P_n = \frac{n^3+5n+6}{6}, \text{where $n \ge 0$}$$

If you are curious enough, on 4d

if $SP_n$ = maximum number of regions that can be formed with n spaces

then

$$ SP_n = \begin{cases} 1, & \text{if $n = 0$} \\ SP_{n - 1} + P_{n - 1}, & \text{if $n > 0$} \end{cases} $$

The solution for the above recurrence is

$$SP_n = \frac{n^4 - 2n^3 + 11n^2 + 14n + 24}{24}, \text{where $n \ge 0$}$$