HMMT 二月 2002 · 代数 · 第 9 题

HMMT February 2002 — Algebra — Problem 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)?

解析

For any positive integer n , let f ( n ) denote the number of 1’s in the base-2 represen- tation 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 the final 0 to a 1; thus f ( n + 1) = f ( n ) + 1. If n is odd, then n + 1 is obtained by changing the last 0 to a 1, the ensuing string of 1s to 0s, 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, 2 f ( n + 1) = f ( n ) if and only if n is congruent to 1 mod 4, and there are 501 such numbers in the specified range.