Day 18: CM, Page 5

Day 18: We're done with the Tower of Hanoi. The authors look at a different problem that will us practice the analytical skills we just learned. The question is: "What is the maximum number L(n) of regions defined by n lines in the plane?" First we look at small cases:


This picture skips n = 0 which is 1 - there is one region if there are no lines. From the sequence above, a pattern jumps out. The difference between the number of regions for each value of n is 1, 2, 3, 4. This is the same pattern as the difference between triangular numbers. In fact, the numbers look like 1 + (n(n+1)/2). But what if we didn't notice the pattern? Is there a more logical approach to this problem?

For each region that we split with a line, we make two regions - one region on one side of the line, and one region on the other side of the line. So if we split k regions, we make k new regions. So how do regions relate to the number of lines? It looks like we need to cross k-1 lines to make k regions. I'm not sure how to prove this.. but the idea is roughly as follows: when a new line hits the first line it will intersect, it has crossed one region and thus formed one new region; each line it hits after that forms one more region. As it crosses the last line and enters the final region, it forms one last region. So for each line we hit, we form one region except for the last line where we form two regions. Thus for k-1 intersected lines, we form k regions. Assuming that none of the lines we draw is parallel, the nth line will intersect all previous n-1 lines in one spot. That means it will form n new regions. So L(n) = L(n-1) + n for n > 0.

More on intersecting lines tomorrow.