HMMT 二月 2015 · COMB 赛 · 第 5 题

英文解析

5. For positive integers x , let g ( x ) be the number of blocks of consecutive 1’s in the binary expansion ofx . For example, g (19) = 2 because 19 = 10011 has a block of one 1 at the beginning and a blockof two 1’s at the end, and g (7) = 1 because 7 = 111 only has a single block of three 1’s. Compute 2
   g (1) + g (2) + g (3) + · · · + g (256).2
   n n − 2
   Answer: 577 Solution 1. We prove that g (1) + g (2) + · · · + g (2 ) = 1 + 2 ( n + 1) for all n ≥ 1,
   6 n ngiving an answer of 1 + 2 · 9 = 577. First note that g (2 ) = 1, and that we can view 0 , 1 , . . . , 2 − 1
   as n -digit binary sequences by appending leading zeros as necessary. (Then g (0) = 0.)
   n n
   Then for 0 ≤ x ≤ 2 − 1, x and 2 − x are complementary n -digit binary sequences (of 0’s and 1’s), withn nx ’s strings of 1’s (0’s) corresponding to 2 − x ’s strings of 0’s (resp. 1’s). It follows that g ( x ) + g (2 − x )
   is simply 1 more than the number of digit changes in x (or 2 − x ), i.e. the total number of 01 andn
   10 occurrences in x . Finally, because exactly half of all n -digit binary sequences have 0 , 1 or 1 , 0 atnpositions k, k + 1 (for 1 ≤ k ≤ n − 1 fixed), we conclude that the average value of g ( x ) + g (2 − x ) isn − 1 n +1 1 n n +1 n − 2
   1 + = , and thus that the total value of g ( x ) is · 2 · = ( n + 1)2 , as desired.
   2 2 2 2
   n n − 2
   Solution 2. We prove that g (1) + g (2) + · · · + g (2 − 1) = 2 ( n + 1). Identify each block of 1’s withits rightmost 1. Then it suffices to count the number of these “rightmost 1’s.” For each 1 ≤ k ≤ n − 1,
   the k th digit from the left is a rightmost 1 if and only if the k and k + 1 digits from the left are 1 and 0
   n − 2
   respectively. Thus there are 2 possible numbers. For the rightmost digit, it is a rightmost 1 if andn − 1 n − 2 n − 1 n − 2
   only if it is a 1, so there are 2 possible numbers. Sum up we have: ( n − 1)2 +2 = 2 ( n +1),
   as desired.
   Remark. We can also solve this problem using recursion or generating functions.