HMMT 二月 2007 · TEAM1 赛 · 第 9 题

英文解析

9. [ 35 ] Find all positive integers n such thatn
   ∑2
   3 n + 5
   φ ( k ) = .
   k =18
   Answer: 1 , 3 , 5 .
   Solution. We contend that the proper relation isn
   ∑2
   3 n + 5
   φ ( k ) ≤ . ( ∗ )
   k =18
   Let Φ( k ) denote the left hand side of ( ∗ ). It is trivial to see that for n ≤ 7 the posed inequality holds,
   has equality where n = 1 , 3 , 5 , and holds strictly for n = 7 . Note that φ (2 k ) ≤ k and φ (2 k + 1) ≤ 2 k,
   the former because 2 , 4 , . . . , 2 k share a common divisor. It follows that φ (2 k )+ φ (2 k +1) ≤ 3 k. Suppose
   3(2 k − 1) +52
   for the sake of induction that Φ(2 k − 1) < . Then
   2 28
   3(2 k − 1) + 5 3(2 k + 1) + 5
   Φ(2 k + 1) = Φ(2 k − 1) + φ (2 k ) + φ (2 k + 1) < + 3 k = .
   8 8
   To complete the proof, it is enough to note that for a positive integer k,
   2 2
   3(2 k − 1) + 5 3(2 k ) + 5 + k < .
   8 8