In how many parts is a plane cut by n lines, or a space cut by n planes?

Question

Into how many parts at most is a plane cut by $n$ lines? Into how many parts is space divided by $n$ planes in general position?

My approach:

$$p(n+1)=p(n)+n+1$$ $$s(n+1)=s(n)+p(n)$$

This solution is given by Engel (pg. 40). It starts with anthe observation that the regions into which the plane is divided by $n$ lines are defined by their vertices which are the points of intersection of the given lines.

We may assume that none of the lines is horizontal; if one is, rotate the plane by a small angle. This ensures that the regions are of two sorts: some regions (finite or not) have the lowest vertex, others do not. Every point of intersection serves as the lowest vertex of exactly one region. Therefore, for $n$ lines, there are $\binom{n}{2}$ regions of the first sort. There are $n+1$ regions of the second sort, which becomes apparent when a horizontal line is drawn that crosses all n lines below all of their "legitimate" intersection points.

Therefore, $$L_n=\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$$

The latter expression can be easily generalized to a 3D problem wherein the question is about the number of regions into which n planes divide the space. The answer is

$$\binom{n}{3}+\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$$

How? Also how to prove that if S(n) is the space part , then at least $\frac{2n-3}{4}$ tetradehra will exist?

What will happen if instead of a line, a circle cuts the plane?

Answer 1

If we arrange $n$ hyperplanes in a $d$-dimensional space such that the number of regions is maximized, we obtain

$$R_d(n) = \sum\limits_{i = 0}^d\binom{n}{i}$$

This is a standard result that you can find in nearly any introductory combinatorics book. This is an outline of the proof:

The following recurrence relation describes this problem:

$$R_d(n) = R_d(n-1) + R_{d-1}(n-1)$$

To see why this is true, imagine taking $n-1$ hyperplanes in general position, then adding the $n^{th}$ hyperplane to the group. If we consider only this hyperplane, each intersection with the other hyperplanes is a "hyperline" in this $(d-1)$-dimensional hyperplane, which will make $R_{d-1}(n-1)$ regions on that plane.

After you convince yourself that each of these regions created on the $n^{th}$ hyperplane adds one to the original $d$-dimensional space, the recurrence is clear. This leaves us with the following:

$$\sum\limits_{i = 0}^d\binom{n}{i} = \sum\limits_{i = 0}^d\binom{n-1}{i} + \sum\limits_{i = 0}^{d-1}\binom{n-1}{i}$$ $$= \sum\limits_{i = 0}^d\binom{n-1}{i} + \sum\limits_{i = 1}^{d}\binom{n-1}{i-1}$$ $$= \binom{n-1}{0} + \sum\limits_{i = 1}^d\binom{n-1}{i} + \binom{n-1}{i-1}$$ Apply Pascal's formula, and note that $\binom{n-1}{0} = \binom{n}{0}$ $$= \binom{n}{0} + \sum\limits_{i = 1}^d\binom{n}{i}$$ $$= \sum\limits_{i = 0}^d\binom{n}{i}$$

Because the recurrence is satisfied and the initial values match, the given summation will work (this is a very lazy way to show it holds).

---

For circles in the plane, the number of regions is given by A014206.

$$R(n) = n^2-n+2$$

This is easy to show by induction. The base case $n=1$, should be clear. We will assume that

$$R(n) = n^2-n+2$$

If we add another circle, then it intersects each other circle twice, creating $2$ regions (overlap, and the non-overlap area inside the new circle). As we currently have $n$ circles, adding the next will create $2n$ more regions:

$$R(n) + 2n = n^2 + n + 2 = (n+1)^2 - (n+1) + 2 = R(n+1)$$

So we are done by induction.

---

I don't think the statement about the tetrahedra is true. If you have just two hyperplanes, it does not hold, nor even with three. Perhaps there is further detail in your textbook?