HMMT 二月 2004 · 团队赛 · 第 16 题

HMMT February 2004 — Team Round — Problem 16

[40] Now suppose again that n is odd. Prove that 2 σ (1) b log n c + σ (3) b log ( n/ 3) c + σ (5) b log ( n/ 5) c + · · · + σ ( n ) b log ( n/n ) c < n / 8 . 2 2 2 2 2

解析

Now suppose again that n is odd. Prove that 2 σ (1) b log n c + σ (3) b log ( n/ 3) c + σ (5) b log ( n/ 5) c + · · · + σ ( n ) b log ( n/n ) c < n / 8 . 2 2 2 2 Solution: The term σ ( i ) b log ( n/i ) c is the sum of the divisors of i times the number 2 of even numbers ≤ n whose greatest odd divisor is i . Thus, summing over all odd i , 5 we get the sum of d over all pairs ( d, j ), where j < n is even and d is an odd divisor of j . Each odd number d then appears b n/ 2 d c times, since this is the number of even numbers < n that have d as a divisor. So the sum equals b n/ 2 c + 3 b n/ 6 c + 5 b n/ 10 c + · · · + n b n/ 2 n c ≤ ( n − 1) / 2 + 3( n − 1) / 6 + · · · + m ( n − 1) / 2 m, where m is the greatest odd integer less than n/ 2. (We can ignore the terms d b n/ 2 d c for d > m because these floors are zero.) This expression equals ( n − 1) / 2 + ( n − 1) / 2 + · · · + ( n − 1) / 2 = ( n − 1)( m + 1) / 4 ≤ ( n − 1)( n + 1) / 8 , 2 which is less than n / 8, as required. 6