HMMT 二月 2011 · TEAM1 赛 · 第 3 题

英文解析

3. [ 15 ] Let n be a positive integer, and let a , a , . . . , a be a set of positive integers such that a = 2 and
   1 2 n 1
   a = ϕ ( a ) for all 1 ≤ m ≤ n − 1, where, for all positive integers k , ϕ ( k ) denotes the number ofm m +1
   n − 1
   positive integers less than or equal to k that are relatively prime to k . Prove that a ≥ 2 .
   Solution: We first note that ϕ ( s ) < s for all positive integers s ≥ 2, so a > 2 for all m > 1.nm
   For integers s > 2, let A be the set of all positive integers x ≤ s such that gcd( s, x ) = 1. Sincesgcd( s, x ) = gcd( s, s − x ) for all x , if a is a positive integer in A , so is s − a . Moreover, if a is in A ,
   s ss s sa and s − a are different since gcd( s, ) = > 1, meaning is not in A . Hence we may evenly pairs
   2 2 2
   Team Round Aup the elements of A that sum to s , so ϕ ( s ), the number of elements of A , must be even. It followss sthat a is even for all m ≤ n − 1.
   If t > 2 is even, A will not contain any even number, so ϕ ( t ) ≤ . We may conclude that a ≥ 2 atmt m m − 1
   n − 2 n − 12
   for all m ≤ n − 1, so a ≥ a ≥ 2 a = 2 , as desired.
   n n − 1 1
   Finally, note that such a set exists for all n by letting a = 2 for all i .ii
   Complex Numbers [35]