Problem:
Into how many regions can a circle be cut by 10 parabolas?
Solution
Solution:
Answer:
We will consider the general case of parabolas, for which the answer is .
We will start with some rough intuition, then fill in the details afterwards. The intuition is that, if we make the parabolas steep enough, we can basically treat them as two parallel lines. Furthermore, the number of regions is given in terms of the number of intersections of the parabolas that occur within the circle, since every time two parabolas cross a new region is created. Since two pairs of parallel lines intersect in points, and pairs of parabolas also intersect in points, as long as we can always make all points of intersection lie inside the circle, the parallel lines case is the best we can do.
In other words, the answer is the same as the answer if we were trying to add ten pairs of parallel lines. We can compute the answer for pairs of parallel lines as follows: when we add the th set of parallel lines, there are already lines that the two new lines can intersect, meaning that each of the lines adds new regions. This means that we add regions when adding the th set of lines, making the answer
Now that we have sketched out the solution, we will fill in the details more rigorously. First, if there are parabolas inside the circle, and they intersect in points total, then we claim that the number of regions the circle is divided into will be at most , where is the number of parabolas that intersect the circle itself in exactly four points.
We will prove this by induction. In the base case of , we are just saying that the circle itself consists of exactly one region.
To prove the inductive step, suppose that we have parabolas with points of intersection. We want to show that if we add an additional parabola, and this parabola intersects the other parabolas in points, then this new parabola adds either or regions to the circle, and that we get regions if and only if the parabola intersects the circle in exactly four points.
We will do this by considering how many regions the parabola cuts through, following its path from when it initially enters the circle to when it exits the circle for the last time. When it initially enters the circle, it cuts through one region, thereby increasing the number of regions by one. Then, for each other parabola that this parabola crosses, we cut through one additional region. It is also possible for the parabola to leave and then re-enter the circle, which happens if and only if the parabola intersects the circle in four points, and also adds one additional region. Therefore, the number of regions is either or , and it is if and only if the parabola intersects the circle in four points. This completes the induction and proves the claim.
So, we are left with trying to maximize . Since a pair of parabolas intersects in at most points, and there are pairs of parabolas, we have . Also, , so . On the other hand, as explained in the paragraphs giving the intuition, we can attain by making the parabolas sufficiently steep that they act like pairs of parallel lines. Therefore, the answer is , as claimed.
For , the answer is .