HMMT 十一月 2019 · 冲刺赛 · 第 6 题

HMMT November 2019 — Guts Round — Problem 6

[6] Compute the sum of all positive integers n < 2048 such that n has an even number of 1’s in its binary representation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT November 2019, November 9, 2019 — GUTS ROUND Organization Team Team ID#

解析

[6] Compute the sum of all positive integers n < 2048 such that n has an even number of 1’s in its binary representation. Proposed by: Milan Haiman Answer: 1048064 Note that the positive integers less than 2047 are those with at most 11 binary digits. Consider the contribution from any one of those digits. If we set that digit to 1, then the remaining 10 digits can 9 be set in 2 = 512 ways so that the number of 1’s is even. Therefore the answer is 0 10 512(2 + · · · + 2 ) = 512 · 2047 = 1048064 .