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

HMMT February 2004 — Team Round — Problem 13

[25] Let n be a positive odd integer. Prove that b log n c + b log ( n/ 3) c + b log ( n/ 5) c + b log ( n/ 7) c + · · · + b log ( n/n ) c = ( n − 1) / 2 . 2 2 2 2 2 Let σ ( n ) denote the sum of the (positive) divisors of n , including 1 and n itself.

解析

Let n be a positive odd integer. Prove that b log n c + b log ( n/ 3) c + b log ( n/ 5) c + b log ( n/ 7) c + · · · + b log ( n/n ) c = ( n − 1) / 2 . 2 2 2 2 2 4 b log k c 2 Solution: Note that b log k c is the cardinality of the set { 2 , 4 , 8 , . . . , 2 } , i.e., 2 the number of powers of 2 that are even and are at most k . Then b log ( n/k ) c is the 2 number of even powers of 2 that are at most n/k , or equivalently (multiplying each such number by k ) the number of positive even numbers ≤ n whose greatest odd divisor is k . Summing over all odd k , we get the number of even numbers ≤ n , which is just ( n − 1) / 2. Let σ ( n ) denote the sum of the (positive) divisors of n , including 1 and n itself.