I'm studying Concrete Mathematics by Donald Knuth. While doing the warmup questions, from the recurrence chapter, I stumbled upon an interesting problem. I have an intuition about the solution but I don't know how to express it. If you can give me any pointers I would greatly appreciate it.
The problem that I'm interested in is based on this original problem:
What is the maximum number $L(n)$ of regions defined by $n$ lines in the plane. The book goes to explain the recurrence $L(n) = L(n-1) + n$. We identify this pattern from generating solutions for the first few smaller scenarios
$L(0) = 1$
$L(1) = 2$
$L(2) = 4$
$L(3) = 7$
and so on… The book then identifies the "closed form" $L(n) = n(n + 1)/2 + 1$
And now the problem I'm trying to solve:
Some of the regions defined by $n$ lines in the plane are infinite, while others are bounded. What's the maximum possible number of bounded regions?
Knuth stresses the importance of looking at smaller scenarios when we try to first understand a problem. In doing so I realized that when $n$ is $0, 1$ or $2$` we don't have any bounded areas. Once we get to $n = 3$` we get one bounded area. This would be our base case. If we go further we notice that the maximum bounded areas for $n = 4$ are $2$, $n = 3$ are $4$, $n = 5$ are $7$. It seems like the initial recurrence is happening again but for bounded areas it starts with $n = 3$ instead of $n = 0$. So the new recurrence would look like this for bounded areas: $L(n) = L(n – 3) + n – 3$.
Am I reasoning correctly about this problem and is there a better way to look at it? Can anybody offer suggestions on how to express this rational better if it is correct or if it's not correct why that's the case?
Best Answer
Call $T$ the bounded region between three lines and add a new line $\ell$. Then it isn't hard to see that for the number of bounded regions to be maximum, $\ell$ must pass through $T$.
By induction, we can show that if the number of bounded regions cut by $n$ lines is maximum, then they all pass through some triangular region $T$ (where three of them are on the sides). Indeed, the key observation here is that if $\ell$ is a new line, then all but finitely many translations don't change the number of regions it cuts out. Then for every choice of $\ell$ which doesn't intersect $T$ there is a translation that sends it to a choice that passes through $T$ and, thus, increases the number of bounded regions by at least one.
Furthermore, note that all the regions outside of $T$ are unbounded.
This means that all we have to do is count the maximum number of regions cut out by $m$ lines in a bounded region, but this is the same as the number of regions (bounded or not) cut out by $m$ lines in the plane. Thus the number of bounded regions cut out by $n$ lines in the plane is $$ B(n) = \begin{cases} 0 & \text{if } n < 3 \\ L(n-3) & \text{otherwise} \end{cases} $$
Important edit: As Darij Grinberg points out in the comments the above formula is actually wrong (basically because most lines through a triangle intersect only two of its sides). A preliminary examination of the first few cases suggests that the correct formula might be $$ B(n) = L(n-3) + n - 3 $$ for $n > 3$, but right now I don't know how to prove or disprove it.