Your cart is empty
Division of the plane and the space
(extra-curricular topic)
In this lesson we will examine problems concerning location of the basic geometric concepts studied in the previous part. These kind of problems are the topic of combinatorial geometry. It is common for these problems that enumerative questions arise along the geometric concepts.
The following easy proposition is suggested by the geometric viewpoint:
Any n points divide a line into \latex{ n + 1 } parts.
It is worth taking a closer look at the proof of this statement as its way of proof can be easily generalized.
If the number of points is \latex{ 0 }, then the line has \latex{ 1 } part. If we pick a point on the line, then the number of parts will increase by \latex{ 1 } even if there were \latex{ n } points chosen already. This is because one part of the line will be divided into two parts by the new point. Therefore \latex{ n } points increase the number of parts from the original \latex{ 1 } by \latex{ n }, to\latex{ n + 1 }.
Example 1
There are \latex{ n } lines given in the plane. Suppose that there are no lines coinciding. At least and at most how many parts do these lines divide the plane into?
Solution
We have already met this problem in the past years but now we will discuss a new solution which gives us a chance to solve the analogous problem in space.
Let us denote the number of parts determined by the lines by \latex{ s }.
It is clear that for \latex{n = 1} the number of parts equals \latex{s = 2}. (Figure 14)
Let us denote the number of parts determined by the lines by \latex{ s }.
It is clear that for \latex{n = 1} the number of parts equals \latex{s = 2}. (Figure 14)
If \latex{n = 2}, then there are two possible cases. If the lines are parallel, then the number of parts is \latex{s = 3}, while if the lines are intersecting, then the number of parts is \latex{s = 4}.
(Figure 14)
If \latex{n = 3}, then the number of possibilities increases even more. (Figure 15)
(Figure 14)
If \latex{n = 3}, then the number of possibilities increases even more. (Figure 15)
\latex{ n=2 }
\latex{ n=1 }
\latex{ e_1 }
\latex{ e_1 }
\latex{ e_2 }
\latex{ e_2 }
\latex{ e_1 }
\latex{ s=4 }
\latex{ s=3 }
\latex{ s=2 }
Figure 14
\latex{ n=3 }
\latex{ s=4 }
\latex{ s=6 }
\latex{ s=6 }
\latex{ s=7 }
Figure 15
It seems clear after studying these examples that for a given \latex{ n } the number of parts will be minimal exactly when the lines are parallel. In this case the number of parts is \latex{s = n + 1}.
It is also clear that the number of parts is maximal for a given n if there are no parallel among the lines and there are no three of them intersecting in one point. (A set of lines with these properties is called independent.)
Let \latex{s(n)} denote the number of the parts which n independent line divided the plane into. If \latex{ n } such lines are already selected then the number of parts is \latex{s(n)}. Choose a new line; this intersects all of the already placed \latex{ n } lines, in \latex{ n } different points (Figure 16). These divide the new line into \latex{n + 1} parts and every part divides an already existing part of the plane into two. Therefore the placement of the \latex{(n+1)^{th}} line increases the number of parts by \latex{n + 1}, that is,
\latex{s(n+1)=s(n)+n+1}.
This gives us a chance to determine \latex{ s(n) } directly: write down \latex{ s(i) } for \latex{ i = 1;\, 2;\, …;\, n }:
\latex{s(1)=s(0)+1},
\latex{s(2)=s(1)+2},
\latex{s(3)=s(2)+3},
\latex{\vdots}
\latex{s(n)=s(n-1)+n}.
\latex{s(2)=s(1)+2},
\latex{s(3)=s(2)+3},
\latex{\vdots}
\latex{s(n)=s(n-1)+n}.
\latex{(n+1)^{th}} line
\latex{ n } intersection
points
points
Figure 16
After adding the corresponding sides of these equations and rearranging, we get
\latex{s(n)=s(0)+1+2+\dots+n=\\=1+\frac{n\times(n+1)}{2}=\frac 1 2\times(n^2+n+2).}
Here we used the fact that the sum of the first n natural numbers can be expressed in the closed form of \latex{\frac{n\times(n+1)}{2}}.
Example 2
There are \latex{ n } planes given in the space. Suppose that there are no coinciding planes. At least and at most how many regions do these planes divide the space into?
Solution
Let us denote the number of regions determined by the planes by \latex{ t }.
Obviously, for \latex{ n = 1 } the number of regions equals \latex{ t = 2 }. (Figure 17)
If \latex{n = 2}, then there are two cases. If the two planes are parallel, then the number of regions of space is \latex{t = 3}, while if they are not parallel, then \latex{t = 4}. (Figure 17)
If \latex{n = 3}, then the possibilities are as follows. (Figure 18)
If \latex{n = 2}, then there are two cases. If the two planes are parallel, then the number of regions of space is \latex{t = 3}, while if they are not parallel, then \latex{t = 4}. (Figure 17)
If \latex{n = 3}, then the possibilities are as follows. (Figure 18)
\latex{ n=2 }
\latex{ n=1 }
\latex{ t=2 }
\latex{ t=3 }
\latex{ t=4 }
Figure 17
\latex{ t=4 }
\latex{ t=6 }
\latex{ t=6 }
\latex{ t=7 }
\latex{ t=8 }
Figure 18
- The planes are pairwise parallel, the number of regions is \latex{t = 4}.
- Two planes are parallel, the third one intersects them. The number of regions is \latex{t = 6}.
- The three planes are incident to one common line. Then the number of regions is \latex{t = 6}.
- The intersection of any two planes is a line parallel (but not incident to) the third one. Then \latex{t = 7}.
- The three planes have one single point in common. Then the number of regions is \latex{t = 8.}
Again it seems clear that for a given n the number of regions is minimal when the planes are parallel; in this case \latex{t = n + 1}.
The number of regions, however, will be maximal if there are none of the following: two parallel planes, three planes having a line in common, four planes having one point in common. (In this case the planes are called independent.)
Let \latex{t(n)} denote the number of regions determined by \latex{ n } independent planes.
The number of regions, however, will be maximal if there are none of the following: two parallel planes, three planes having a line in common, four planes having one point in common. (In this case the planes are called independent.)
Let \latex{t(n)} denote the number of regions determined by \latex{ n } independent planes.
In this lesson we will examine problems concerning location of the basic geometric concepts studied in the previous part. These kind of problems are the topic of combinatorial geometry. It is common for these problems that enumerative questions arise along the geometric concepts.
The following easy proposition is suggested by the geometric viewpoint:
Suppose that we choose an \latex{(n + 1)^{th}} plane after placing \latex{ n }. This new plane intersects the previous ones in \latex{ n } independent lines which divide it into \latex{s(n)} domains. Each one of these divides an existing region of space, thus adding one new plane increases the number of regions by \latex{s(n)}.
Therefore
\latex{t(n+1)=t(n)+s(n)}.
Again, write down this equation for \latex{i = 1;\, 2;\,\dots;\, n} and add the corresponding sides:
\latex{t(1)=t(0)+s(0)},
\latex{t(2)=t(1)+s(1)},
\latex{\vdots},
\latex{t(n)=t(n-1)+s(n-1)}.
Thus\latex{t(2)=t(1)+s(1)},
\latex{\vdots},
\latex{t(n)=t(n-1)+s(n-1)}.
\latex{t(n)=t(0)+s(0)+s(1)+\dots+s(n-1)}.
We know that \latex{ t(0) = 1 } and the rest of the sum can be computed as follows:
\latex{s(0)+s(1)+\dots+s(n-1)=\\=\frac 1 2\times(0^2+0+2)+\frac 1 2\times(1^2+1+2)+\dots+\frac 12\left[(n-1)^2+(n-1)+2\right]=\\=\frac 12\left[1^2+2^2+\dots+(n-1)^2+1+2+\dots+(n-1)+2n\right]=\\=\frac 1 2\left[\frac{n\times(n-1)\times(2n-1)}{6}+\frac{n\times(n-1)}{2}+2n\right]=\frac{n^3+5n}{6}}
Therefore the number of regions created is
\latex{t(n)=\frac16\times(n^3+5n+6)}.
Note: The number of parts of plane and space can be expressed in the following form, which is easy to remember as they use the binomial coefficients. The following two equalities can be formed:
\latex{s(n)=\binom{n}0+\binom n 1+\binom n 2};
\latex{t(n)=\binom{n}0+\binom n 1+\binom n 2+\binom n 3}.
\latex{t(n)=\binom{n}0+\binom n 1+\binom n 2+\binom n 3}.
Exercises
{{exercise_number}}. Determine the number of finite and infinite regions determined by \latex{ n } independent lines in the plane.
{{exercise_number}}. Place \latex{ 7 } lines and \latex{ 6 } points in the plane such that there are exactly \latex{ 3 } points incident to every line.
{{exercise_number}}. At most how many intersection points can the diagonals of a convex \latex{ 7 }-gon determine?
{{exercise_number}}. There are \latex{ n } points given in the plane such that no three of them are incident to one line. How many lines are determined by these points?
{{exercise_number}}. There are \latex{ n } independent lines given in the plane. At most how many lines can their intersection points determine?
{{exercise_number}}. A set of \latex{ 5 } parallel lines are intersected perpendicularly by a set of \latex{ 11 } parallel lines. How many rectangles are determined by the lines of the resulting grid?
{{exercise_number}}. There are \latex{ n } independent points in the plane. We take the perpendicular bisector of every segment determined by these points. At most how many intersection points can these lines have?