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

英文解析

16. Now suppose again that n is odd. Prove thatσ (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
    Solution: The term σ ( i ) b log ( n/i ) c is the sum of the divisors of i times the numberof even numbers ≤ n whose greatest odd divisor is i . Thus, summing over all odd i ,2
    we get the sum of d over all pairs ( d, j ), where j < n is even and d is an odd divisor 5
    of j . Each odd number d then appears b n/ 2 d c times, since this is the number of evennumbers < n that have d as a divisor. So the sum equalsb 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 cfor 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 ,
    which is less than n / 8, as required.2 6