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

HMMT February 2009 — Guts Round — Problem 20

[ 10 ] A positive integer is called jubilant if the number of 1’s in its binary representation is even. For example, 6 = 110 is a jubilant number. What is the 2009th smallest jubilant number? 2

解析

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