0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Thanks:)....yes ,sorry about tetrahedra....n>=5 $\endgroup$ – blue boy Jun 20 '15 at 0:26

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.