PUMaC 2012 · 个人决赛（B 组） · 第 2 题
PUMaC 2012 — Individual Finals (Division B) — Problem 2
题目详情
- Let O , O , . . . , O be 2012 circles in the plane such that no circle intersects or contains any 1 2 2012 other circle and no two circles have the same radius. For each 1 ≤ i < j ≤ 2012, let P denote i,j the point of intersection of the two external tangent lines to O and O , and let T be the set of i j ( ) 2012 all P (so | T | = = 2023066). Suppose there exists a subset S ⊂ T with | S | = 2021056 i,j 2 such that all points in S lie on the same line. Prove that all points in T lie on the same line. 2 3
解析
- Let O , O , . . . , O be 2012 circles in the plane such that no circle intersects or contains any 1 2 2012 other circle and no two circles have the same radius. For each 1 ≤ i < j ≤ 2012, let P denote i,j the point of intersection of the two external tangent lines to O and O , and let T be the set of i j ( ) 2012 all P (so | T | = = 2023066). Suppose there exists a subset S ⊂ T with | S | = 2021056 i,j 2 such that all points in S lie on the same line. Prove that all points in T lie on the same line. Solution: For each O , let S be the sphere which has O as a great circle. Then P is the apex of the i i i i,j cone tangent to S and S . As all three of these apexes must lie in both of the planes which i j are externally tangent to the three spheres, they must lie along the line in which these two planes intersect, so they must be collinear. Once we have this result, the problem reduces to a graph theory question. Let l be the line containing the points of S , and let G be a simple graph with vertices v , v , . . . , v such 1 2 2012 that, for each 1 ≤ i < j ≤ 2012, v is adjacent to v if and only if P lies on l . From the i j i,j problem statement, we are given that | E ( G ) | ≥ 2021056. Also, our lemma says that for any three vertices a, b, c , if a is adjacent to b and b is adjacent to c , then a is adjacent to c . We first claim that G is connected. Suppose for the sake of contradiction that it is not. Then there exists some 1 ≤ k ≤ 2011 such that V ( G ) can be partitioned into two sets of sizes k ( ) ( ) k 2012 − k and 2012 − k with no edges going between them. This implies that | E ( G ) | ≤ + = 2 2 k ( k − 1)+(2012 − k )(2011 − k ) 2 = k − 2012 k +2023066. As this is a convex function of k , it achieves its 2 2 maximum at one of the endpoints of the interval, so | E ( G ) | ≤ 1 − 2012 + 2023066 = 2021055 (it takes the same value for k = 2011). This contradicts | E ( G ) | ≥ 2021056, so we conclude that G is connected. We now claim that G is complete. Since G is connected, for any two vertices a and b there exists a path from a to b , say au u . . . u b . Repeated application of the lemma gives that a 0 1 n 1 is adjacent to u , u , . . . , u , and finally to b . We conclude that every pair of vertices of G is 1 2 n adjacent, which gives the desired result. 2 3