HMMT 二月 2007 · TEAM1 赛 · 第 9 题

HMMT February 2007 — TEAM1 Round — Problem 9

解析

[ 35 ] Find all positive integers n such that n 2 ∑ 3 n + 5 φ ( k ) = . 8 k =1 Answer: 1 , 3 , 5 . Solution. We contend that the proper relation is n 2 ∑ 3 n + 5 φ ( k ) ≤ . ( ∗ ) 8 k =1 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 2 3(2 k − 1) +5 for the sake of induction that Φ(2 k − 1) < . Then 8 2 2 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