HMMT 二月 2009 · 冲刺赛 · 第 20 题

英文解析

20. [ 10 ] A positive integer is called jubilant if the number of 1’s in its binary representation is even. Forexample, 6 = 110 is a jubilant number. What is the 2009 th smallest jubilant number?
    Answer: 40182
    Solution: Notice that for each pair of consecutive positive integers 2 k and 2 k + 1, their binaryrepresentation differs by exactly one 1 (in the units digit), so exactly one of 2 and 3 is jubilant, exactlyone of 4 and 5 is jubilant, etc. It follows that there are exactly 2009 jubilant numbers less than or equalto 4019. We now simply need to check whether 4018 or 4019 is jubilant. Since the binary representationof 4018 is 111110110010, 4018 is the 2009 th jubilant number. 4