Subdividing the plane
In the interest of developing my probabilistic intuition and facility with counting arguments, I went looking for probability problem books at the school library. The search reconfirmed by earlier suspicion that the library system here is in some subarea of mathematics smaller than UH’s. I did manage to find a good book, Probability Theory: Collection of Problems, published by the AMS. It has a range of exercises from counting arguments through martingales and functionals of wiener processes, and doesn’t skim on analytic questions– just what I’m look for in terms of exercises to bolster my understanding of more traditional monographs.
I got stuck on the 13th problem in the book:
What is the largest number of parts into which
straight lines can divide the plane?
so eventually I looked in the solution section. The solution begins with “Evidently, in order that the number of parts be maximal, it is necessary that no three straight lines intersect in one point and no two lines be parallel.” Hmm– it seems like a natural condition, but that hardly makes the truth of it evident.
I remember encountering this problem before in Knuth’s Concrete Mathematics, and seeing a convincing development of a solution, so I’ll see if I can find a copy later, but it bothers me that what this book says should be evident is not, at least to me.
Possibly relevant posts:
- Probabilistic Tools (8/25/2008)
- Painting houses (1/21/2005)
- Diff Eq. (5/18/2005)
Consider adding each line in turn to the plane. The first line divides the plane into two regions. Each successive line crosses, at a maximum, all of the lines that come before it once; each of these intersections divides the new line into n segments (if we’re laying the nth line down). For the sake of simplicity, we consider the two rays that result on either end of the new line to be segments as well. Each of those n segments of the new line divides a different region in two, so each segment adds 1 to the total count of regions in the plane.
Therefore, the nth line added to the drawing adds a maximum of n new regions into the plane, by dividing n regions into 2n regions; the maximum number of regions after adding n lines is therefore 1 (1 2 … n), or (n^2 n 2)/2.
If you draw it out on paper, you can see that this is the case… if you add each line such that it doesn’t run through any preexisting intersection points, and it crosses every line on the page already, you get 2 regions after one line, 4 regions after two lines, 7 regions after three lines, etc.
Hope this helps! Great blog, btw.
The words “evidently”, “obvious”, “immediate” and their ilk may be translated for, “I am too lazy to do this” at best, and “I am unable to do this” at worst. In either case, they have no place in any professional mathematics text.
I agree with the sentiment– those words are abused and misused much too often for anyone to be completely comfortable even when they’re employed correctly– but you have to admit that somethings *are* obvious. (just not in this case :))