PUMaC 2010 · 组合（A 组） · 第 3 题
PUMaC 2010 — Combinatorics (Division A) — Problem 3
题目详情
- Sterling draws 6 circles on the plane, which divide the plane into regions (including the un- bounded region). What is the maximum number of resulting regions?
解析
- Sterling draws 6 circles on the plane, which divide the plane into regions (including the un- bounded region). What is the maximum number of resulting regions? Answer: 32 Solution: Let R ( n ) be the greatest number of regions that n circles can divide the plane into. We want to calculate R ( n + 1) in terms of R ( n ). Suppose we have drawn n circles on the plane, dividing the plane into r regions. Suppose we draw another circle, forming k intersection points with the existing circles. If k = 0, then there are no intersection points, and the resulting number of regions is r + 1. Otherwise, the k intersection points divide the new circle into k arcs. Each arc divides an existing region into two regions, so the resulting number of regions is r + k . Since the new circle intersects each 1 other circle at most twice, we have k ≤ 2 n . By definition, r ≤ R ( n ), so the resulting number of regions is at most R ( n ) + 2 n . To show that this maximum is attainable, we need to produce a set of n + 1 circles such that every pair of circles intersects twice, and every intersection point is distinct. It should be easy for the reader to convince himself or herself that there is such a set for all n + 1 ≤ 6 by drawing circles on paper. Therefore R ( n + 1) = R ( n ) + 2 n for all n ≤ 5. We can easily see that R (1) = 2. Repeatedly applying the recursive equation, we obtain R (6) = 32 . For a solution that doesn’t require drawing circles on paper that look like they intersect prop- erly, we can prove the following statement: Claim: For all m , there exists a set of m circles such that every pair of circles intersects twice, and every intersection point is distinct. Proof: Take a regular m -gon, and let s be the radius of the circumcircle of the m -gon. Put m circles at the vertices of the m -gon, all with the same radius, and let the common radius be greater than s . For two circles of the same radius to intersect twice, it is sufficient for the common radius to be greater than half the distance between the centers of the circles. Since the distance between the centers of any two of these circles is at most 2 s , the diameter of the circumcircle, and since the common radius is greater than s , every pair of circles intersects twice. Now suppose for contradiction that some three circles pass through the same point P . Then P is equidistant from three distinct points on the circumcircle of the m -gon, so P is the circumcenter of the triangle formed by these three points and thus the circumcenter of the m -gon. But then the distance between P and the three points is s . Since the common radius is greater than s , P is not on any of the circles, a contradiction. Therefore, every intersection point is distinct. Therefore, such a set of circles exists for all m .