HMMT 二月 2013 · 代数 · 第 3 题

英文解析

3. Let S be the set of integers of the form 2 + 2 + 2 , where x, y, z are pairwise distinct non-negativeintegers. Determine the 100 th 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 16 th 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.)