HMMT 二月 2013 · 代数 · 第 3 题

HMMT February 2013 — Algebra — Problem 3

Let S be the set of integers of the form 2 + 2 + 2 , where x, y, z are pairwise distinct non-negative integers. Determine the 100th smallest element of S .

解析

Let S be the set of integers of the form 2 + 2 + 2 , where x, y, z are pairwise distinct non-negative integers. Determine the 100th smallest element of S . Answer: 577 S is the set of positive integers with exactly three ones in its binary representation. ( ) ( ) ( ) d 9 10 The number of such integers with at most d total bits is , and noting that = 84 and = 120, 3 3 3 9 x y 9 we want the 16th smallest integer of the form 2 + 2 + 2 , where y < x < 9. Ignoring the 2 term, ( ) ( ) ′ d 6 x y ′ there are positive integers of the form 2 + 2 with at most d total bits. Because = 15, our 2 2 9 6 0 answer is 2 + 2 + 2 = 577. (By a bit , we mean a digit in base 2.)