HMMT 二月 2010 · TEAM2 赛 · 第 6 题
HMMT February 2010 — TEAM2 Round — Problem 6
题目详情
- [ 25 ] Into how many regions can a circle be cut by 10 parabolas?
解析
- [ 25 ] Into how many regions can a circle be cut by 10 parabolas? 2 Answer: 201 We will consider the general case of n parabolas, for which the answer is 2 n + 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 4 points, and pairs of parabolas also intersect in 4 points, as long as we can always make all 4 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 k th set of parallel lines, there are already 2 k − 2 lines that the two new lines can intersect, meaning that each of the lines 1 adds 2 k − 1 new regions . This means that we add 4 k − 2 regions when adding the k th set of lines, 2 2 making the answer 1+2+6+10+14+ · · · +(4 n − 2) = 1+2(1+3+5+7+ · · · +(2 n − 1)) = 1+2 · n = 2 n +1. Now that we have sketched out the solution, we will fill in the details more rigorously. First, if there are n parabolas inside the circle, and the they intersect in K points total, then we claim that the number of regions the circle is divided into will be at most K + n + r + 1, where r 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 = 0, we are just saying that the circle itself consists of exactly one region. To prove the inductive step, suppose that we have n parabolas with K points of intersection. We want to show that if we add an additional parabola, and this parabola intersects the other parabolas in p points, then this new parabola adds either p + 1 or p + 2 regions to the circle, and that we get p + 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 2 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 1 This is the maximum possible number of new regions, but it’s not too hard to see that this is always attainable. 2 While the fact that a curve going through a region splits it into two new regions is intuitively obvious, it is actually very difficult to prove. The proof relies on some deep results from algebraic topology and is known as the Jordan Curve Theorem. If you are interested in learning more about this, see http://en.wikipedia.org/wiki/Jordan_curve_theorem Team Round B the circle in four points, and also adds one additional region. Therefore, the number of regions is either p + 1 or p + 2, and it is p + 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 + 1. Since a pair of parabolas intersects in at ( ) ( ) n n 2 most 4 points, and there are pairs of parabolas, we have K ≤ 4 = 2 n − 2 n . Also, r ≤ n , so 2 2 2 K + n + r + 1 ≤ 2 n + 1. On the other hand, as explained in the paragraphs giving the intuition, we 2 can attain 2 n + 1 by making the parabolas sufficiently steep that they act like pairs of parallel lines. 2 Therefore, the answer is 2 n + 1, as claimed.