6. Let $\mathcal{S}$ be the smallest subset of the set of integers satisfying the following properties:
1) $0 \in \mathcal{S}, 2)$ if $x \in \mathcal{S}$, then $3 x \in \mathcal{S}$ and $3 x+1 \in \mathcal{S}$.

Find the number of non-negative integers in the set $\mathcal{S}$ that do not exceed 2009.
Solution 1. We will write the numbers from the set $\mathcal{S}$ in the ternary numeral system. Then, the transition from number $x$ to number $3x$ means appending 0 to the right of the "ternary representation" of the number $x$, and the transition from $x$ to $3x+1$ means appending 1 to the right. Therefore, a number belongs to the set $S$ if and only if its ternary representation consists only of 0 and 1.

It remains to note that $3 \cdot 729>2009>2 \cdot 729=2 \cdot 3^{6}$. From this, it follows that in the ternary representation, the number 2009 is a 7-digit number, with the first (most significant) digit being 2. The largest number obtained on the 7th step has the representation $1111111_{3}$, so it is less than 2009. Therefore, the total number of such numbers is $2^{7}=128$.