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 ⊕ .kk =02
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 ⊕ .kk =02
Here ⌊ x ⌋ is the greatest integer not exceeding x .
⌊ ⌋
2013 2014 4027 2013 k
Answer: 2 (2 − 1) OR 2 − 2 Let k = a a ...a in base 2. Then =
2013 2012 0
⌊ ⌋2
0 a ...a in base 2. So the leftmost digit of k ⊕ is 1 if and only if a = 1, and the n th digitk
2013 1 2013
from the right is 1 if and only if a 6 = a (1 ≤ n ≤ 2013).2
n n − 1
In either case, the probability of each digit being 1 is . Therefore, the sum of all such numbers is 1
2014 2013 201412
· 2 · 11 . . . 11 = 2 (2 − 1) .
︸ ︷︷ ︸2
2014 digits 2
n +1