Saturday, August 1, 2009

Solutions to "Dividing a plane"

See the original puzzle

Every time you draw a line, it "splits" all of the regions which it goes through. Every time a region is split, it increases the number of regions by exactly one. Therefore, to maximize the number of regions, you want to have the line go through as many different regions as possible.

For example, here is a picture of the fourth line being drawn.
The fourth line (in color) crosses four regions. This is the best you can do, because there are only three other lines, and it can only cross each one once. Every time it crosses a line, it goes from one region to another. If it crosses three lines, then it crosses four regions. If it splits four regions, then the total number of regions increases by four.

In general, whenever you add the Nth line, the number of regions increases by N. When there are zero lines, we start out with a single region. Therefore, the maximum number of regions is equal to 1 + (1+2+3+...+N). If we simplify this equation,* we get 1+N*(N+1)/2.

The circles are more or less the same idea. Whenever you draw a circle, it splits every region it crosses into two. For example, here is a picture of the third circle being drawn:
The third circle splits at most four regions. This is the best it can do because there are only two other circles, and each circle can only be crossed twice. Just like with the lines, each time the circle crosses a line, it goes from one region to another. So if the circle crosses four lines, then it goes through four different regions, splitting each of them into two.

In general, whenever you add the Nth circle, it can crosses 2*(N-1) lines. Therefore, it goes through 2*(N-1) different regions. Note that there is an exception to this rule, when N=1, and it crosses zero lines. Even if the circle crosses zero lines, it still goes through one region, splitting it. The maximum number of regions which can be created by N circles is therefore 2+(2+4+6+...2*(N-1)). This simplifies to 2+N*(N-1). Note that because of the exception mentioned earlier, this equation fails for N=0, when there is only one region.

The ellipses are the same idea yet again. Except now, each pair of ellipses can cross themselves at most four times, rather than two. So the maximum regions which can be created by N ellipses is 2+(4+8+12+...4*(N-1)). This simplifies to 2+2*N*(N-1). Note that this equation also fails for N=0.

Also see the reader comments for other ways to think of the problem.

*If you are wondering how I simplified the equation, consider the sum (1+2+3+...+N).
Let x = 1+2+3+...+N
2x = (1+2+3+...+N) + (N+(N-1)+(N-2)+...+1)
2x = (1+N) + (2+N-1) + (3+N-2) + ... + (N+1)
2x = (N+1)*N
x = N*(N+1)/2

0 comments: