## Saturday, April 9, 2016

### Number of Regions N Lines Divide Plane

http://www.cut-the-knot.org/proofs/LinesDividePlane.shtml
What is the maximum number Ln of regions defined by n lines in the plane?
We find and then solve a recursive formula for Ln, see [Concrete Mathematics, 4-8].
Obviously L0=1 and L1=2. Short experimentation will convince you that L2=4. However, the next number that intuition often suggests, i.e., L3=8 does not hold. Instead, L3=7. Why so? This is because, if we want to obtain the maximum possible number of regions, we shall not let the new line pass through the intersection of the first two, for then we would get six regions and can do better. Leaving that point on one side of the third line means that the line won't be able to cross all four already existent regions, but at most only three - one more than there are lines. This gives a clue to a general case.
When adding a line, the latter may cross the existent ones in so many distinct points and thus cross (and divide) so many existent regions. On reflection, \$L_{n+1}=L_{n}+(n+1). Further,
Ln+1=Ln+(n+1)=Ln1+[n+(n+1)]=Ln2+[(n1)+n+(n+1)] =L2+[3++(n1)+n+(n+1)]=L1+[2+3++(n1)+n+(n+1)]=L0+[1+2+3++(n1)+n+(n+1)]=1+[1+2+3++(n1)+n+(n+1)]=1+(n+1)(n+2)2.
In other words, Ln=n(n+1)2+1=n2+n+22.
n条线可以把一个平面最多分成几个部分