2
$\begingroup$

I have $n$ lines in the plane such that no two are parallel and no three lines intersect in a common point.

Into how many finite regions do the lines divide the plane?

I came up with this recurrence relation: $$x_3=1, \qquad x_n=x_{n-1}+n-2 ,$$ and I found out it is correct. Even though I solved it intuitively, I'd like to understand how to prove this recurrence relation formally. How can I do it?

$\endgroup$
  • $\begingroup$ here is a good write up. If you search online, you'll find others. $\endgroup$ – lulu Aug 15 at 16:55
  • $\begingroup$ But why do you think $X_3=1$? Three lines in general position create $7$ regions $\endgroup$ – lulu Aug 15 at 16:57
  • $\begingroup$ @lulu Maybe OP wants only bounded regions. $\endgroup$ – Don Thousand Aug 15 at 16:58
  • 1
    $\begingroup$ @MatthewDaly and @ lulu, you seem to have missed the word "finite" in "how many finite regions." As such, both proposed links, although useful for techniques, answer the related but different question of counting how many regions are possible where we don't care if the regions are finite. $\endgroup$ – JMoravitz Aug 15 at 16:58
  • $\begingroup$ @JMoravitz Ah, thank you. $\endgroup$ – lulu Aug 15 at 16:58
1
$\begingroup$

We can adapt a standard trick used to solve the analogous problem for which we do not restrict to finite regions.

First, for any configuration of lines (like that of the solid lines in the diagram below), by rotating slightly we can assume that none of the lines are horizontal. Any region not bounded below has a unique lowest vertex (such regions may still be unbounded above), and conversely, every vertex is the lowest vertex of one region; in the diagram, the marked angles indicate which region is associated to each vertex.

enter image description here

The number of intersections---and hence the number of regions bounded below---is at most ${n \choose 2} = \frac{1}{2} n (n - 1)$, and this number is achieved exactly when the lines are in general position (i.e., no two lines are parallel, and no three lines intersect in a point). If we draw a horizontal line above all of the intersections (like the dotted line in the diagram), it intersects all $n$ of the lines in the original configuration (again, since none of those lines are horizontal), and so there are $n - 1$ regions corresponding to a vertex and unbounded above. (In the diagram, these are the regions marked by red angles.) Since every unbounded region is unbounded above or unbounded below, the maximum number of bounded regions is $$\frac{1}{2} n (n - 1) - (n - 1) = \color{#df0000}{\boxed{\frac{1}{2} (n - 1) (n - 2) = {n - 1 \choose 2}}} .$$ A standard induction argument shows this quantity value coincides with the term $x_n$ of your sequence for every $n$.

(Alternatively, if you take as given the result that $n$ lines in general position divide the plane into ${n + 1}\choose 2$ regions (including unbounded regions), then since $n$ lines yield $2 n$ unbounded regions---to see this, draw a circle enclosing all of the intersections of the lines---there are ${{n + 1}\choose 2} - 2 n$ bounded regions.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.