Maximum number of regions in which the plane can be split using $n$ lines.

Question

I got this problem from here; the directions instruct to solve it by induction. I would appreciate it if someone could give me a hint on this problem.

One of the aspects which makes this problem difficult for me is that the following statement is not obvious (if it is even true) for me: "If you have arranged $n$ lines to give you the maximum number of regions possible with $n$ lines, the maximum number of regions possible with $n+1$ lines can be achieved by adding a line to the previous $n$ line configuration"

Although I haven't found a counterexample to the statement, I did find that by using $n=2$ and $n=3$ you can make the sequences (of number of regions) $(3, 6)$ and $(4, 6)$.

By sketching for $n = 1, 2, 3, 4$ I got $2, 4, 6, 10$ which is a nice sequence, but unfortunately for $n = 5$ the maximum I could make was $14$, not $16$.

I of course also noticed that if you make a line cutting through $k$ regions, you increase the number of regions by $k$.

Answer 1

You must have been doing something wrong drawing your 5 lines. Just draw a pentagram with extended lines and count clockwise so you're sure you didn't leave anything out:

But your sequence is flawed in other points, too, as Robert Israel pointed out; try ironing that using a similar principle. When you have a guess (or when you're feeling like confirming a hypothesis), it's a matter of proving that. Try thinking of cutting existing regions, and how many of them a new line that crosses each line so far will encounter.

Another possible hint is to see what happens if you go in reverse: starting with my picture, try removing one line and counting again. Then removing another. I'll leave you with that, the problem teaches you more if you do the main part of it yourself.

Answer 2

For $n=3$ you should get $7$, not $6$.

Hint: the $n$'th line should intersect each of the previous lines in a distinct point.

Answer 3

I will first give the explanation for the proof of the formula by induction followed by a derivation of the same formula by combinatorial methods.

Let $f(n)$ be the maximum number of regions into which $n$ lines divide a plane.

Now, let us add the $(n+1)$th line. Provided none of the lines are collinear and no 3 lines intersect at the same point upon adding the new line, this new $(n+1)$th line would make an intersection with each of the previous $n$ lines. Hence the new line passes thorugh $(n+1)$ regions dividing each of these regions into two. Hence $(n+1)$ new regions are created when the $(n+1)$th line is added. This means that:

$f(n+1)=f(n)+(n+1)$.

Let me demonstrate this with an example:

Assume that we have 2 lines dividing a plane into 4 regions. When we add a 3rd line, it will intersect the previous 2 lines and will be passing through 3 regions: the region on one side of the 1st line, the region between the 1st line and 2nd line, and the region on the other side of the 2nd line. Hence 3 new regions have been created.

So, now we have the conditions: $f(n)=f(n-1)+n$ and $f(0)=1$

$f(n)=f(n-1)+n$

$f(n-1)=f(n-2)+n-1$

$f(n-2)=f(n-3)+n-2$

.....

$f(2)=f(1)+2$

$f(1)=f(0)+1$

$f(0)=1$

Adding the above equations gives:

$f(n)=1+(1+2+3+...+n)$

So, $f(n)=1+\frac{n(n+1)}{2}$

This can also be written in combinatorial form as:

$f(n)=\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$

This combinatorial formula is not a mere coincidence. In fact, there is a combinatorial proof for this formula by considering the "deepest points" in the plane. I will briefly explain about it here:

Each region in the plane (except for the regions which are not bounded below) has exacly one "deepest point" (i.e. a point at the deepest "corner" in that region). This deepest point is the deepest point of only that particular region and not of any of the other 3 regions adjacent to it. We can also notice that an intersection between any two lines will create exactly one deepest point belonging to one particular region. The maximum number of points of intersections created by $n$ lines is $\binom{n}{2}$. Hence, there are $\binom{n}{2}$ deepest points.

Now let us consider the regions which do not have a deepest point. These are the regions which are not bounded below. So we cannot pick out a deepest point for these regions. There are exactly $n+1$ such regions.

So the total number of regions is $\binom{n}{2}+n+1=\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$.

There is also a 3 dimensional version of this problem which asks for the maximum number of regions into which n planes divide a space. The answer turns out to be $\binom{n}{3}+\binom{n}{2}+\binom{n}{1}+\binom{n}{0}$. This can also be proved by the induction method (considering the number of regions divided by the $(n+1)$th plane) as well as the combinatorial method (using the concept of deepest points).