Dividing The Plane 直线划分平面

A line dividesthe plane into two pieces (regions). Draw another line. The plane is nowdivided into three or four regions. It is three regions if the lines areparallel, four if they intersect. For the purposes of this article, we want thegreatest number of regions. So, two lines, four regions. A third line dividesthe plane into seven regions (See the diagram). The results, so far:

lines	regions
1	2
2	4
3	7

Using a little algebra, we can find an equation for the first three lines:

R(n) = an² + bn + c
2 =  a +  b + c
4 = 4a + 2b + c
7 = 9a + 3b + c
...
R(n) = (n²+n+2)/2

We see, from the diagram, that four lines produces eleven regions. So wesee that our formula works for four lines. And we suspect that it is valid ingeneral. How do we prove that?

Let's say that we've got n lines (for some arbitrary n). Andwe add an n+1th line. That line goes throughregion-line-region-line-...-line-region. It went through n lines andn+1 regions (assuming that all of the lines intersect). For each regionthat it went through, it added a region (split that region into two regions).So it added n+1 regions. So, we've just proved the rule: R(n+1)=R(n)+ n + 1.

Our earlier formula, which works for some n, is:

R(n) = (n²+n+2)/2

What is R(n+1), by that formula?

R(n+1) = [(n+1)² + (n+1) + 2]/2
       = (n²+3n+4)/2
       = (n²+n+2)/2 + n + 1

In other words:

R(n+1) = R(n) + n + 1

So, our formula follows the rule R(n+1)=R(n) + n + 1. This meansthat we have actually proved our formula, by Mathematical Induction. Ourformula works for the first case (n=1). And we showed that if theformula works for some n, then it works for n+1.

By using Mathematical Induction, we have shown that if our formula worksfor n=1 (which it does), then it works for n=2. And if it worksfor n=2, then it works for n=3. And if it works for n=3,then it works for n=4, etc. In other words, it works for all, infinitelymany cases, from 1 on up.

---

Our formula, R(n)=(n²+n+2)/2 is an integer divided by 2. Doesit always give us an integer for R(n)? It should, because we never endup with a fraction of a region. Well, if n is even, then n²is even and n²+n+2 is even, we get an integer when we divide by 2.If n is odd, then n² is odd and n²+n+2 is even,we get an integer when we divide by 2.

Incidentally, our formula works for n=0. With no lines, we find thatthe plane is divided into one region. In our proof, we could have saved alittle effort, by using n=0 as the first case.

Notice: 100 lines divide the plane into 5051 regions. See my article,How To Be A Little Gauss, for an amazing"coincidence." Also notice that 1000 lines divide the plane into500501 regions. This article was actually the inspiration for that article.

© Copyright 1997, Jim Loy http://www.jimloy.com/geometry/plane.htm