Intersecting Ellipses
What is the maximum number of regions a plane may be cut into by 2017 ellipses?
The answer is 8132546.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
(I do believe the answer is indeed 2 ( n 2 − n + 1 ) , but I'm not convinced that this argument is rigorous.)
Unfortunately, I think your image over simplifies the scenario. While I agree that we generate at most 4 ( n − 1 ) intersection points, it is not clear why we can only generate at most 4 ( n − 1 ) regions. In particular, why can't there be some crazy intersecting with already intersected regions that lead to chaos?
What would seem better, is if we could somehow associate each region with a unique intersection point. However, the standard approach of "lowest point" doesn't quite seem to work.
Log in to reply
There is a relationship between the number of regions, R, number of points, P, and a number of segments S between neighboring points. The relationship is R + P - S = 2. Starting with two fully intersecting ellipses, which satisfy this relationship since they have R = 6, P = 4, and S = 8, we can proceed by adding not ellipses, but only individual segments, which will all of them together then generate the next ellipse. Segment may connect two existing points, in which case it increases R and S each by 1 and not change the relationship. Or it may connect an existing point to the middle of a segment. That will create a new point there (+1 for P), it will increase a number of regions by 1, and it will increase a number of segments by 2 (the new segment added plus the one generated by splitting an existing segment). 1 +1 = 2, so the balance will still be the off by 2 as before. Or the segment may connect two middles of sides generating 2 new points, one new region, and 3 new segments. 2 + 1 = 3. It could also connect to two internal points on the same side, with net gain of 2 points, 1 region, and 3 segments, or even go from a point to the same point with a net gain of one segment and one region. Nothing you do will change the fact that R + R - S = 2. (At least not as long as the segments added are attached to some of the existing segments. But the problems associated with having two separate groups of objects not intersecting each other at any point are not relevant for this problem.) So if you are satisfied that both the number of points and the number of segments is increasing as described, the number of regions is guaranteed to do likewise.
Previous discussion is actually more general than it needs to be. When placing in an additional ellipse in the ideal way, that is not going through any existing points, we put in a first segment going from side to the same side. That will generate two points and one region. Then we will continue connecting a point (the one made by the previous segment) to a side, each time generating one new point and one region. And finally we connect back to the starting point, going point to point, which will generate one region but no new points. So the number of points and the number of regions for the entire ellipse will be exactly the same.
@Marta Reece This problem (and its solution a year later) was published in Parabola Volume 20.2, in 1984. Let R n be the largest number of regions obtained from n ellipses. The n th ellipse meets each of the previous n − 1 ellipses at 4 points, and so there are 4 ( n − 1 ) points of intersection on this ellipse, which split the ellipse up into 4 ( n − 1 ) arcs. Each of these arcs subdivides one of the R n − 1 regions formed by the first n − 1 ellipses, forming 4 ( n − 1 ) extra regions, and hence R n = R n − 1 + 4 ( n − 1 ) . The rest is a matter of induction.
Isn't this problem similar to how many maximum number of slices(not necessarily regular) of a pizza can be cut by 2017 straight cuts ?
Log in to reply
Sort of. More like how many pieces would be cut if you were cutting with a double knife which makes two parallel cuts every time.
Log in to reply
Why double knife ? Is this problem similar to the concept used in the Lazy Caterers' Sequence ?
oh.. i tried 8132545 because of forget about "outside" region... and use hard " 1 + Sum(4*(n-1)) where n from 1 to 2017 " formula..
The first ellipse in a plane will divide it into two regions. The second, if it intersects the first four times, which is the most it can do, will raise it to 6. The third, if it cuts both of the first in the best it can, will make it 14. Generally ellipse number n will contribute 4 × ( n − 1 ) regions. This is demonstrated in the figure above. Assume the brown ellipses already exist. We are not concerned with their interaction with each other here. And the red ellipse is being added. The most it can do in a way of generating regions is to intersect each existing ellipse in four points. The regions generated will be: the end region, before an ellipse is encountered, then four regions per ellipse except one of the end ellipses (number 4 in the image), which only contributes two, and then the other end. That comes to 4 × ( n − 2 ) + 2 + 2 = 4 × ( n − 1 ) .
Since the increase in number of regions at each step is a linear function of n , total number of regions will be a quadratic function of n which we car write as a n 2 + b n + c . The coefficients of this function can be obtained from the first three values (corresponding to n = 1 , 2 , and 3.
a + b + c = 2
4 a + 2 b + c = 6
9 a + 3 b + c = 1 4
The coefficients are a = 2 , b = − 2 , c = 2 and the function is 2 ( n 2 − n + 1 ) . For 2017 this is 8,132,546.
It is left to show that all ellipses are capable of actually intersecting all existing ellipses. We can imagine them very very elongated, so that they are effectively functioning as straight lines. As long as two straight lines are not parallel to each other, they will intersect. Intersections inside the mess of other lines/ellipses, will generate the same number of regions per ellipse crossed.