11

What is the greatest number of regions a plane can be divided into using $n$ straight lines? What about $n$ circles?

Can you generalize this into 3-dimensional space, planes and spheres?

For lines, I got $U_{n+1}=U_n+n,$ with $U_0=1.$ And for circles, I got $U_{n+1}=U_n+2n,$ with $U_0=1$ and $U_1=2.$

Am I right so far?

user26857
  • 52,094
user61067
  • 467

4 Answers4

8

Lines

For a plane with $n$ lines, consider what happens when you add a line. It divides all the regions through which it passes into two, thus adding one region for each region it passes through. The number of regions it passes through is the number of lines it crosses plus one, that is the number of points it creates plus one for itself. Thus, the number of regions added to the original one, $\binom{n}{0}$, is the number of points, $\binom{n}{2}$, plus the number of lines, $\binom{n}{1}$. Thus, the maximum number of regions is $$ \binom{n}{0}+\binom{n}{1}+\binom{n}{2}=\frac{n^2+n+2}{2} $$

Circles

For a plane with $n$ circles, consider what happens when you add a circle. It divides all the regions through which it passes into two, thus adding one region for each region it passes through. The first circle divides the plane into two. The number of regions it passes through is at least one, if it doesn't intersect any other circles, and up to the number of crossings with other circles. For $n$ circles there can be up to $2\binom{n}{2}$ crossings. Thus, the first circle divides the plane into two, $2\binom{n}{0}$, then the rest of the circles add the number of crossings. Thus, the maximum number of regions is $$ 2\binom{n}{0}+2\binom{n}{2}=n^2-n+2 $$

robjohn
  • 345,667
  • can you please tell me your reasoning behind this? How did you know to use binomials? – user61067 Apr 01 '13 at 17:45
  • I understand what you are doing, but don't feel as though I could explain it to someone else. – user61067 Apr 01 '13 at 17:47
  • @user61067: In the case of the lines, $\binom{n}{2}$ is the number of pairs of lines, and each pair of lines forms at most one point of intersection. In the case of circles, $2\binom{n}{2}$, is twice the number of pairs of circles, and each pair of circles forms at most two points of intersection. I used $\binom{n}{1}=n$ and $\binom{n}{0}=1$ not only because they make the formulas look nice, but also they explain the fact that the formulas match powers of $2$ for a few terms. – robjohn Apr 02 '13 at 00:28
  • thanks again. Is it correct that for planes in space the solution is the same as this but with $\binom{n}{3}$ added? And if so... What does $\binom{n}{3}$ represent? – user61067 Apr 02 '13 at 13:09
  • 1
    @user61067: in $\mathbb{R}^3$, $\binom{n}{3}$ represents the number of points since the intersection of three planes determines a point. However, a simple way to compute the maximum number of regions into which $n$ planes divides $\mathbb{R}^3$ is to notice that the number of regions added by plane $n$ is the number of regions split by plane $n$ which is the number of regions into which the previous $n-1$ planes divides plane $n$. That is, $R_3(n)-R_3(n-1)=R_2(n-1)=\binom{n-1}{2}+\binom{n-1}{1}+\binom{n-1}{0}$. $R_3(0)=1$ implies $$R_3(n)=\binom{n}{3}+\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$$ – robjohn Nov 02 '16 at 04:37
  • @user61067: in the same way, $R_4(n)=\binom{n}{4}+\binom{n}{3}+\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$ – robjohn Nov 02 '16 at 04:39
3

If a plane is divided by lines, recursion function is $R(n+1)=R(n)+n+1$, where $R(0)=1$, $n\geq0$ Solving the recurrence $R(n)=\frac{n^2+n+2}{2}$
If a plane is divided by circles, the recursion function is $R(n+1)=R(n)+2n$, where $R(1)=2$, $n>0$ Solving the recurrence $R(n)=n^2-n+2$

voyager
  • 59
0

Start with an empty plane. That’s one region. Then add $n$ parallel lines. You add $n$ more regions. Then tilt one line. Every time it hits another line a new region is created. Tilt all lines. You get $n$ choose 2 new regions for each pair of lines hitting each other. The sum is the formula above.

Likewise, in 3-D space start with an empty space which is one region. Then add $n$ parallel vertical walls, which add $n$ new regions. Then rotate the walls while keeping them vertical. They will meet in $n$ choose 2 vertical lines creating as many new regions. Then tilt the walls and they will meet in $n$ choose 3 points creating as many new regions (look up in the room you’re in right now!). The sum is the formula above.

Venky Nagar
  • 121
  • 1
  • 4
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Community Dec 11 '21 at 22:56
-2

For a plane divided by lines: $$l_{n+1}=l_{n}+n+1$$

For space divided by planes: $$s_{n+1}=s_{n}+l_{n}$$

Shaswata
  • 5,068