HMMT 十一月 2010 · GEN1 赛 · 第 9 题

英文解析

9. [ 7 ] What is the sum of all numbers between 0 and 511 inclusive that have an even number of 1 s whenwritten in binary?
   Answer: 65408 Call a digit in the binary representation of a number a bit. We claim that for anygiven i between 0 and 8, there are 128 numbers with an even number of 1 s that have a 1 in the bitrepresenting 2 . To prove this, we simply make that bit a 1, then consider all possible configurationsiof the other bits, excluding the last bit (or the second-last bit if our given bit is already the last bit).
   The last bit will then be restricted to satisfy the parity condition on the number of 1 s. As there are
   128 possible configurations of all the bits but two, we find 128 possible numbers, proving our claim.
   Therefore, each bit is present as a 1 in 128 numbers in the sum, so the bit representing 2 contributesii
   128 · 2 to our sum. Summing over all 0 ≤ i ≤ 8, we find the answer to be 128(1 + 2 + . . . + 128) =
   128 · 511 = 65408.