HMMT 二月 2015 · COMB 赛 · 第 5 题
HMMT February 2015 — COMB Round — Problem 5
题目详情
- For positive integers x , let g ( x ) be the number of blocks of consecutive 1’s in the binary expansion of x . For example, g (19) = 2 because 19 = 10011 has a block of one 1 at the beginning and a block 2 of 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).
解析
- For positive integers x , let g ( x ) be the number of blocks of consecutive 1’s in the binary expansion of x . For example, g (19) = 2 because 19 = 10011 has a block of one 1 at the beginning and a block 2 of 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). 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 n giving 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), with n n x ’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 ) n is simply 1 more than the number of digit changes in x (or 2 − x ), i.e. the total number of 01 and 10 occurrences in x . Finally, because exactly half of all n -digit binary sequences have 0 , 1 or 1 , 0 at n positions k, k + 1 (for 1 ≤ k ≤ n − 1 fixed), we conclude that the average value of g ( x ) + g (2 − x ) is n − 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 with its 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 and n − 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.