Maths Olympiad Prep

Library / /279 of 377

Geometry Difficulty 5.4 AIME, harder Prove it United States

Problem:
Into how many regions can a circle be cut by 10 parabolas?

Solution

Solution:
Answer: 201201

We will consider the general case of nn parabolas, for which the answer is 2n2+12 n^{2} + 1.

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 44 points, and pairs of parabolas also intersect in 44 points, as long as we can always make all 44 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 kkth set of parallel lines, there are already 2k22k-2 lines that the two new lines can intersect, meaning that each of the lines adds 2k12k-1 new regions. This means that we add 4k24k-2 regions when adding the kkth set of lines, making the answer
1+2+6+10+14++(4n2)=1+2(1+3+5+7++(2n1))=1+2n2=2n2+1. 1 + 2 + 6 + 10 + 14 + \cdots + (4n-2) = 1 + 2(1 + 3 + 5 + 7 + \cdots + (2n-1)) = 1 + 2 \cdot n^{2} = 2n^{2} + 1.

Now that we have sketched out the solution, we will fill in the details more rigorously. First, if there are nn parabolas inside the circle, and they intersect in KK points total, then we claim that the number of regions the circle is divided into will be at most K+n+r+1K + n + r + 1, where rr 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 n=0n=0, we are just saying that the circle itself consists of exactly one region.

To prove the inductive step, suppose that we have nn parabolas with KK points of intersection. We want to show that if we add an additional parabola, and this parabola intersects the other parabolas in pp points, then this new parabola adds either p+1p+1 or p+2p+2 regions to the circle, and that we get p+2p+2 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 p+1p+1 or p+2p+2, and it is p+2p+2 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 K+n+r+1K + n + r + 1. Since a pair of parabolas intersects in at most 44 points, and there are (n2)\binom{n}{2} pairs of parabolas, we have K4(n2)=2n22nK \leq 4 \binom{n}{2} = 2n^{2} - 2n. Also, rnr \leq n, so K+n+r+12n2+1K + n + r + 1 \leq 2n^{2} + 1. On the other hand, as explained in the paragraphs giving the intuition, we can attain 2n2+12n^{2} + 1 by making the parabolas sufficiently steep that they act like pairs of parallel lines. Therefore, the answer is 2n2+12n^{2} + 1, as claimed.

For n=10n = 10, the answer is 2×102+1=2012 \times 10^{2} + 1 = 201.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.