HMMT 二月 2002 · 代数 · 第 9 题

英文解析

9. For any positive integer n , let f ( n ) denote the number of 1’s in the base-2 representation of n . For how many values of n with 1 ≤ n ≤ 2002 do we have f ( n ) = f ( n + 1)?
   Solution: 501 . If n is even, then n + 1 is obtained from n in binary by changing thefinal 0 to a 1; thus f ( n + 1) = f ( n ) + 1. If n is odd, then n + 1 is obtained by changingthe last 0 to a 1, the ensuing string of 1 s to 0 s, and then changing the next rightmost 0 to a 1. This produces no net change in the number of 1’s iff n ends in 01 in base 2. Thus,
   f ( n + 1) = f ( n ) if and only if n is congruent to 1 mod 4, and there are 501 such numbers in 2
   the specified range.