HMMT 十一月 2014 · GEN 赛 · 第 9 题

HMMT November 2014 — GEN Round — Problem 9

For any positive integers a and b , define a ⊕ b to be the result when adding a to b in binary (base 2), neglecting any carry-overs. For example, 20 ⊕ 14 = 10100 ⊕ 1110 = 11010 = 26. (The operation ⊕ 2 2 2 is called the exclusive or .) Compute the sum 2014 ( ⌊ ⌋) 2 − 1 ∑ k k ⊕ . 2 k =0 Here ⌊ x ⌋ is the greatest integer not exceeding x . n +1

解析

For any positive integers a and b , define a ⊕ b to be the result when adding a to b in binary (base 2), neglecting any carry-overs. For example, 20 ⊕ 14 = 10100 ⊕ 1110 = 11010 = 26. (The operation ⊕ 2 2 2 is called the exclusive or .) Compute the sum 2014 ( ⌊ ⌋) 2 − 1 ∑ k k ⊕ . 2 k =0 Here ⌊ x ⌋ is the greatest integer not exceeding x . ⌊ ⌋ k 2013 2014 4027 2013 Answer: 2 (2 − 1) OR 2 − 2 Let k = a a ...a in base 2. Then = 2013 2012 0 2 ⌊ ⌋ k 0 a ...a in base 2. So the leftmost digit of k ⊕ is 1 if and only if a = 1, and the n th digit 2013 1 2013 2 from the right is 1 if and only if a 6 = a (1 ≤ n ≤ 2013). n n − 1 1 In either case, the probability of each digit being 1 is . Therefore, the sum of all such numbers is 2 1 2014 2013 2014 · 2 · 11 . . . 11 = 2 (2 − 1) . 2 ︸︷︷︸ 2 2014 digits n +1