# Another olympiad question related to Extremal Principle (regarding geometry problem)

Into how many parts at most is a plane cut by $n$ lines? (b) Into how many parts is space divided by $n$ planes in general position First i was thinking about the approach (not able to find it). Solution goes something like this. It uses recursion

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

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

How? This is the solution given in Engel: This solution [Engel, p. 40] starts with an 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; otherwise, 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 $n(n−1)/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)=n(n−1)/2+n+1={n\choose 2}+{n\choose 1}+{n\choose 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 ${n\choose 3}+{n\choose 2}+{n\choose 1}+{n\choose 0}$. How?

Also how to prove that if $S(n)$ is the space part, then at least $(2n-3)/4$ tetrahedra will exist?

• p(1)=2 p(2)=4 p(3)=p(2)+2+1=4+2+1=7 . Isn't p(3)=6 as p(3)=2*(3C2) – blue boy Jun 19 '15 at 13:13
• The numbers for line are known as the Lazy Caterer's sequence, the numbers for the plane are known as the cake numbers ! – Jorge Fernández Hidalgo Jun 19 '15 at 13:53
• interesting..:) @Gamamal – blue boy Jun 19 '15 at 14:42

Suppose that you have only one line in the plane. Then there are two parts. If you put another line, two things can happen: either the line intersects with the former line, or not. If it intersects the line, then each part will be divided by 2, if it doesn't intersect the line, then only one part is divided by 2. Then we look to add lines that intersect all the other lines in the plane (3 lines intersecting at the same point is not valid since it doesn't maximize the ammount of parts in which the plane is divided). Now, note that if the new line intersects all the other lines $n$, then there will be $n+1$ parts of the plane that will be cut, and therefore there will be $n$ new parts.
Then your relation should be $p(n+1)=p(n)+n$. Can you work out the recursion for the parts of the space? Do you see any similarity between the space case and the plane case?