HMMT 二月 2008 · COMB 赛 · 第 5 题

英文解析

5. [ 5 ] Let S be the smallest subset of the integers with the property that 0 ∈ S and for any x ∈ S , wehave 3 x ∈ S and 3 x + 1 ∈ S . Determine the number of non-negative integers in S less than 2008.
   Answer: 128 Write the elements of S in their ternary expansion (i.e. base 3). Then the secondcondition translates into, if d d · · · d ∈ S , then d d · · · d 0 and d d · · · d 1 are also in S . It follows
   1 2 k 1 2 k 1 2 kthat S is the set of nonnegative integers whose tertiary representation contains only the digits 0 and
   6 7 7