HMMT 二月 2022 · 团队赛 · 第 8 题
HMMT February 2022 — Team Round — Problem 8
题目详情
- [50] Let P P · · · P be a regular n -gon in the plane and a , . . . , a be nonnegative integers. It is 1 2 n 1 n possible to draw m circles so that for each 1 ≤ i ≤ n , there are exactly a circles that contain P on i i their interior. Find, with proof, the minimum possible value of m in terms of the a . i
解析
- [50] Let P P · · · P be a regular n -gon in the plane and a , . . . , a be nonnegative integers. It is 1 2 n 1 n possible to draw m circles so that for each 1 ≤ i ≤ n , there are exactly a circles that contain P on i i their interior. Find, with proof, the minimum possible value of m in terms of the a . i Proposed by: Daniel Zhu P n 1 Answer: max a , . . . , a , | a − a | 1 n i i +1 i =1 2 Solution: For convenience, we take all indices modulo n . Let [ n ] be the set { 1 , 2 , . . . , n } . Also, let P 1 ′ ′ M = max( a , . . . , a ), d = | a − a | , and M = max( M, d ). We claim that M is the answer. 1 n i i +1 i 2 Let Ω be the circumcircle of the polygon. ′ First let’s prove that m ≥ M . Obviously m ≥ M . Also, there must be at least | a − a | circles i i +1 crossing Ω between P and P , and a circle can cross Ω at most twice. Thus m ≥ d . i i +1 We will present two ways to arrive at a construction. P Inductive construction. We use induction on a . If all the a are zero, then the problem is trivial. i i i Now assume that not all the a are zero the idea is that we are going to subtract 1 from a consecutive i ′ subset of the a so that the value of M goes down by 1. i There are two cases. First of all, if a = 0 for some i , then we can choose such an i so that a > 0. i i +1 Then, let j be the minimal positive integer so that a = 0. Then subtract 1 from a , . . . , a . i + j i +1 i + j − 1 It is clear that d decreases by 1. If a = a = · · · = a = 0, then M also goes down by 1. If not, i + j i + j +1 i ′ then M < d , so M goes down by 1 anyway. The second case is when a > 0 for all i . If all the a are the same then we are done by subtracting 1 from i i everything. If not, we can find i, j with j > i +1 so that a = M , a = M , and a , a , . . . , a < M . i j i +1 i +2 j − 1 Then subtract 1 from the complement of a , a , . . . , a . Then M goes down by 1 and d goes down j j +1 i − 1 by 1. Non-inductive construction. We will prove that if M ≤ d , then we may choose m = d . If M > d , then since d ≥ M − min( a , . . . , a ) we can subtract M − d from every a , draw M − d circles containing 1 n i every point, and apply the below construction. ′ ′ ′ ′ ′ Let a = a − min ( a ), A = { i | a < h, a ≥ h } , B = { i | a ≥ h, a < h } . Also, let i j j h h i i i +1 i i +1 P ′ s = | A | = | B | . Note that d = s and that s > 0 ⇐⇒ h ≤ max( a ). h h h h h i h ( j ) ′ For h ≤ max( a ) and 1 ≤ j ≤ s , define an arrangement of circles C as follows: let the elements of h i h A and B be a , b , a , b , . . . in order. Then for each i ≤ s add a circle covering the points in the h h 1 1 2 2 h ′ interval ( a , b ]. One can show that point P is covered by circles j times if a ≥ h and j − 1 times i i + j i i otherwise. S ( j ) h Now, for some choice of j for all h , consider taking C . Then, P is covered by circles h i h h P P j + a − M times. If we choose the j so that j = M , which can be shown to be possi- h i h h h h ble, we are done.