11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ it is a very hard question unless you're just asked for an intuitive answer ... $\endgroup$ – user354674 Sep 1 '16 at 20:58
7
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ Sorry I couldn't follow for the three dimensions part. Could you elaborate that part. Also could you explain how there is correspondence between the two things. It is not obvious at all how you could replace lines with planes and planes with space. $\endgroup$ – Amrita Sep 2 '16 at 19:45
  • $\begingroup$ I suggest you read the comments on the two OEIS pages I linked. I paraphrased them to put as an answer here. $\endgroup$ – Parcly Taxel Sep 3 '16 at 1:37
  • $\begingroup$ Hey, I read the comments in oeis, it is just a statement with no formal proof or justification. There is no justification how you could replace lines with planes and planes with space and still there will be a correspondence. $\endgroup$ – Amrita Sep 5 '16 at 18:10
  • $\begingroup$ The OEIS comments do provide a formal justification for the cake numbers, in a purely geometric fashion. You need to step outside the algebraic formulation of hyperplanes. $\endgroup$ – Parcly Taxel Sep 5 '16 at 23:35
4
$\begingroup$

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$}$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ My math background is not good. I have no idea about hyperplanes and the article is very difficult to follow. Is not a space very different from a plane. I don't see how one corresponds to another $\endgroup$ – Amrita Sep 1 '16 at 18:51
  • $\begingroup$ @Amrita Yes, the articles will be hard without math background. But you might be able to start as I suggested, thinking about lines in the plane. Or just wait a while - someone may provide the answer for you. $\endgroup$ – Ethan Bolker Sep 1 '16 at 18:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.