Let's say we have a plane. Draw N straight lines on the plane, any way you wish. Try to divide the plane into as many different regions as possible. How many regions is that? For example, if we draw 1 line on the plane, we can divide it into two regions. If we draw 2 lines, we can divide it into four regions.
Followup questions: Draw N perfect circles on a plane, of any size, anywhere you want. Into how many regions can you divide the plane? Next, draw N perfect ellipses on another plane. Into how many regions can you divide the plane?
This is, by the way, what's called a combinatorics puzzle. Combinatorics is the branch of mathematics which is all about counting. Fabricated statistics say that 50% of my readers will run away at the first mention of math, but surely no one's afraid of a little counting?
Solution has been posted
Thursday, July 16, 2009
Subscribe to:
Post Comments (Atom)
11 comments:
I have formulas from WolframMathWorld.
Lines: (n^2+n+2)/2
Circles: n^2-n+2
Ellipses: (n^2-n+1)*2
The sketches show no size and form variations.
Are those important?
95% percent of all statistics are made up.
Eduard,
If that's what WolframMathWorld says, then it is mistaken. The formulas certainly fail when n=0 (that is, you can't cut the plane in two with zero circles).
Size and form may or may not matter.
In the case of lines, for each n, you can create n new regions. Informally: say line n created x new regions. By drawing line n+1 parallel and very close to line n, you can always create another x new regions. But then you can angle line n+1 ever so slightly, so that it intersects line n and creates x+1 new regions.
If we then assume that line n created as many new sections as it possibly could have, then line n+1 has too now, since it can't cross any lines that n couldn't have. The only "advantage" it has over line n is that it can cross line n too!
So if f(n) = the number of new regions created by line n, then f(n + 1) = f(n) + 1, and f(1) = 1, so f(n) = n for all n > 0. And if r(n) = the total number of regions created, then r(n) = 1 + f(1) + f(2) + ... + f(n) = 1 + 1 + 2 + ... + n = 1 + (n)(n + 1)/2
I like this last version of the equation better than the Wolfram version. It's easier to do in one's head.
I have to think about circles and ellipses more, but I suspect that similar logic would apply.
Yes, I think similar logic applies. Without going into detail, each new circle can create as many new regions as the previous circle did, plus two more (instead of one as with lines -- since circles intersect each other twice instead of just once). Then in the case of ellipses, each ellipse can cross the previous one four times. I'm too lazy to work out the recurrence relations though.
Scott, that's a very well-reasoned solution, and it is correct. Congratulations.
That is, I was referring to your solution with the straight lines.
Late again...
Dividing the plane with lines is basically the same as the "cutting the cake" puzzle and Eduard and Scott seem to have that sorted. (The values are basically 1 more than the triangular numbers and the formula given by Ed works for all n.
For circles I get:
Circles : Regions
0 : 1
1 : 2
2 : 4
3 : 8
4 : 14
5 : 22
with each new circle n adding 2*(n-1) regions. Ed's formula seems to hold for all values of n>0 (0 must always be 1).
Drawing long skinny ellipses and copying the orientation I used for the lines gives the following:
E : R
0 : 1
1 : 2
2 : 6
3 : 14
4 : 26
with each new ellipse n adding 4*(n-1) regions, shadowing Scott's reasoning. Again, Ed's formula appears to hold for all values of n except 0.
There's obviously some subtlety that you're looking for that I'm missing. Perhaps a hint?
I didn't have the answer worked out before hand, so I just checked Eduard's solution for the simplest case, n=0. I guess that threw everyone off! But now you've got it.
Bonus points for anyone who explains why the polynomial function doesn't apply to the case n=0.
Hmm, well, when n=0 the formula for lines still applies, while in the other two cases, the formula does not. Superficially, this appears to be related to the fact that, as I said above, each pair of circles intersect one another twice, and each pair of ellipses intersect one another four times; but the first circle/ellipse can only cut the plane in half, so C(0) = E(0) = L(0) = 1 and C(1) = E(1) = L(1) = 2. In other words, circles and ellipses "act like lines" for the first two terms.
It occurs to me that this might have something to do with the analogy between difference equations/recurrence relations and differential equations. Consider Secret Squïrrel's formula 2*(n-1). I take this to be shorthand for C(n) = C(n-1) + 2*(n-1). Much like a differential equation, this equation requires some initial values in order to have a unique solution. So this puzzle is sort of like a so-called "boundary value problem." It just so happens that the boundary values for L(n) yield a nice well-behaved equation, but the same boundary values for C(n) and E(n) don't. There might be a more precise or well-developed way of saying this, but I can't push my intuition here any further.
I also have a geometric interpretation of this phenomenon. I've occasionally heard people describe lines on the plane as "circles intersecting the point at infinity." From that perspective, the line problem appears to be equivalent to the circle problem with the additional constraint that all the circles intersect each other at one common point. This is why for the lower terms, circles and ellipses act like lines.
So here's a fun counter-problem. What is the answer to the ellipse problem with a similar constraint? That is, into how many regions can n ellipses divide the plane if each of them shares one intersection point. And what is the plane-curve equivalent of an ellipse that "intersects the point at infinity"? I have guesses for both, but they're just guesses.
Ok, I'm back.
In response to Scott, since restricting ellipses to sharing a common intersection point will reduce the number of new regional divisions by 1 for each new ellipse, you should get the following series -
E : R
0 : 1
1 : 2
2 : 5
3 : 11
4 : 20
etc.
Following the format initially used by Ed, the formula would be R=(n^2-n+(4/3))*1.5
Rearranging these formulae slightly provides a small further insight with regard to the formula series. "r" prefix means restricted to having one common intersection.
Lines/rCircles - 0.5*(n^2+n)+1
Circles - 1.0*(n^2-n)+2
rEllipses - 1.5*(n^2-n)+2
Ellipses - 2.0*(n^2-n)+2
I'm guessing that the formula for lines is of a different form from the others because they can only ever intersect each other at one point, whereas circles and ellipses are closed loops and must intersect an even number of times (for the original puzzle since touching tangentially isn't an efficient sol'n).
This is prob also related to why the non-line formulas fail for n=0. As Scott said, the first one always divides the plane into two - there is no other shape for them to intersect so they all have zero intersections for the first two terms (n=0, n=1), but then while lines add 1 intersection per other line crossed, circles add 2 per other circle, and ellipses add 4.
I'm not sure about the plane-curve equiv for ellipses.
Post a Comment