HMMT 二月 2008 · COMB 赛 · 第 5 题
HMMT February 2008 — COMB Round — Problem 5
题目详情
- [ 5 ] Let S be the smallest subset of the integers with the property that 0 ∈ S and for any x ∈ S , we have 3 x ∈ S and 3 x + 1 ∈ S . Determine the number of non-negative integers in S less than 2008.
解析
- [ 5 ] Let S be the smallest subset of the integers with the property that 0 ∈ S and for any x ∈ S , we have 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 second condition 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 k that S is the set of nonnegative integers whose tertiary representation contains only the digits 0 and 6 7 7