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

HMMT November 2010 — GEN1 Round — Problem 9

[ 7 ] What is the sum of all numbers between 0 and 511 inclusive that have an even number of 1s when written in binary?

解析

[ 7 ] What is the sum of all numbers between 0 and 511 inclusive that have an even number of 1s when written in binary? Answer: 65408 Call a digit in the binary representation of a number a bit. We claim that for any given i between 0 and 8, there are 128 numbers with an even number of 1s that have a 1 in the bit i representing 2 . To prove this, we simply make that bit a 1, then consider all possible configurations of 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 1s. As there are 128 possible configurations of all the bits but two, we find 128 possible numbers, proving our claim. i Therefore, each bit is present as a 1 in 128 numbers in the sum, so the bit representing 2 contributes i 128 · 2 to our sum. Summing over all 0 ≤ i ≤ 8, we find the answer to be 128(1 + 2 + . . . + 128) = 128 · 511 = 65408.